Operational complexity: NFA-to-DFA trade-off

DOI10.1007/978-3-031-34326-1_6MaRDI QIDQ6175089zbMATH OpenOpenAlexFDO

Authors

Publication date 17 August 2023

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-34326-1_6

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Cuts in regular expressions
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1916664 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• New tools for state complexity
• NFA-to-DFA trade-off for regular operations
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On the state complexity of operations on two-way finite automata
• Operations on Self-Verifying Finite Automata
• Operations on Unambiguous Finite Automata
• Quotient complexity of regular languages
• Reversal of binary regular languages
• State complexity of combined operations
• Syntactic complexity of regular ideals
• The cut operation in subclasses of convex languages (extended abstract)
• The range of state complexities of languages resulting from the cut operation
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)
• Tight bounds for cut-operations on deterministic finite automata

Cited in

(1)

• Operational complexity: NFA-to-DFA trade-off

This page was built for publication: Operational complexity: NFA-to-DFA trade-off

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