Prefix and equality languages of rational functions are co-context-free

DOI10.1016/0020-0190(88)90167-6zbMath0678.68066OpenAlexW1966523679MaRDI QIDQ1124356

Joost Engelfriet, Hendrik Jan Hoogeboom

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90167-6

zbMATH Keywords

prefix language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• An infinite square-free co-CFL
• Every iterated morphism yields a co-CFL
• What makes some language theory problems undecidable
• Two-way counter machines and finite-state transducers†
• Equality languages and fixed point languages
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• A note on finite-valued and finitely ambiguous transducers
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Prefix and equality languages of rational functions are co-context-free