Tight bounds for cut-operations on deterministic finite automata

DOI10.3233/FI-2017-1577MaRDI QIDQ4601149zbMATH OpenFDO

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)

zbMATH Keywords

regular languagedescriptional complexityfinite automatacut operationiterated cut

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cited in

(4)

• Operational accepting state complexity: the unary and finite case
• Tight bounds for cut-operations on deterministic finite automata
• Operational complexity: NFA-to-DFA trade-off
• 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)