Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Acta Informatica
Erschienen in: Acta Informatica 5/2017

19.04.2016 | Original Article

Reversible Watson–Crick automata

verfasst von: Kingshuk Chatterjee, Kumar Sankar Ray

Erschienen in: Acta Informatica | Ausgabe 5/2017

Einloggen

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

search-config
loading …

Abstract

Since 1970, reversible finite automata have generated interest among researcher; but till now, we have not come across a model of reversible read only one-way finite automata which accept all regular languages, In this paper, we introduce a new model of one-way reversible finite automata inspired by the Watson–Crick complementarity relation and show that our model can accept all regular languages. We further show that our model accepts a language which is not accepted by any multi-head deterministic finite automaton.
Vorheriger Artikel On the relations between Markov chain lumpability and reversibility
Nächster Artikel Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with , messages, and constant time

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 "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

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
Literatur
1.
2.
Morita, K.: Two-way reversible multi-head finite automata. Fundam. Inform. 110, 241–254 (2011)MathSciNetMATH
3.
Kutrib, M., Malcher, A.: One-way reversible multi-head finite automata. In: Reversible Computation. Lecture Notes in Computer Science, vol. 7581, pp. 14–28 (2013)
4.
5.
Pin, J.E.: On reversible automata. In: Proceedings of the first LATIN conference, Sao-Paulo, Brazil. Lecture Notes in Computer Science, vol. 583, pp. 401–416. Springer (1992)
6.
Freund, R., Păun, G., Rozenberg, G., Salomaa, A.: Watson–Crick finite automata. In: Proceedings of 3rd DIMACS Workshop on DNA Based Computers, Philadelphia, pp. 297–328 (1997)
7.
Păun, G., Rozenberg, G., Salomaa, A., Computing, D.N.A.: New Computing Paradigms. Springer, Berlin (1998)MATH
8.
Czeizler, E., Czeizler, E., Kari, L., Salomaa, K.: On the descriptional complexity of Watson–Crick automata. Theor. Comput. Sci. 410(35), 3250–3260 (2009)MathSciNetCrossRefMATH
9.
Ray, K.S., Chatterjee, K., Ganguly, D.: Equivalence of subclasses of two-way non-deterministic Watson-Crick automata. Appl. Math. 4(10A), 26–34 (2013)CrossRef
10.
11.
Păun, A., Păun, M.: State and transition complexity of Watson–Crick finite automata. In: Fundamentals of Computation Theory, vol. 1684, pp. 409–420. Lecture Notes in Computer Science (1999)
12.
Ray, K.S., Chatterjee, K., Ganguly, D.: State complexity of deterministic Watson–Crick automata and time varying Watson–Crick automata. Nat. Comput. 14(4), 691–699 (2015)MathSciNetCrossRef
13.
Kuske, D., Weigel, P.:The role of the complementarity relation in Watson–Crick automata and sticker systems. IN: Proceedings of DLT 2004. LNCS 3340, pp. 272–283. Springer (2004)
14.
Sempere, J.M.: Exploring regular reversibility in Watson–Crick finite automata. In: The Thirteenth International Symposium on Artificial Life and Robotics 2008 (AROB 13th ’08), B-Con Plaza, Beppu, Oita, Japan, January 31–February 2 (2008)
15.
Metadaten
Titel
Reversible Watson–Crick automata
verfasst von
Kingshuk Chatterjee
Kumar Sankar Ray
Publikationsdatum
19.04.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 5/2017
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-016-0267-0