Operational complexity: NFA-to-DFA trade-off

DOI10.1007/978-3-031-34326-1_6OpenAlexW4381855770MaRDI QIDQ6175089

No author found.

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal of binary regular languages
• On the state complexity of operations on two-way finite automata
• Syntactic complexity of regular ideals
• The state complexity of \(L^{2}\) and \(L^k\)
• The state complexities of some basic operations on regular languages
• The cut operation in subclasses of convex languages (extended abstract)
• NFA-to-DFA trade-off for regular operations
• The range of state complexities of languages resulting from the cut operation
• State complexity of combined operations
• Operations on Self-Verifying Finite Automata
• Tight Bounds for Cut-Operations on Deterministic Finite Automata*
• Operations on Unambiguous Finite Automata
• Cuts in Regular Expressions
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES

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