Operational complexity and pumping lemmas

DOI10.1007/S00236-022-00431-3MaRDI QIDQ2170280zbMATH OpenOpenAlexWikidataFDO

Authors Ismaël Jecker, Jürgen Dassow

Publication date 30 August 2022

Published in Acta Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the computational complexity of finite operations
• scientific article; zbMATH DE number 5901113
• Further Remarks on the Operational Nonterminal Complexity
• Logical operations and Kolmogorov complexity
• On computability and learnability of the pumping lemma function
• Complexity theory for operators in analysis
• Complexity theory for operators in analysis
• Algorithms and Computation
• scientific article; zbMATH DE number 2090609
• scientific article; zbMATH DE number 7650250

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 1962776 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A survey on operational state complexity
• Further Remarks on the Operational Nonterminal Complexity
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On the number of accepting states of finite automata
• Operational complexity and right linear grammars
• State complexity of cyclic shift
• The ranges of accepting state complexities of languages resulting from some operations
• The ranges of state complexities for complement, star, and reversal of regular languages
• The state complexities of some basic operations on regular languages

Cited in

(5)

• scientific article; zbMATH DE number 5901113 (Why is no real title available?)
• On Minimal Pumping Constants for Regular Languages
• On Jaffe's pumping lemma, revisited
• The pumping lemma for regular languages is hard
• On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)

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

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