Pumping lemmas can be ``harmful

DOI10.1007/S00224-024-10169-9MaRDI QIDQ6635700zbMATH OpenFDO

Authors Jingnan Xie, Harry B. Hunt III, R. E. Stearns

Publication date 12 November 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-024-10169-9

zbMATH Keywords

EDT0Lextended regular expressionsproductivenesspumping lemmassynchronized regular expressionsundecidability

Mathematics Subject Classification ID

Special aspects of infinite or finite groups (20Fxx) Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Complexity of some problems concerningL systems
• Computational Parallels between the Regular and Context-Free Languages
• EDT0L solutions to equations in group extensions
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 7407779 (Why is no real title available?)
• Language and automata theory and applications. Third international conference, LATA 2009, Tarragona, Spain, April 2--8, 2009. Proceedings
• Lattice-valued tree pushdown automata: pumping lemma and closure properties
• On the equivalence, containment, and covering problems for the regular and context-free languages
• On the intersection of regex languages with regular languages
• On the undecidability and descriptional complexity of synchronized regular expressions
• Pumping lemmas for classes of languages generated by folding systems
• Synchronized regular expressions
• Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups

Cited in

(3)

• Decision problems concerning L systems
• On the computational and descriptional complexity of multi-pattern languages
• A practical extension of computational complexity theory for applications in mathematics and sciences

This page was built for publication: Pumping lemmas can be ``harmful

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