On Languages of P Automata

• Autorzy: Csuhaj-Varjú, Erzsébet , Vaszil, György
• Języki publikacji: EN

Abstrakty

EN

P automata are accepting computing devices combining features of classical automata and membrane systems. In this paper we introduce P n-stack-automata, a restricted class of P automata that mimics the behaviour of n-stack automata. We show that for n = 1 these constructs describe the context-free language class and for n = 3 the class of quasi-realtime languages.

Słowa kluczowe

EN

machine theory; language

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 133--149
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Csuhaj-Varjú, Erzsébet

• Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary,

autor

Vaszil, György

• Department of Computer Science, Faculty of Informatics, University of Debrecen, Kassai út 26, 4028 Debrecen, Hungary,

Bibliografia

• [1] Păun G. Computing with Membranes. Journal of Computer and Systems Sciences, 2000. 6(1):108-143. URL https://doi.org/10.1006/jcss.1999.1693.
• [2] Păun G, Rozenberg G, Salomaa A (eds.). The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, 2010. ISBN:0199556679, 9780199556670.
• [3] Csuhaj-Varjú E, Vaszil G. P Automata. In: Pre-Proceedings of the Workshop on Membrane Computing WMC-CdeA 2002, volume 1 of MolCoNet-IST-2001-32008. 2002 pp. 177-192.
• [4] Csuhaj-Varjú E, Vaszil G. P Automata or Purely Communicating P systems. In: Păun G, Rozenberg G, Salomaa A, Zandron C (eds.), WMC2002, volume 2597 of Lecture Notes in Computer Science. Springer, Berlin, 2003 pp. 219-233. doi:10.1007/3-540-36490-0_14.
• [5] Freund R, Oswald M. A Short Note on Analysing P Systems. EATCS Bulletin, 2002. 78:231-236.
• [6] Vaszil G. A Class of P Automata Characterizing Context-free Languages. In: Gutiérrez-Naranjo MA, et al (eds.), Proc. BWMC4, volume II of RGNC Report 03/2006. Fénix Editora, 2006 pp. 267-276.
• [7] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages. Springer-Verlag, Berlin Heidelberg, 1997. doi:10.1007/978-3-642-59136-5.
• [8] Book R, Greibach S. Quasi-realtime Languages. Mathematical Systems Theory, 1970. 4:97-111. doi:10.1007/BF01705890.
• [9] Csuhaj-Varjú E, Ibarra O, Vaszil G. On the Computational Complexity of P automata. Natural Computing, 2006. 5(2):109-126. doi:10.1007/s11047-005-4461-1.
• [10] Holzer M, Otto F. Shrinking Multi-pushdown Automata. In: Liskiewicz M, Reischuk R (eds.), FCT 2005, volume 3623 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, Heidelberg, 2005 pp. 305-316. doi:10.1007/11537311_27.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu
"Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja
sportu (2020).

Identyfikatory

DOI

10.3233/FI-2020-1876