nach oben

Natural Computing

Erschienen in:

01.12.2015

State complexity of deterministic Watson–Crick automata and time varying Watson–Crick automata

verfasst von: Kumar Sankar Ray, Kingshuk Chatterjee, Debayan Ganguly

Erschienen in: Natural Computing | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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. State complexity of Watson–Crick automata has also been discussed. In this paper we analyze the state complexity of deterministic Watson–Crick automata with respect to non-deterministic block automata and non-deterministic finite automata. We also introduce new finite automata combining the properties of Watson–Crick automata and time varying automata. These automata have the unique property that the 1-limited stateless variant of these automata have the power to count. We further discuss the state complexity of time varying automata and time varying Watson–Crick automata.

Vorheriger Artikel Multipartite entanglement in Grover’s search algorithm

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Campeanu C, Santean N, Yu S (1998) Minimal cover automata for finite languages, International workshop on implementing automata, WIA 98, Rouen, 32–42

Czeizler E, Czeizler E (2005) Parallel communicating Watson-Crick Automata systems, Proc. 11th International Conference AFL

Czeizler E, Czeizler E (2006a) On the power of parallel communicating Watson–Crick automata systems. Theor Comput Sci 358(1):142–147MATHMathSciNetCrossRef

Czeizler E, Czeizler E (2006b) A short survey on Watson-Crick automata. Bull EATCS 88:104–119MATHMathSciNetCrossRef

Czeizler E, Czeizler E, Kari L, Salomaa K (2009) On the descriptional complexity of Watson-Crick automata. Theor Comput Sci 410(35):3250–3260 28 August 2009MATHMathSciNetCrossRef

Freund R, Păun G, Rozenberg G, Salomaa A (1997) Watson-Crick finite automata, Proc 3rd DIMACS Workshop on DNA Based Computers, Philadelphia, 297–328

Krithivasan K, Das A (1986) Time varying finite automata. Int J Comput Math 19:103–123MATHCrossRef

Păun A, Păun M (1999) State and transition complexity of Watson-Crick finite automata. Fundam Comput Theory Lect Notes Comput Sci 1684:409–420CrossRef

Păun G, Rozenberg G, Salomaa A (1998) DNA computing: new computing paradigms. Springer-Verlag, BerlinMATHCrossRef

Ray KS, Chatterjee K, Ganguly D (2013) Equivalence of subclasses of two-way non-deterministic Watson-Crick automata. Appl Math 4(10):26CrossRef

Salomaa K, Yu S, Zhuang Q (1994) The state complexities of some basic operations on regular languages. Theor Comput Sci 125:315–328MATHMathSciNetCrossRef

Yu S (1997) Regular languages, in handbook of formal languages, vol 1, chap 2. Springer, Berlin, pp 41–110

Titel: State complexity of deterministic Watson–Crick automata and time varying Watson–Crick automata
verfasst von: Kumar Sankar Ray
Kingshuk Chatterjee
Debayan Ganguly
Publikationsdatum: 01.12.2015
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 4/2015
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9494-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2015

Asynchronous Boolean networks and hereditarily bijective maps

Hardware implementation of evolutionary algorithms using dynamic reconfiguration technology

Multipartite entanglement in Grover’s search algorithm

Minimization and equivalence in multi-valued logical models of regulatory networks

Time-free solution to SAT problem by P systems with active membranes and standard cell division rules

Text comprehension and the computational mind-agencies

Premium Partner