Reversible Watson-Crick automata

DOI10.1007/S00236-016-0267-0MaRDI QIDQ2406432zbMATH OpenOpenAlexFDO

Authors Kingshuk Chatterjee, Kumar S. Ray

Publication date 29 September 2017

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05283

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Watson-Crick automata are finite automata working on double strands. Extensive research work has already been done on non-deterministic Watson-Crick automata and on deterministic Watson-Crick automata. In this paper, we introduce a new model of Watson-Crick automata which is reversible in nature named reversible Watson-Crick automata and explore its computational power. We show even though the model is reversible and one way it accepts all regular languages and also analyze the state complexity of the above stated model with respect to non-deterministic block automata and non-deterministic finite automata and establish its superiority. We further explore the relation of the reversible model with twin-shuffle language and recursively enumerable languages.

Recommendations

• Watson-Crick quantum finite automata
• scientific article; zbMATH DE number 1342112
• On the descriptional complexity of Watson-Crick automata
• Unary Watson-Crick automata
• \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata

Cites work

• scientific article; zbMATH DE number 5605080 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 1342112 (Why is no real title available?)
• scientific article; zbMATH DE number 1390082 (Why is no real title available?)
• k + 1 Heads Are Better than k
• Developments in Language Theory
• Logical Reversibility of Computation
• On the descriptional complexity of Watson-Crick automata
• One-way reversible multi-head finite automata
• Reversible pushdown automata
• State complexity of deterministic Watson-Crick automata and time varying Watson-Crick automata
• Two-way reversible multi-head finite automata

Cited in

(5)

• Watson-Crick T0L Systems and Red-Green Register Machines
• Watson-Crick quantum finite automata
• Reversible Two-Party Computations
• scientific article; zbMATH DE number 1342112 (Why is no real title available?)
• Unary Watson-Crick automata

This page was built for publication: Reversible Watson-Crick automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2406432)