A pumping lemma for regular closure of prefix-free languages

DOI10.1016/J.IC.2022.104976MaRDI QIDQ2105458zbMATH OpenOpenAlexWikidataFDO

Authors 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

deterministic context-free languagesformal languagesprefix-free languagespumping lemma

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A pumping lemma for deterministic context-free languages
• A pumping lemma for real-time deterministic context-free languages
• Operational complexity and pumping lemmas
• Regular Closure of Deterministic Languages
• Kleene Closure on Regular and Prefix-Free Languages

Cites work

• A New Approach to Formal Language Theory by Kolmogorov Complexity
• 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
• Context-dependent nondeterminism for pushdown automata
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Kleene Closure on Regular and Prefix-Free Languages
• Kolmogorov Complexity and Deterministic Context-Free Languages
• Prefix-free languages, simple grammars representing a group element, languages of partial order in a group
• Regular Closure of Deterministic Languages
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

Cited in

(3)

• Non-regular Maximal Prefix-Free Subsets of Regular Languages
• Kleene Closure on Regular and Prefix-Free Languages
• scientific article; zbMATH DE number 1222097 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105458)