Tight bounds for cut-operations on deterministic finite automata

DOI10.3233/FI-2017-1577zbMATH Open1393.68091MaRDI QIDQ4601149FDOQ4601149

Authors: Markus Holzer, Sebastian Jakobi, Brink van der Merwe, Frank Drewes 

Publication date: 19 January 2018

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Recommendations

• Tight bounds for cut-operations on deterministic finite automata
• The range of state complexities of languages resulting from the cut operation
• The state complexities of some basic operations on regular languages
• State complexity of unambiguous operations on finite automata
• scientific article; zbMATH DE number 2081044

zbMATH Keywords

regular languagedescriptional complexityfinite automatacut operationiterated cut

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (4)

• Operational accepting state complexity: the unary and finite case
• Operational complexity: NFA-to-DFA trade-off
• Tight bounds for cut-operations on deterministic finite automata
• Operations on Permutation Automata

This page was built for publication: Tight bounds for cut-operations on deterministic finite automata

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