pith. sign in

arxiv: 1602.05721 · v1 · pith:JDQPESD3new · submitted 2016-02-18 · 💻 cs.FL

Restricted deterministic Watson-Crick automata

classification 💻 cs.FL
keywords deterministicrestrictedwatson-crickautomatalanguagesregularautomatoncontext
0
0 comments X
read the original abstract

In this paper, we introduce a new model of deterministic Watson-Crick automaton namely restricted deterministic Watson- Crick automaton which is a deterministic Watson-Crick automaton where the complementarity string in the lower strand is restricted to a language L. We examine the computational power of the restricted model with respect to L being in different language classes such as regular, unary regular, finite, context free and context sensitive. We also show that computational power of restricted deterministic Watson- Crick automata with L in regular languages is same as that of deterministic Watson-Crick automata and that the set of all languages accepted by restricted deterministic Watson-Crick automata with L in unary regular languages is a proper subset of context free languages.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.