The pumping lemma for regular languages is hard

DOI10.1007/978-3-031-40247-0_9OpenAlexW4385711117MaRDI QIDQ6199869FDOQ6199869

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Which problems have strongly exponential complexity?
• Relationships between nondeterministic and deterministic tape complexities
• Inference of Reversible Languages
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Title not available (Why is that?)
• Title not available (Why is that?)
• Operational complexity and pumping lemmas
• On Jaffe's pumping lemma, revisited

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)