کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873882 | 1440709 | 2018 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Transducer descriptions of DNA code properties and undecidability of antimorphic problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Transducer descriptions of DNA code properties and undecidability of antimorphic problems Transducer descriptions of DNA code properties and undecidability of antimorphic problems](/preview/png/6873882.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 237-258
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 237-258
نویسندگان
Lila Kari, Stavros Konstantinidis, Steffen Kopecki,