×

Iterated GSMs and CO-CFL. (English) Zbl 0659.68097

We study the infinite words generated by an iterated generalized sequential machine (gsm). The motivation was twofold. The first one was given by the apparent similarity between the iterated gsm and the iterated morphism. However contrary to the appearences almost all questions become undecidable. The second one was to disprove the following conjecture of Berstel: The language of coprefixes of an infinite word w is context free iff w is generated by an iterated gsm. We use for that the infinite word: \[ w=abca^ 2ba^ 2bca^ 4ba^ 4ba^ 4ba^ 4bc...(a^{2^ n}b)^{2^ n}c...\quad. \] We prove also that the degree of the ambiguity problem for coprefixes of iterated gsm in \(\Pi_ 1\)-complete in the Kleene hierarchy. This result fills the gap between the degree of this problem for iterated morphisms which is \(\Pi_ 0\)- and for arbitrary context-free grammars which is \(\Pi_ 2\)- complete.
Reviewer: J.Gabarro

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Autebert, J.-M., Béauquier, J., Boasson, L., Nivat, M.: Quelques problemes ouverts en théorie des langages algébriques. RAIRO Inf. Theor. 13, 363-379 (1979)
[2] Autebert, J.-M., Beauquier, J., Boasson, L., Latteux, M.: Very small families of algebraic nonrational languages. In: Book, R.V. (ed.) Formal Language Theory, pp. 89-108. New York: Academic Press 1980
[3] Autebert, J.-M., Gabarró, J.: Compléments des facteurs gauches de mots infinis et ambiguité: quelques exemples. Facultat d’Informàtica de Barcelona, Report de Recerca RR85/15, 1985
[4] Autebert, J.-M., Flajolet, P., Gabarro, J.: Prefixes of infinite words and ambiguous context-free languages. Inf. Process. Lett. 25, 211-216 (1987) · Zbl 0653.68076 · doi:10.1016/0020-0190(87)90162-1
[5] Berstel, J.: Some recent results on squarefree words, in STACS’84. Lect. Notes Comput. Sci. 166, 14-25 (1984) · Zbl 0582.68042
[6] Berstel, J.: Complémentaires de mots infinis. Séminaire du vendredi du LITP, Paris, December 1986
[7] Berstel, J.: Every iterated morphism yields a Co-CFL, Inf. Process. Lett. 22, 7-9 (1986) · Zbl 0584.68082 · doi:10.1016/0020-0190(86)90034-7
[8] Blanc, G., Bleuzen-Guernalec, N.: Production en temps réel et complexité de structure de suites infinies. Theor. Inf. Appl. 23, 195-216 (1989) (To appear) · Zbl 0681.68055
[9] Boasson, L., Nivat, M.: Adherences of languages. J. Comput. Syst. Sci. 20, 285-309 (1980) · Zbl 0471.68052 · doi:10.1016/0022-0000(80)90010-0
[10] Eilenberg, S.: Automata, languages and machines, Vol. 1. New York: Academic Press 1987 · Zbl 0317.94045
[11] Goldstine, J.: Substitution and bounded languages. J. Comput. Syst. Sci. 67, 186-192 (1972) · Zbl 0232.68030
[12] Grazon, A.: An infinite word language which is not co-CFL. Inf. Process. Lett. 24, 81-85 (1987) · Zbl 0637.68091 · doi:10.1016/0020-0190(87)90098-6
[13] Kolakovski, W.: Self generating runs, problem 5304. Amer. Math. Monthly 72, 674 (1965). Solution of N. Ucoluk (same journal) 73, 681-682 (1966)
[14] Main, M.G.: An infinite square free Co-CFL. Inf. Process. Lett. 20, 105-107 (1985) · Zbl 0556.68041 · doi:10.1016/0020-0190(85)90073-0
[15] Main, M.G., Bucher, W., Haussler, D.: Applications of an infinite square free Co-CFL. Theor. Comput. Sci. 49, 113-119 (1987) · Zbl 0612.68070 · doi:10.1016/0304-3975(87)90003-X
[16] Minsky, M.: Computation, finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall 1967 · Zbl 0195.02402
[17] Pansiot J.-J.: On various classes of infinite words. In: Nivat, M., Perrin, D. (eds.) Automata on Infinite Words. Lect. Notes Comput. Sci. 192, 188-197 (1984)
[18] Pansiot, J.-J.: Decidability of periodicity for infinite words. Theor. Inf. Appl. 20, 434-446 (1986)
[19] Terlutte, A.: Sur le centre des langages DOL. Theor. Inf. Appl. 21, 137-145 (1987) · Zbl 0634.68071
[20] Reedy, A., Savitch, W.J.: The Turing degree of inherent ambiguity problem for context-free languages. Theor Comput. Sci. 1, 77-91 (1975) · Zbl 0313.68064 · doi:10.1016/0304-3975(75)90013-4
[21] Rogers, H.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967 · Zbl 0183.01401
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.