On the Languages Accepted by Watson-Crick Finite Automata with Delays

José M. Sempere
Additional contact information
José M. Sempere: Valencian Research Institute for Artificial Intelligence (VRAIN), Universitat Politècnica de València, Camino de Vera, 46022 Valencia, Spain

Mathematics, 2021, vol. 9, issue 8, 1-12

Abstract: 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.

Keywords: Watson-Crick finite automata; sticker systems; DNA computing; formal languages (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/8/813/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/8/813/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:8:p:813-:d:532798

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().