×

Languages obtained from infinite words. (English) Zbl 0903.68115

It is decidable whether a language is the set of all finite factors (subwords) of some infinite word? If the language is context-free, the answer is no [S. Marcus and G. Păun, Bull. EATCS 54, 224-231 (1994; Zbl 0825.68388)]. In the paper under review, the authors give a positive answer to this question for a regular language (and the infinite word can be either taken as one-sided or two-sided). Note that the abstract in French contains a misprint (“décidable” has been replaced by “indécidable”).

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words

Citations:

Zbl 0825.68388
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] J.-M. AUTEBERT and J. GABARRO, Iterated GSM’s and Co-CFL, Acta Informatica, 1989, 26, pp. 749-769. Zbl0659.68097 MR1021789 · Zbl 0659.68097 · doi:10.1007/BF00289160
[2] J.-M. AUTEBERT, P. FLAJOLET and J. GABARRO, Prefixes of infinite words and ambiguous context-free languages, Inf. Process. Lett, 1987, 25, pp. 211-216. Zbl0653.68076 MR896136 · Zbl 0653.68076 · doi:10.1016/0020-0190(87)90162-1
[3] D. BEAUQUIER, Thin homogeneous sets of factors, Proc. of the 6th Conference of Foundations of Software Technology and Theoret. Comput. Sci., Lecture Notes in Computer Science 241, 1986, pp. 239-251. Zbl0624.68067 MR889923 · Zbl 0624.68067
[4] D. BEAUQUIER, Minimal automaton of a rational cover, Proc. ICALP’87, Lecture Notes in Computer Science 267, 1987, pp. 174-189. Zbl0635.68088 MR912707 · Zbl 0635.68088
[5] D. BEAUQUIER and M. NIVAT, About rational sets of factors of a bi-infinite word, Proc. ICALP’85, Lecture Notes in Computer Science 194, 1985, pp. 33-42. Zbl0571.68066 MR819238 · Zbl 0571.68066
[6] J. BERSTEL, Every iterated morphism yields a Co-CFL, Inf. Process. Lett., 1986, 22, pp. 7-9. Zbl0584.68082 MR825639 · Zbl 0584.68082 · doi:10.1016/0020-0190(86)90034-7
[7] L. BOASSON and M. NIVAT, Adherence of languages, J. Comput. Syst. Sci., 1980, 20, pp. 285-309. Zbl0471.68052 MR584863 · Zbl 0471.68052 · doi:10.1016/0022-0000(80)90010-0
[8] S. EILENBERG, Automata, Languages and Machines, Vol. 1, Academic Press, New York, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[9] J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[10] M. LOTHAIRE, Combinatorics on Words, Addison-Wesley, Reading, Mass., 1983. Zbl0514.20045 MR675953 · Zbl 0514.20045
[11] S. MARCUS and Gh. PĂUN, Infinite (almost periodic) words, formal languages and dynamical systems, The Bulletin of the EATCS, 1994, 54, pp. 224-231. Zbl0825.68388 · Zbl 0825.68388
[12] S. MARCUS and Gh. PĂUN, Infinite words and their associated formal language, in: C. Calude, M. J. J. Lennon, H. Maurer (eds.), Salodays in Auckland (Auckland Univ. Press, 1994), pp. 95-99. Zbl0927.68050 · Zbl 0927.68050
[13] A. SALOMAA, Formal Languages, Academic Press, New York, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
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.