Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

State and transition complexity of Watson-Crick finite automata

Andrei PăunContact Information and Mihaela Păun6

(6)  Department of Computer Science, University of Western Ontario, London, Ontario, Canada, N6A 5B7
Abstract
We consider the number of states and the number of transitions in Watson-Crick finite (non-deterministic) automata as descriptional complexity measures. The succinctness of recognizing regular languages by Watson-Crick (arbitrary or 1-limited) automata in comparison with non-deterministic finite automata is investigated, as well as decidability and computability questions. Major differences are found between finite automata and Watson-Crick finite automata from both these points of view.

Contact Information Andrei Păun
Email: apaun@csd.uwo.ca
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)