The tractability frontier for NFA minimization

DOI10.1016/J.JCSS.2011.03.001MaRDI QIDQ414869zbMATH OpenOpenAlexFDO

Authors Henrik Björklund, Wim Martens

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

zbMATH Keywords

complexityfinite automataoptimizationstate minimization

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

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; zbMATH DE number 176769
• 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

Cites work

• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Comparing the size of NFAs with and without \(\epsilon\)-transitions
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Descriptional complexity of machines with limited resources
• Descriptional Complexity of Nondeterministic Finite Automata
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• scientific article; zbMATH DE number 1670824 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• Hyper-minimisation Made Efficient
• Hyper-minimizing minimized deterministic finite state automata
• Implementation and Application of Automata
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Minimal NFA Problems are Hard
• Minimizing finite automata is computationally hard
• Minimizing nfa's and regular expressions
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Regular Expressions and NFAs Without ε-Transitions
• Regular Expressions with Counting: Weak versus Strong Determinism
• Regular Expressions with Numerical Constraints and Automata with Counters
• Succinctness of regular expressions with interleaving, intersection and counting
• Succinctness of the complement and intersection of regular expressions
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• The Tractability Frontier for NFA Minimization
• Three Partition Refinement Algorithms
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Unambiguous finite automata over a unary alphabet

Cited in

(19)

• Minimisation of automata
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• A multi-parameter analysis of hard problems on deterministic finite automata
• Determinizing monitors for HML with recursion
• On the complexity of determinizing monitors
• Minimizing nfa's and regular expressions
• Compression of finite-state automata through failure transitions
• The Tractability Frontier for NFA Minimization
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• scientific article; zbMATH DE number 176769 (Why is no real title available?)
• Unambiguous finite automata over a unary alphabet
• scientific article; zbMATH DE number 2040906 (Why is no real title available?)
• scientific article; zbMATH DE number 1927179 (Why is no real title available?)
• scientific article; zbMATH DE number 1929949 (Why is no real title available?)
• Branching measures and nearly acyclic NFAs
• Minimization of visibly pushdown automata is NP-complete
• Nondeterministic tree width of regular languages
• Descriptional complexity of finite automata -- selected highlights
• Minimizing finite automata is computationally hard

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)