Minimizing nfa's and regular expressions
We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as of regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's). We show that it is impossible to efficiently minimize a given nfa or regular expression with n states, transitions, respectively symbols within the factor \(o(n)\), unless P=PSPACE. For the unary case, we show that for any \(\delta>0\) it is impossible to efficiently construct an approximately minimal nfa or regular expression within the factor \(n^{1-\delta}\), unless P=NP. Our inapproximability results for a given dfa with n states are based on cryptographic assumptions and we show that any efficient algorithm will have an approximation factor of at least \(\frac{n}{poly(\log n)}\). Our setup also allows us to analyze the minimum consistent dfa problem.
- Cryptographic limitations on learning Boolean formulae and finite automata
- Follow automata.
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 2068873 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2003
- Minimal NFA Problems are Hard
- Natural proofs
- NFA reduction algorithms by means of regular inequalities
- Number-theoretic constructions of efficient pseudo-random functions
- Prediction-preserving reducibility
- STACS 2005
- The minimum consistent DFA problem cannot be approximated within any polynomial
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Theory Is Forever
- Aggregation-based minimization of finite state automata
- -automata
- Minimisation of automata
- Descriptional complexity of regular languages
- On minimizing regular expressions without Kleene star
- Minimal consistent DFA from sample strings
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Determinizing monitors for HML with recursion
- Hyper-optimization for deterministic tree automata
- More on deterministic and nondeterministic finite cover automata
- On the complexity of determinizing monitors
- On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
- More on deterministic and nondeterministic finite cover automata (extended abstract)
- On the Inference of Finite State Automata from Positive and Negative Data
- Büchi automata can have smaller quotients
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- The minimum consistent DFA problem cannot be approximated within any polynomial
- The tractability frontier for NFA minimization
- Minimized Thompson NFA
- Optimal regular expressions for permutations
- Fixing the state budget: approximation of regular languages with small DFAs
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Implementation and Application of Automata
- STACS 2005
- Minimization of finite state automata through partition aggregation
- Approximate NFA universality and related problems motivated by information theory
- Multi-entry DFA with reduced initial states to speedup parallel recognition
- From regular expressions to smaller NFAs
- Backward and forward bisimulation minimization of tree automata
- An approximation algorithm for state minimization in 2-MDFAs
- Lower bounds for the transition complexity of NFAs
This page was built for publication: Minimizing nfa's and regular expressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641868)
