×

zbMATH — the first resource for mathematics

An automata-theoretical characterization of context-free trace languages. (English) Zbl 1298.68152
Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 406-417 (2011).
Summary: We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store.
For the entire collection see [Zbl 1205.68007].
Reviewer: Reviewer (Berlin)

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aalbersberg, I., Rozenberg, G.: Theory of traces. Theoretical Computer Science 60, 1–82 (1988) · Zbl 0652.68017 · doi:10.1016/0304-3975(88)90051-5
[2] Autebert, J., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Word, Language, Grammar, vol. 1, pp. 111–174. Springer, Berlin (1997) · doi:10.1007/978-3-642-59136-5_3
[3] Berstel, J.: Transductions and Context-Free Languages. In: Teubner Studienbücher: Informatik, Teubner, Stuttgart (1979) · Zbl 0424.68040
[4] Bordihn, H., Holzer, M., Kutrib, M.: Input reversals and iterated pushdown automata: a new characterization of Khabbaz geometric hierarchy of languages. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 102–113. Springer, Heidelberg (2004) · Zbl 1117.68394 · doi:10.1007/978-3-540-30550-7_9
[5] Bertoni, A., Mauri, G., Sabadini, N.: Membership problems for regular and context-free trace languages. Information and Computation 82, 135–150 (1989) · Zbl 0682.68040 · doi:10.1016/0890-5401(89)90051-5
[6] Diekert, V., Rozenberg, G.: The Book of Traces. World Scientific, Singapore (1995) · doi:10.1142/2563
[7] Jančar, P., Moller, F., Sawa, Z.: Simulation problems for one-counter machines. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol. 1725, pp. 404–413. Springer, Heidelberg (1999) · Zbl 0963.68094 · doi:10.1007/3-540-47849-3_28
[8] Kutrib, M., Messerschmidt, H., Otto, F.: On stateless two-pushdown automata and restarting automata. In: Csuhaj-Varjú, E., Ésik, Z. (eds.) Proc. of Automata and Formal Languages, AFL 2008, pp. 257–268. Computer and Automation Research Institute, Hungarian Academy of Sciences (2008) · Zbl 1207.68193
[9] Messerschmidt, H., Otto, F.: Cooperating distributed systems of restarting automata. Intern. J. Found. Comput. Sci. 18, 1333–1342 (2007) · Zbl 1183.68347 · doi:10.1142/S0129054107005376
[10] Nagy, B., Otto, F.: CD-systems of stateless deterministic R(1)-automata accept all rational trace languages. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 463–474. Springer, Heidelberg (2010) · Zbl 1284.68363 · doi:10.1007/978-3-642-13089-2_39
[11] Nagy, B., Otto, F.: On CD-systems of stateless deterministic R-automata with window size one. Kasseler Informatikschriften, Fachbereich Elektrotechnik/Informatik, Universität Kassel handle/urn:nbn:de:hebis:34-2010042732682 (February 2010), https://kobra.bibliothek.uni-kassel.de/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.