The tractability frontier for NFA minimization
From MaRDI portal
Publication:414869
DOI10.1016/J.JCSS.2011.03.001zbMATH Open1282.68119OpenAlexW2157017998MaRDI QIDQ414869FDOQ414869
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
Recommendations
- The Tractability Frontier for NFA Minimization
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Minimal NFA Problems are Hard
- scientific article
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Implementation and Application of Automata
- MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON
- Implementation and Application of Automata
- Deterministic blow-ups of minimal NFA's
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Regular Expressions with Numerical Constraints and Automata with Counters
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Three Partition Refinement Algorithms
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Title not available (Why is that?)
- Minimal NFA Problems are Hard
- The Tractability Frontier for NFA Minimization
- Title not available (Why is that?)
- Descriptional complexity of machines with limited resources
- Regular Expressions with Counting: Weak versus Strong Determinism
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
- Minimizing nfa's and regular expressions
- Title not available (Why is that?)
- Hyper-minimisation Made Efficient
- 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
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Title not available (Why is that?)
- Descriptional Complexity of Nondeterministic Finite Automata
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Regular Expressions and NFAs Without ε-Transitions
- Implementation and Application of Automata
- Minimizing finite automata is computationally hard
- Succinctness of regular expressions with interleaving, intersection and counting
Cited In (20)
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Title not available (Why is that?)
- Unambiguous finite automata over a unary alphabet
- Title not available (Why is that?)
- Minimizing finite automata is computationally hard
- Minimisation of automata
- Compression of finite-state automata through failure transitions
- Nondeterministic Tree Width of Regular Languages
- The Tractability Frontier for NFA Minimization
- Title not available (Why is that?)
- Descriptional complexity of finite automata -- selected highlights
- A multi-parameter analysis of hard problems on deterministic finite automata
- Minimizing nfa's and regular expressions
- Determinizing monitors for HML with recursion
- A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
- On the complexity of determinizing monitors
- Title not available (Why is that?)
- Branching Measures and Nearly Acyclic NFAs
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Title not available (Why is that?)
This page was built for publication: The tractability frontier for NFA minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414869)
