On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
From MaRDI portal
Publication:3532998
Recommendations
- Minimal NFA Problems are Hard
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- scientific article; zbMATH DE number 176769
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
Cites work
- A comparison of two lower-bound methods for communication complexity
- A geometrical view of the determinization and minimization of finite-state automata
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- A lower bound technique for the size of nondeterministic finite automata
- Communication Complexity
- Communication complexity method for measuring nondeterminism in finite automata
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Descriptional Complexity of Nondeterministic Finite Automata
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Finite automata and unary languages
- scientific article; zbMATH DE number 4026854 (Why is no real title available?)
- scientific article; zbMATH DE number 58314 (Why is no real title available?)
- scientific article; zbMATH DE number 193480 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 1948494 (Why is no real title available?)
- scientific article; zbMATH DE number 2068869 (Why is no real title available?)
- scientific article; zbMATH DE number 1361468 (Why is no real title available?)
- scientific article; zbMATH DE number 2083798 (Why is no real title available?)
- scientific article; zbMATH DE number 1857650 (Why is no real title available?)
- scientific article; zbMATH DE number 918133 (Why is no real title available?)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Mathematical Foundations of Computer Science 2003
- Minimal NFA Problems are Hard
- Minimizing nfa's and regular expressions
- Natural proofs
- Number-theoretic constructions of efficient pseudo-random functions
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Prediction-preserving reducibility
- Regular Expressions and NFAs Without ε-Transitions
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
Cited in
(19)- Mergible states in large NFA
- Weighted automata are compact and actively learnable
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Language operations with regular expressions of polynomial size
- Minimizing nfa's and regular expressions
- Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata
- A Nontrivial Lower Bound for an NP Problem on Automata
- The Tractability Frontier for NFA Minimization
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- scientific article; zbMATH DE number 176769 (Why is no real title available?)
- The tractability frontier for NFA minimization
- Minimal NFA Problems are Hard
- scientific article; zbMATH DE number 1929949 (Why is no real title available?)
- scientific article; zbMATH DE number 7377986 (Why is no real title available?)
- Descriptional and computational complexity of finite automata -- a survey
- Lower bound methods for the size of nondeterministic finite automata revisited
- Lower Bounds for the Transition Complexity of NFAs
- Lower bounds for the transition complexity of NFAs
This page was built for publication: On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532998)
