Hierarchies of Stateless Multicounter 5' → 3' Watson-Crick Automata Languages

• Autorzy: Egecioglu Ö. , Hegedüs L. , Nagy B.
• Języki publikacji: EN

Abstrakty

EN

We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters.

Słowa kluczowe

EN

stateless multicounter WK-automata; automata languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 111--123
• Opis fizyczny: Bibliogr. 19 poz., wykr.

Twórcy

autor

Egecioglu Ö.

autor

Hegedüs L.

autor

Nagy B.

• Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, 4032, Hungary,

Bibliografia

• [1] Eğecioğlu, Ö, Ibarra, O.H.: On stateless multicounter machines. Ambos-Spies, K., Löwe, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 178-187. Springer, Heidelberg (2009)
• [2] Eğecioğlu, Ö., Hegedüs, L., Nagy, B.: Stateless multicounter 5′ → 3′ Watson-Crick Automata. In: Fifth International Conference on Bio-Inspired Computing: Theories and Applications, pp. 1599-1606. IEEE Press (2010)
• [3] Freund, R., Pǎun, Gh., Rozenberg, G., Salomaa, A.: Watson-Crick Finite Automata. In: Third Annual DIMACS Symposium on DNA Based Computers, Philadelphia, pp. 535-546 (1994)
• [4] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation. Series in Computer Science. Addison-Wesley, Reading, MA, 1979.
• [5] Ibarra O.H., Eğecioğlu, ö.: Hierarchies and characterizations of stateless multicounter machines. In: Ngo, H.G. (ed.) COCOON 2009. LNCS, vol. 5609, pp. 408-417. Springer, Heidelberg (2009)
• [6] Ibarra, O.H., Karhumäki, J., Okhotin, A.: On stateless multihead automata: hierarchies and the emptiness problem. In: Laber, E.S. et al. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 94-105. Springer, Heidelberg (2008)
• [7] A. J. Korenjak and J. E. Hopcroft, Simple deterministic languages. Proc. of IEEE 7th Ann. Symp. on Switching and Automata Theory, 1966, pp. 36-46.
• [8] M. Kutrib, H. Messerschmidt and Friedrich Otto, On stateless two-pushdown automata and restarting automata. Proceedings of the 8th Automata and Formal Languages,May, 2008, pp. 257-268.
• [9] Leupold, P., Nagy, B.: 5′ → 3′ Watson-Crick automata with several runs. In: Workshop on Non-Classical Models of Automata and Applications (NCMA), Wroclaw, Poland, pp. 167-180. [e-mail],österreichischen Computer Gesellschaft (2009)
• [10] Leupold, P., Nagy, B.: 5′ → 3′ Watson-Crick automata with several runs. Fundamenta Informaticae 104, pp. 71-91 (2010) (extended version of [9]).
• [11] Minsky,M.L.: Computation: finite and infinitemachines. Prentice-Hall, Upper Saddle River, NJ, USA (1967)
• [12] Nagy, B.: On a hierarchy of 5′ → 3′ sensing WK finite automata languages. In: CiE 2009: Mathematical Theory and Computational Practice, Abstract Booklet, pp. 266-275. University of Heidelberg (2009)
• [13] Nagy, B.: On 5′ → 3′ sensing Watson-Crick finite automata. In: Garzon, M.H., Yan, H. (eds.) DNA 13. LNCS vol. 4848, pp. 256-262. Springer, Heidelberg (2008)
• [14] Nagy, B.: 5′ → 3′ sensing Watson-Crick finite automata. In: G. Fung (ed.) Sequence and Genome Analysis: Methods and Application II, iConcept Press Ltd. (2011), in print
• [15] Nagy, B., Heged¨us, L., Eğecioğlu, ö.: Hierarchy Results On Stateless Multicounter 5′ → 3′ Watson-Crick Automata, IWANN 2011, LNCS vol. 6691, pp. 465-472. Springer, Heidelberg (2011)
• [16] Pǎun, Gh.: Computing with Membranes. Journal of Computer and System Sciences 61/1, 108-143 (2000)
• [17] Pǎun, Gh.: Computing with Membranes: An Introduction. Springer, Berlin (2002)
• [18] Pǎun, Gh., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer-Verlag, Berlin, Heidelberg (1998)
• [19] Yang, L., Dang, Z., Ibarra, O.H.: On stateless automata and P systems. In: Pre-Proceedings of Workshop on Automata for Cellular and Molecular Computing, pp. 144-157 (2007)