nach oben

Natural Computing

Erschienen in:

01.09.2012

Stateless multicounter 5′ → 3′ Watson–Crick automata: the deterministic case

verfasst von: László Hegedüs, Benedek Nagy, Ömer Eğecioğlu

Erschienen in: Natural Computing | Ausgabe 3/2012

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider stateless counter machines which mix the features of one-head counter machines and special two-head Watson–Crick automata (WK-automata). These biologically motivated machines have heads that read the input starting from the two extremes. The reading process is finished when the heads meet. The machine is realtime or non-realtime depending on whether the heads are required to advance at each move. A counter machine is k -reversal if each counter makes at most k alternations between increasing mode and decreasing mode on any computation, and reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of deterministic stateless realtime WK-automata with counters that are reversal bounded. We give examples and establish hierarchies with respect to counters and reversals.

Vorheriger Artikel A genetic algorithm for the Zen Puzzle Garden game

Nächster Artikel Comparing simulation algorithms for multienvironment probabilistic P systems over a standard virtual ecosystem

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

Eğecioğlu Ö, Ibarra OH (2009) On stateless multicounter machines. In: CiE 2009, LNCS, vol 5635. Springer, Heidelberg, pp 178–187

Eğecioğlu Ö, Hegedüs L, Nagy B (2010) Stateless multicounter 5′ → 3′ Watson–Crick automata. In: 5th IEEE BIC-TA, pp 1599–1606

Freund R, Păun G, Rozenberg G, Salomaa A (1994) Watson–Crick finite automata. In: Proceedings of third annual DIMACS symposium on DNA based computers, pp 535–546

Hopcroft JE, Ullman JD (1979) Introduction to automata theory, languages and computation. Addison-Wesley, Reading

Ibarra OH, Eğecioğlu Ö (2009) Hierarchies and characterizations of stateless multicounter machines. In: COCOON 2009, LNCS 5609. Springer, Heidelberg, pp 408–417

Ibarra OH, Karhumäki J, Okhotin A (2008) On stateless multihead automata: hierarchies and the emptiness problem. In: LATIN’08, LNCS 4957. Springer, Heidelberg, pp 94–105

Korenjak AJ, Hopcroft JE (1966) Simple deterministic languages. In: FOCS, IEEE computer society, Los Alamitos, CA, pp 36–46

Kutrib M, Messerschmidt H, Otto F (2008) On stateless two-pushdown automata and restarting automata. In: 8th AFL, pp 257–268

Leupold P, Nagy B (2009) 5′ → 3′ Watson–Crick automata with several runs. In: NCMA, pp 167–180

Leupold P, Nagy B (2010) 5′ → 3′ Watson–Crick automata with several runs. Fundamenta Informaticae 104:71–91

Minsky ML (1967) Computation: finite and infinite machines. Prentice-Hall Inc., Upper Saddle River, NJ

Nagy B (2008) On 5′ → 3′ sensing Watson–Crick finite automata. In: DNA 13, LNCS 4848. Springer-Verlag, Berlin, Heidelberg, pp 256–262

Nagy B (2009) On a hierarchy of 5′ → 3′ sensing WK finite automata languages. In: CiE 2009, pp 266–275

Nagy B, Hegedüs L, Eğecioğlu Ö (2011) Hierarchy results on stateless multicounter 5′ → 3′ Watson–Crick automata. In: IWANN 2011, LNCS 6691. Springer, Heidelberg, pp 465–472

Păun G (1998) Computing with membranes. Technical report, TUCS

Păun G (2002) Membrane computing: an introduction. Springer-Verlag, Heidelberg

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

Yang L, Dang Z, Ibarra OH (2007) On stateless automata and P systems. In: Workshop on automata for cellular and molecular computing, pp 144–157

Titel: Stateless multicounter 5′ → 3′ Watson–Crick automata: the deterministic case
verfasst von: László Hegedüs
Benedek Nagy
Ömer Eğecioğlu
Publikationsdatum: 01.09.2012
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2012
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-011-9290-9

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 3/2012

Designing a new software tool for Digital Imagery based on P systems

The Gestalt heuristic: emerging abstraction to improve combinatorial search

Comparing simulation algorithms for multienvironment probabilistic P systems over a standard virtual ecosystem

Evolutionary mechanics: new engineering principles for the emergence of flexibility in a dynamic and uncertain world

Programming and evolving physical self-assembling systems in three dimensions

Emergence of synchronicity in a self-organizing spiking neuron network: an approach via genetic algorithms