We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.
@article{ITA_2011__45_4_413_0,
author = {Nagy, Benedek and Otto, Friedrich},
title = {CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {45},
year = {2011},
pages = {413-448},
doi = {10.1051/ita/2011123},
mrnumber = {2876115},
zbl = {1250.68172},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2011__45_4_413_0}
}
Nagy, Benedek; Otto, Friedrich. CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) pp. 413-448. doi : 10.1051/ita/2011123. http://gdmltest.u-ga.fr/item/ITA_2011__45_4_413_0/
[1] and , Theory of traces. Theoret. Comput. Sci. 60 (1988) 1-82. | MR 947532 | Zbl 0652.68017
[2] , and , Context-free languages and pushdown automata, in Handbook of Formal Languages, Word, Language, Grammar, edited by G. Rozenberg and A. Salomaa. 1 (1997) 111-174. | MR 1469995 | Zbl 0900.68286
[3] , Transductions and Context-Free Languages, Leitfäden der angewandten Mathematik und Mechanik 38 (1979). | MR 549481 | Zbl 0424.68040
[4] , and , Membership problems for regular and context-free trace languages. Inform. Comput. 82 (1989) 135-150. | MR 1010929 | Zbl 0682.68040
[5] , and , Input reversals and iterated pushdown automata: a new characterization of Khabbaz geometric hierarchy of languages, in Proc. of DLT 2004, edited by C.S. Calude, E. Calude and M.J. Dinneen. Lect. Notes Comput. Sci. 3340 (2004) 102-113. | MR 2152136 | Zbl 1117.68394
[6] and , Problèmes Combinatoires de Commutation et Réarrangements. Lect. Notes Comput. Sci. 85 (1969). | Zbl 0186.30101
[7] , , and , Grammar Systems. A Grammatical Approach to Distribution and Cooperation, edited by Gordon and Breach. London (1994). | MR 1475215 | Zbl 0925.68286
[8] , and , Multiset automata, in Multiset Processing, edited by C.S. Calude, G. Păun, G. Rozenberg and A. Salomaa. Lect. Notes Comput. Sci. 2235 (2001) 69-83. | MR 2054254 | Zbl 1052.68071
[9] and Eds., The Book of Traces. World Scientific, Singapore (1995). | MR 1478992
[10] , , and , Optimal Zielonka-type construction of deterministic asynchronous automata, in Proc. of ICALP 2010, Part. II, edited by S. Abramsky, C. Gavoille, C. Kircher, F. Meyer auf der Heide and P.G. Spirakis. Lect. Notes Comput. Sci. 6199 (2010) 52-63. | MR 2734635 | Zbl 1288.68154
[11] , Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978). | MR 526397 | Zbl 0411.68058
[12] and , Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). | MR 645539 | Zbl 0980.68066
[13] , , and , Restarting automata, in Proc. of FCT 1995, edited by H. Reichel. Lect. Notes Comput. Sci. 965 (1995) 283-292. | MR 1459184
[14] , and , Simulation problems for one-counter machines, in Proc. of SOFSEM'99, edited by J. Pavelka, G. Tel and M. Bartošek. Lect. Notes Comput. Sci. 1725 (1999) 404-413. | MR 1784525 | Zbl 0963.68094
[15] , and , Multiset pushdown automata. Fund. Inform. 93 (2009) 221-233. | MR 2543950 | Zbl 1191.68392
[16] , and , On stateless two-pushdown automata and restarting automata, in Proc. of AFL 2008, edited by E. Csuhaj-Varjú and Z. Ésik. Hungarian Academy of Sciences (2008) 257-268. | Zbl 1207.68193
[17] , and , On stateless two-pushdown automata and restarting automata. Int. J. Found. Comput. Sci. 21 (2010) 781-798. | MR 2728324 | Zbl 1207.68193
[18] , Concurrent program schemes and their interpretations, DAIMI Rep. PB. Aarhus University, Aarhus 78 (1977).
[19] and , Cooperating distributed systems of restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 1333-1342. | MR 2363813 | Zbl 1183.68347
[20] and , On deterministic CD-systems of restarting automata. Int. J. Found. Comput. Sci. 20 (2009) 185-209. | MR 2494598 | Zbl 1170.68505
[21] and , CD-systems of stateless deterministic R(1)-automata accept all rational trace languages, in Proc. of LATA 2010, edited by A.H. Dediu, H. Fernau and C. Martin-Vide. Lect. Notes Comput. Sci. 6031 (2010) 463-474. | MR 2753932 | Zbl 1284.68363
[22] and , On CD-systems of stateless deterministic R-automata with window size one. Kasseler Informatikschriften, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2010). https://kobra.bibliothek.uni-kassel.de/handle/urn:nbn:de:hebis:34-2010042732682 | Zbl 1279.68167
[23] and , An automata-theoretical characterization of context-free trace languages, in Proc. of SOFSEM 2011: Theory and Practice of Computer Science, edited by I. Černá, T. Gyimóthy, J. Hromkovič, K. Jefferey, R. Královič, M. Vukolič and S. Wolf. Lect. Notes Comput. Sci. 6543 (2011) 406-417. | MR 2804139 | Zbl 1298.68152
[24] and , Finite-state acceptors with translucent letters, in Proc. of BILC 2011: AI Methods for Interdisciplinary Research in Language and Biology, edited by G. Bel-Enguix, V. Dahl and A.O. De La Puente. SciTePress, Portugal (2011) 3-13.
[25] , Restarting automata, in Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence, edited by Z. Ésik, C. Martin-Vide and V. Mitrana. 25 (2006) 269-303. | Zbl 1116.68044
[26] , Note on finite asynchronous automata. RAIRO-Inf. Theor. Appl. 21 (1987) 99-135. | Numdam | MR 894706 | Zbl 0623.68055