Transition complexity of incomplete DFAs

DOI10.3233/FI-2011-533MaRDI QIDQ3100931zbMATH OpenOpenAlexFDO

Authors Yuan Gao, Kai Salomaa, Sheng Yu

Publication date 22 November 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2011-533

zbMATH Keywords

Boolean operationsdeterministic finite automatonincomplete automatonregular languagestransition complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Transition complexity of incomplete DFAs
• Incomplete operational transition complexity of regular languages
• Incomplete transition complexity of some basic operations
• Incomplete transition complexity of basic operations on finite languages
• Lower Bounds for the Transition Complexity of NFAs

Cited in

(15)

• Operational complexity and right linear grammars
• Operational union-complexity
• Time window temporal logic
• Unrestricted state complexity of binary operations on regular languages
• State complexity of Kleene-star operations on trees
• Incomplete transition complexity of some basic operations
• State complexity of the concatenation of regular tree languages
• Transition complexity of incomplete DFAs
• Incomplete operational transition complexity of regular languages
• Operational accepting state complexity: the unary and finite case
• Incomplete transition complexity of basic operations on finite languages
• DFA with a Bounded Activity Level
• Lower Bounds for the Transition Complexity of NFAs
• Further Remarks on the Operational Nonterminal Complexity
• Lower bounds for the transition complexity of NFAs

This page was built for publication: Transition complexity of incomplete DFAs

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