Operational complexity and pumping lemmas

DOI10.1007/s00236-022-00431-3OpenAlexW4285891680WikidataQ124842188 ScholiaQ124842188MaRDI QIDQ2170280

Ismaël Jecker, Juergen Dassow

Publication date: 30 August 2022

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-022-00431-3

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

On Jaffe's pumping lemma, revisited ⋮ The pumping lemma for regular languages is hard ⋮ On Minimal Pumping Constants for Regular Languages

Cites Work

• The state complexities of some basic operations on regular languages
• The ranges of accepting state complexities of languages resulting from some operations
• Operational complexity and right linear grammars
• On the Number of Accepting States of Finite Automata
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• State complexity of cyclic shift
• THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES
• Further Remarks on the Operational Nonterminal Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Operational complexity and pumping lemmas