Operational accepting state complexity: the unary and finite case

DOI10.1142/S0129054119400240MaRDI QIDQ5205038zbMATH OpenOpenAlexWikidataFDO

Authors Jürgen Dassow

Publication date 10 December 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054119400240

zbMATH Keywords

finite languagesunary languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The ranges of accepting state complexities of languages resulting from some operations
• The ranges of accepting state complexities of languages resulting from some operations
• scientific article; zbMATH DE number 1948495
• The state complexities of some basic operations on regular languages
• State complexity of unambiguous operations on finite automata

Cites work

• A survey on operational state complexity
• Descriptional complexity of union and star on context-free languages
• DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Incomplete operational transition complexity of regular languages
• Magic numbers and ternary alphabet
• Model Checking Software
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Nonterminal complexity of some operations on context-free languages
• On the descriptional complexity of operations on semilinear sets
• On the descriptional complexity of Watson-Crick automata
• On the number of accepting states of finite automata
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• Operational State Complexity under Parikh Equivalence
• Quotient complexity of regular languages
• State complexity of operations on input-driven pushdown automata
• State complexity of regular languages
• State complexity of the concatenation of regular tree languages
• Tight bounds for cut-operations on deterministic finite automata
• Transition complexity of incomplete DFAs

Cited in

(4)

• The ranges of accepting state complexities of languages resulting from some operations
• On the number of accepting states of finite automata
• Operational State Complexity under Parikh Equivalence
• The ranges of accepting state complexities of languages resulting from some operations

This page was built for publication: Operational accepting state complexity: the unary and finite case

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