Iterated GSMs and CO-CFL

DOI10.1007/BF00289160zbMath0659.68097OpenAlexW2076121015MaRDI QIDQ1112624

Jean-Michel Autebert, Joaquim Gabarró

Publication date: 1989

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289160

zbMATH Keywords

context-free grammarsambiguity problemiterated generalized sequential machineKleene hierarchyundecidable problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Iterated sequential transducers as language generating devices ⋮ Properties of infinite words : Recent results ⋮ Iterative devices generating infinite words ⋮ Comparing descriptional and computational complexity of infinite words ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ Languages obtained from infinite words ⋮ On quasi orders of words and the confluence property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An infinite square-free co-CFL
• Every iterated morphism yields a co-CFL
• Applications of an infinite square-free co-CFL
• An infinite word language which is not co-CFL
• Prefixes of infinite words and ambiguous context-free languages
• Adherences of languages
• The Turing degree of the inherent ambiguity problem for context-free languages
• Substitution and bounded languages
• Sur les centres de DOL-langages
• Production en temps réel et complexité de structure de suites infinies

This page was built for publication: Iterated GSMs and CO-CFL