The pumping lemma for regular languages is hard

DOI10.1007/978-3-031-40247-0_9MaRDI QIDQ6199869zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer, Christian Rauch

Publication date 28 February 2024

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-40247-0_9

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3557270 (Why is no real title available?)
• scientific article; zbMATH DE number 3617584 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• Inference of Reversible Languages
• On Jaffe's pumping lemma, revisited
• Operational complexity and pumping lemmas
• Relationships between nondeterministic and deterministic tape complexities
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Which problems have strongly exponential complexity?

Cited in

(1)

• On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)

This page was built for publication: The pumping lemma for regular languages is hard

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