On the Languages Accepted by Watson-Crick Finite Automata with Delays
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-04-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/8/813 |
| _version_ | 1797538321227841536 |
|---|---|
| author | José M. Sempere |
| author_facet | José M. Sempere |
| author_sort | José M. Sempere |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-03-10T12:28:54Z |
| format | Article |
| id | doaj.art-4df4b88121df4d838cb45a7c52e6d60c |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T12:28:54Z |
| publishDate | 2021-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-4df4b88121df4d838cb45a7c52e6d60c2023-11-21T14:47:54ZengMDPI AGMathematics2227-73902021-04-019881310.3390/math9080813On the Languages Accepted by Watson-Crick Finite Automata with DelaysJosé M. Sempere0Valencian Research Institute for Artificial Intelligence (VRAIN), Universitat Politècnica de València, Camino de Vera, 46022 Valencia, SpainIn 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.https://www.mdpi.com/2227-7390/9/8/813Watson-Crick finite automatasticker systemsDNA computingformal languages |
| spellingShingle | José M. Sempere On the Languages Accepted by Watson-Crick Finite Automata with Delays Mathematics Watson-Crick finite automata sticker systems DNA computing formal languages |
| title | On the Languages Accepted by Watson-Crick Finite Automata with Delays |
| title_full | On the Languages Accepted by Watson-Crick Finite Automata with Delays |
| title_fullStr | On the Languages Accepted by Watson-Crick Finite Automata with Delays |
| title_full_unstemmed | On the Languages Accepted by Watson-Crick Finite Automata with Delays |
| title_short | On the Languages Accepted by Watson-Crick Finite Automata with Delays |
| title_sort | on the languages accepted by watson crick finite automata with delays |
| topic | Watson-Crick finite automata sticker systems DNA computing formal languages |
| url | https://www.mdpi.com/2227-7390/9/8/813 |
| work_keys_str_mv | AT josemsempere onthelanguagesacceptedbywatsoncrickfiniteautomatawithdelays |