Transition Complexity of Incomplete DFAs

DOI10.3233/FI-2011-533zbMath1230.68130OpenAlexW1572529124MaRDI QIDQ3100931

Kai Salomaa, Yuan Gao, 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 operationsregular languagesdeterministic finite automatontransition complexityincomplete automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

State Complexity of Kleene-Star Operations on Trees ⋮ Time window temporal logic ⋮ Further Remarks on the Operational Nonterminal Complexity ⋮ State complexity of the concatenation of regular tree languages ⋮ Incomplete operational transition complexity of regular languages ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ Operational complexity and right linear grammars ⋮ Unrestricted State Complexity of Binary Operations on Regular Languages ⋮ Operational union-complexity