×

zbMATH — the first resource for mathematics

Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata. (English) Zbl 1359.68177
Summary: Recently the one-counter trace languages and the context-free trace languages have been characterized through restricted types of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size one (so-called stl-det-R(1)-automata) that work in mode ‘=1’ and that use an external counter or pushdown store to determine the successor components within computations. Here we study the deterministic variants of these CD-systems, comparing the resulting language classes to the classes of languages defined by CD-systems of stl-det-R(1)-automata without such an external device and to some classical language families, among them in particular the classes of rational, one-counter, and context-free trace languages. In addition, we present a large number of (non-)closure properties for our language classes.
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, Theor. Comput. Sci., 60, 1-82, (1988) · Zbl 0652.68017
[2] Berstel, J.: Transductions and Context-Free Languages. Teubner, Stuttgart (1979) · Zbl 0424.68040
[3] Bertoni, A; Mauri, G; Sabadini, N, Membership problems for regular and context-free trace languages, Inform. Comput., 82, 135-150, (1989) · Zbl 0682.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, Proceedings. LNCS 3340, pp. 102-113. Springer, Berlin (2004) · Zbl 1117.68394
[5] Chottin, L.: Strict deterministic languages and controlled rewriting systems. In: Maurer, H. (ed.) ICALP 1979, Proceedings. LNCS 71, pp. 104-117. Springer, Berlin (1979) · Zbl 0438.68031
[6] Chottin, L, Langages algébriques et systèmes de réècriture rationnels, RAIRO Theor. Inform. Appl., 16, 1-20, (1982) · Zbl 0498.68048
[7] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Păun, G.: Grammar Systems—A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London (1994) · Zbl 0925.68286
[8] Culy, C, Formal properties of natural language and linguistic theories, Linguist. Philos., 19, 599-617, (1996)
[9] Dahlhaus, E; Warmuth, M, Membership for growing context-sensitive grammars is polynomial, J. Comput. Syst. Sci., 33, 456-472, (1986) · Zbl 0625.68055
[10] Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)
[11] Duske, J; Parchmann, R, Linear indexed languages, Theoret. Comput. Sci., 32, 47-60, (1984) · Zbl 0545.68067
[12] Harrison, M.: Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978) · Zbl 0411.68058
[13] Jančar, P., Moller, F., Sawa, Z.: Simulation problems for one-counter machines. In: Pavelka, J., Tel, G., Bartošek, M. (eds.) SOFSEM’99, Proceedings. LNCS 1725, pp. 404-413. Springer, Berlin (1999) · Zbl 0963.68094
[14] Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995, Proceedings. LNCS 965, pp. 283-292. Springer, Berlin (1995)
[15] Kutrib, M., Messerschmidt, H., Otto, F.: On stateless two-pushdown automata and restarting automata. In: Csuhaj-Varjú, E., Ésik, Z. (eds.) AFL 2008, Proceedings, pp. 257-268. Hungarian Academy of Sciences (2008) · Zbl 1207.68193
[16] Kutrib, M; Messerschmidt, H; Otto, F, On stateless two-pushdown automata and restarting automata, Int. J. Found. Comput. Sci., 21, 781-798, (2010) · Zbl 1207.68193
[17] Lopatková, M., Plátek, M., Kubon, V.: Modeling syntax of free word-order languages: dependency analysis by reduction. In: Matoušek, V., Mautner, P., Pavelka, T. (eds.) Text, Speech and Dialogue, Proceedings, LNAI 3658. pp. 140-147, Springer, Berlin (2005)
[18] Lopatková, M; Plátek, M; Sgall, P, Towards a formal model for functional generative description—analysis by reduction and restarting automata, Prague Bull. Math. Linguist., 87, 7-26, (2007)
[19] McNaughton, R; Narendran, P; Otto, F, Church-rosser thue systems and formal languages, J. ACM, 35, 324-344, (1988) · Zbl 0652.68093
[20] Messerschmidt, H; Otto, F, Cooperating distributed systems of restarting automata, Int. J. Found. Comput. Sci., 18, 1333-1342, (2007) · Zbl 1183.68347
[21] Messerschmidt, H; Otto, F, On deterministic CD-systems of restarting automata, Int. J. Found. Comput. Sci., 20, 185-209, (2009) · Zbl 1170.68505
[22] Nagy, B., Otto, F.: CD-systems of stateless deterministic R(1)-automata accept all rational trace languages. In: Dediu, A.H., Fernau, H., Martin-Vide, C. (eds.) LATA 2010, Proceedings. LNCS 6031, pp. 463-474. Springer, Berlin (2010) · Zbl 1284.68363
[23] Nagy, B., Otto, F.: An automata-theoretical characterization of context-free trace languages. In: Černá, I. et al. (eds.) SOFSEM 2011, Proceedings. LNCS 6543, pp. 406-417. Springer, Berlin (2011) · Zbl 1298.68152
[24] Nagy, B., Otto, F.: Finite-state acceptors with translucent letters. In: Bel-Enguix, G., Dahl, V., De La Puente, A.O. (eds.) BILC 2011, Proceedings, pp. 3-13. SciTePress, Portugal (2011) · Zbl 0682.68040
[25] Nagy, B., Otto, F.: Globally deterministic CD-systems of stateless R(1)-automata. In: Dediu, A., Inenaga, S., Martin-Vide, C. (eds.) LATA 2011, Proceedings. LNCS 6638, pp. 390-401. Springer, Berlin (2011) · Zbl 1330.68170
[26] Nagy, B., Otto, F.: Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata. In: Dömösi, P., Iván, S. (eds.) Automata and Formal Languages, AFL 2011, Proceedings, pp. 328-342. Institute of Mathematics and Informatics, College of Nyiregyháza (2011) · Zbl 1341.68103
[27] Nagy, B; Otto, F, CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store, RAIRO Theor. Inform. Appl., 45, 413-448, (2011) · Zbl 1250.68172
[28] Nagy, B; Otto, F, On CD-systems of stateless deterministic R-automata with window size one, J. Comput. Syst. Sci., 78, 780-806, (2012) · Zbl 1279.68167
[29] Niemann, G., Otto, F.: Further results on restarting automata. In: Ito, M., Imaoka, T. (eds.) Words, Languages and Combinatorics III, Proceedings, pp. 352-369. World Scientific, Singapore (2003) · Zbl 1250.68172
[30] Otto F.: Restarting automata. In: Ésik, Z., Martin-Vide, C., Mitrana, V. (eds.) Recent Advances in Formal Languages and Applications. Studies in Computational Intelligence, vol. 25, pp. 269-303. Springer, Berlin (2006) · Zbl 1279.68167
[31] Sénizergues, G, Church-rosser controlled rewriting systems and equivalence problems for deterministic context-free languages, Inform. Comput., 81, 265-279, (1989) · Zbl 0672.68040
[32] Sénizergues, G, Some decision problems about controlled rewriting systems, Theoret. Comput. Sci., 71, 281-346, (1990) · Zbl 0695.68056
[33] Sgall, P., Nebeský, L., Gorlčíková, A., Hajičová, E.: A Functional Approach to Syntax in Generative Description of Language. American Elsevier Publishing Company, New York (1969) · Zbl 0193.32004
[34] Taşdemir, N., Cem Say, A.C.: Models of pushdown automata with reset. In: Mauri, G., Leporati, A. (eds.) DLT 2011, Proceedings. LNCS 6795, pp. 417-428. Springer, Berlin (2011) · Zbl 1221.68149
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.