Prefixes of infinite words and ambiguous context-free languages

DOI10.1016/0020-0190(87)90162-1zbMath0653.68076OpenAlexW2034926538MaRDI QIDQ1108044

Philippe Flajolet, Jean-Michel Autebert, Joaquim Gabarró

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00076062/file/RR-0492.pdf

zbMATH Keywords

context-free grammarsambiguityinfinite wordgap theorems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Asymptotic approximation by regular languages, Iterated GSMs and CO-CFL, Properties of infinite words : Recent results, Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages1 1Work supported by the Grants-in Aid for Scientific Research No. 1 0440034, Japan Society for the Promotion of Sciences and the Dirección General de Enseñanza Superior e Investigación Cientifica, SB 97-00110508, Formulae and Asymptotics for Coefficients of Algebraic Functions, A decision method for Parikh slenderness of context-free languages, Languages obtained from infinite words, On Parikh slender context-free languages, On quasi orders of words and the confluence property, A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES, Non recursive functions have transcendental generating series, Transcendence of formal power series with rational coefficients

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic counting algorithms for data base applications
• Every iterated morphism yields a co-CFL
• Analytic models and ambiguity of context-free languages
• Folds! III: More morphisms
• Algebraic functions over finite fields
• Dirichlet Series and Curious infinite Products
• On the periodicity of morphisms on free monoids
• Decidability of periodicity for infinite words