A Survey of Results on Stateless Multicounter Automata

• Autorzy: Ibarra O.H. , Egecioglu Ö.
• Języki publikacji: EN

Abstrakty

EN

A stateless multicountermachine hasm-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accepted if, when the input head is started on the left end marker with all counters zero, themachine eventually reaches the configurationwhere the input head is on the right end marker with all the counters again zero. We bring together a number of results on stateless multicounter automata of various different types: deterministic, nondeterministic, realtime (the input head moves right at every step), or non-realtime. We investigate realtime and non-realtime machines in both deterministic and nondeterministic cases with respect to the number of counters and reversals. In addition to hierarchy results, we also consider closure properties and the connections to stateless multihead automata.

Słowa kluczowe

EN

stateless multicounter machines; reversal-bounded; realtime; non-realtime; hierarchy; stateless multihead automata; closure properties

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 129--140
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Ibarra O.H.

autor

Egecioglu Ö.

• Department of Computer Science, University of California Santa Barbara, CA 93106, USA,

Bibliografia

• [1] Ö. Eğecioğlu, L. Hegedüs, and B. Nagy. Stateless multicounter 5′ → 3′ Watson-Crick Automata. In: Fifth International Conference on Bio-Inspired Computing: Theories and Applications, IEEE Press, pp. 1599-1606 (2010).
• [2] Ö. Eğecioğlu, L. Hegedüs, and B. Nagy. Hierarchies of Stateless Multicounter 5′ → 3′ Watson-Crick Automata Languages, Fundamenta Informaticae, Vol. 110, No. 1-4, pp. 111-123 (2011).
• [3] Ö. Eğecioğlu and O. H. Ibarra. On stateless multicounter machines. Ambos-Spies, K., Löwe, B., Merkle,W. (eds.) CiE 2009, LNCS, Vol. 5635, pp. 178-187 (2009).
• [4] P. Frisco and O. H. Ibarra. On stateless multihead finite automata and multihead pushdown automata. DLT 2009, LNCS, Vol. 5583, pp. 240-251 (2009).
• [5] R. Freund, Gh. Păun, G. Rozenberg, and A. Salomaa. Watson-Crick Finite Automata. In: Third Annual DIMACS Symposium on DNA Based Computers, Philadelphia, pp. 535-546 (1994).
• [6] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Series in Computer Science. Addison-Wesley, Reading, MA, 1979.
• [7] O. H. Ibarra. Reversal-boundedmulticounter machines and their decision problems. J. Assoc. for Computing Machinery, 25, pp. 116-133 (1978).
• [8] O. H. Ibarra and ö. Eğecioğlu. Hierarchies and characterizations of stateless multicountermachines. In: Ngo, H.G. (ed.), COCOON 2009, LNCS, Vol. 5609, pp. 408-417 (2009).
• [9] O. H. Ibarra, J. Karhumaki, and A. Okhotin. On stateless multihead automata: hierarchies and the emptiness problem. Proceedings of 8th Latin American Symposium, LNCS Vol. 4957, pp. 94-105 (2008).
• [10] A. J. Korenjak and J. E. Hopcroft. Simple deterministic languages. Proceedings of IEEE 7th Annu. Symp. On Switching and Automata Theory, pp. 36-46 (1966).
• [11] M. Kutrib, H. Messerschmidt, and Friedrich Otto. On stateless two-pushdown automata and restarting automata. Pre-Proceedings of the 8th Automata and Formal Languages,May (2008).
• [12] B. Nagy, L. Hegedüs, and ö. Eğecioğlu. Hierarchy Results On Stateless Multicounter 5′ → 3′ Watson-Crick Automata, IWANN 2011, LNCS, Vol. 6691, pp. 465-472 (2011).
• [13] Gh. Păun. ComputingwithMembranes. Journal of Computer and System Sciences, 61, 1, pp. 108-143 (2000) (and Turku Center for Computer Science-TUCS Report 208, November 1998, www.tucs.fi).
• [14] Gh. Păun. Computing with Membranes: An Introduction, Springer, Berlin, 2002.
• [15] L. Yang, Z. Dang, and O. H. Ibarra. On stateless automata and P systems. Pre-Proceedings of Workshop on Automata for Cellular and Molecular Computing, August (2007).