A pumping lemma for regular closure of prefix-free languages

DOI10.1016/J.IC.2022.104976OpenAlexW4307046643WikidataQ124849286 ScholiaQ124849286MaRDI QIDQ2105458

Toshihiro Koga

Publication date: 8 December 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104976

zbMATH Keywords

formal languagespumping lemmadeterministic context-free languagesprefix-free languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Context-dependent nondeterminism for pushdown automata
• A pumping lemma for deterministic context-free languages
• A structural lemma for deterministic context-free languages
• Applications of transducers in independent languages, word distances, codes
• Kleene Closure on Regular and Prefix-Free Languages
• Regular Closure of Deterministic Languages
• Kolmogorov Complexity and Deterministic Context-Free Languages
• A New Approach to Formal Language Theory by Kolmogorov Complexity
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

This page was built for publication: A pumping lemma for regular closure of prefix-free languages