Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873882 | Information and Computation | 2018 | 22 Pages |
Abstract
This work concerns formal descriptions of DNA code properties and related (un)decidability questions. This line of research allows us to give a property as input to an algorithm, in addition to any regular language, which can then answer questions about the language and the property. Here we define DNA code properties via transducers and show that this method is strictly more expressive than that of regular trajectories, without sacrificing the efficiency of deciding the satisfaction question. We also show that the maximality question can be undecidable. Our undecidability results hold not only for the fixed DNA involution but also for any fixed antimorphic permutation. Moreover, we also show the undecidability of the antimorphic version of the Post Correspondence Problem, for any fixed antimorphic permutation.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Lila Kari, Stavros Konstantinidis, Steffen Kopecki,