The tractability frontier for NFA minimization
From MaRDI portal
Publication:414869
DOI10.1016/j.jcss.2011.03.001zbMath1282.68119OpenAlexW2157017998MaRDI QIDQ414869
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.03.001
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Compression of finite-state automata through failure transitions ⋮ Unnamed Item ⋮ On the complexity of determinizing monitors ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Unambiguous finite automata over a unary alphabet ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ Determinizing monitors for HML with recursion ⋮ Minimisation of automata ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimizing finite automata is computationally hard
- Succinctness of regular expressions with interleaving, intersection and counting
- An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Minimizing nfa's and regular expressions
- Hyper-minimisation Made Efficient
- Regular Expressions with Numerical Constraints and Automata with Counters
- The Tractability Frontier for NFA Minimization
- Hyper-minimizing minimized deterministic finite state automata
- Unambiguous Finite Automata over a Unary Alphabet
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Three Partition Refinement Algorithms
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Minimal NFA Problems are Hard
- Descriptional Complexity of Nondeterministic Finite Automata
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Regular Expressions and NFAs Without ε-Transitions
- Regular Expressions with Counting: Weak versus Strong Determinism
- Implementation and Application of Automata
This page was built for publication: The tractability frontier for NFA minimization
