Loading...
Please wait, while we are loading the content...
Similar Documents
On the Languages Accepted by Watson-Crick Finite Automata with Delays
| Content Provider | MDPI |
|---|---|
| Author | Sempere, José |
| Copyright Year | 2021 |
| Description | In this work, we analyze the computational power of Watson-Crick finite automata (WKFA) if some restrictions over the transition function in the model are imposed. We consider that the restrictions imposed refer to the maximum length difference between the two input strands which is called the delay. We prove that the language class accepted by WKFA with such restrictions is a proper subclass of the languages accepted by arbitrary WKFA in general. In addition, we initiate the study of the language classes characterized by WKFAs with bounded delays. We prove some of the results by means of various relationships between WKFA and sticker systems. |
| Starting Page | 813 |
| e-ISSN | 22277390 |
| DOI | 10.3390/math9080813 |
| Journal | Mathematics |
| Issue Number | 8 |
| Volume Number | 9 |
| Language | English |
| Publisher | MDPI |
| Publisher Date | 2021-04-09 |
| Access Restriction | Open |
| Subject Keyword | Mathematics Logic Watson-crick Finite Automata Sticker Systems Dna Computing Formal Languages |
| Content Type | Text |
| Resource Type | Article |
