×
Autebert, Jean-Michel; Flajolet, Philippe; Gabarro, Joaquim

Prefixes of infinite words and ambiguous context-free languages. (English) Zbl 0653.68076

Inf. Process. Lett. 25, 211-216 (1987).
Summary: Two ‘gap’ theorems are shown for languages formed with words that fail to be prefixes of an infinite word: such languages can never be described by unambigous context-free grammars.

Cited in 12 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

gap theorems; ambiguity; infinite word; context-free grammars
PDF BibTeX XML Cite
\textit{J.-M. Autebert} et al., Inf. Process. Lett. 25, 211--216 (1987; Zbl 0653.68076)
Full Text: DOI Link

References:

[1] Allouche, J.-P.; Cohen, H., Dirichlet series and curious infinite products, Bull. Lond. Math. Soc., 17, 531-538 (1985) · Zbl 0577.10036
[2] Autebert, J.-M.; Beauquier, J.; Boasson, L.; Latteux, M., Very small families of algebraic non-rational languages, (Book, R. V., Formal Language Theory (1980), Academic Press: Academic Press New York), 89-108
[3] Autebert, J.-M.; Gabarro, J., Compléments des facteurs gauches de mots infinis et ambiguité: Quelques examples, (Rept. de Recerca RR85/15 (1985), Faculdad d’Informatica de Barcelona)
[4] Berstel, J., Sur les mots sans carrés définis par morphismes, (Proc. ICALP’79. Proc. ICALP’79, Lecture Notes in Computer Science, Vol. 71 (1979), Springer: Springer Berlin), 16-22
[5] Berstel, J., Every iterated morphism yields a co-CFL, Inform. Process. Lett., 22, 1, 7-9 (1986) · Zbl 0584.68082
[6] Carlson, F., Über Potenzreihen mit ganzzahligen Koeffizienten, Math. Zeitschrift, 9, 1-13 (1921) · JFM 48.1208.02
[7] Chomsky, N.; Schutzenberger, M.-P., The algebraic theory of context-free languages, (Braffort, P.; Hirschberg, D., Computer Programming and Formal Systems (1963), North-Holland: North-Holland Amsterdam), 118-161 · Zbl 0148.00804
[8] Dekking, M.; Mendes France, M.; Van der Porten, A., Folds!, Mathematical Intelligencer, 4, 190-195 (1982) · Zbl 0493.10003
[9] Flajolet, P., Ambiguity and transcendence, (Proc. ICALP’85. Proc. ICALP’85, Lecture Notes in Computer Science, Vol. 194 (1985), Springer: Springer Berlin), 179-188
[10] Flajolet, P., Theoret. Comput. Sci., 49, 2, 3 (1987), to appear · Zbl 0612.68069
[11] Flajolet, P.; Martin, N., Probabilistic counting algorithms and data base applications, J. Comput. System Sci., 31, 182-209 (1985) · Zbl 0583.68059
[12] Furstenberg, H., Algebraic functions over finite fields, J. Algebra, 7, 271-277 (1967) · Zbl 0175.03903
[13] Grazon, A., Contribution à l’étude des petites familles de langages, (Ph.D. Thesis, 7 (1985), Univ. of Paris)
[14] Harju, T.; Linna, M., On the periodicity of morphisms in free monoids, Theoret. Inform. & Appl., 20, 47-54 (1986) · Zbl 0608.68065
[15] Lothaire, M., Combinatorics on words, (Encyclopaedia of Mathematics and Its Applications, Vol. 17 (1983), Addison-Wesley: Addison-Wesley Reading, MA), (collective pseudonym) · Zbl 1001.68093
[16] Pansiot, J.-J., Decidability of periodicity for infinite words, Theoret. Inform. & Appl., 20, 43-46 (1986) · Zbl 0617.68063
[17] Polya, G., (Boas, R.-P., Siggularities of Analytic Functions. Siggularities of Analytic Functions, Collected Papers, Vol. 1 (1974), MIT Press: MIT Press Cambridge, MA)
[18] Salomaa, A.; Soittola, M., Automata Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin/New York · Zbl 0377.68039
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.