Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
From MaRDI portal
Publication:3602795
DOI10.1007/978-3-540-70844-5_1zbMATH Open1172.68511OpenAlexW1843639509MaRDI QIDQ3602795FDOQ3602795
Authors: Markus Holzer, Martin Kutrib 
Publication date: 12 February 2009
Published in: Implementation and Applications of Automata (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70844-5_1
Recommendations
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Descriptional and Computational Complexity of Finite Automata
- Descriptional and computational complexity of finite automata -- a survey
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- scientific article; zbMATH DE number 1962776
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The state complexities of some basic operations on regular languages
- State complexity of regular languages
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the state complexity of reversals of regular languages
- Title not available (Why is that?)
- Minimal NFA Problems are Hard
- The Tractability Frontier for NFA Minimization
- Finite automata and unary languages
- Descriptional complexity of machines with limited resources
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- A lower bound technique for the size of nondeterministic finite automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Magic numbers in the state hierarchy of finite automata
- Title not available (Why is that?)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- State complexity of power
- State complexity of some operations on binary regular languages
- State-complexity of finite-state devices, state compressibility and incompressibility
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- On the State Minimization of Nondeterministic Finite Automata
- Lower bounds on the size of sweeping automata
- Intersection and union of regular languages and state complexity
- Communication complexity method for measuring nondeterminism in finite automata
- Optimal simulations between unary automata
- 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?)
- Nondeterminism and the size of two way finite automata
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- State Complexity of Union and Intersection of Finite Languages
- Regular Expressions and NFAs Without ε-Transitions
- Partial orders on words, minimal elements of regular languages, and state complexity
- Minimizing finite automata is computationally hard
- Succinct representation of regular languages by Boolean automata
- A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
- Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
- Complementing unary nondeterministic automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2005
- Title not available (Why is that?)
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Transition complexity of language operations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2003
- STACS 2005
- Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- On the average state and transition complexity of finite languages
- Title not available (Why is that?)
- Lower Bounds for the Transition Complexity of NFAs
- Title not available (Why is that?)
- State complexity of cyclic shift
- Title not available (Why is that?)
- On Transition Minimality of Bideterministic Automata
Cited In (21)
- Title not available (Why is that?)
- State complexity of binary coded regular languages
- Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
- The tractability frontier for NFA minimization
- Run-Length Encoded Nondeterministic KMP and Suffix Automata
- Nonterminal complexity of one-sided random context grammars
- Descriptional and Computational Complexity of Finite Automata
- Title not available (Why is that?)
- Operational state complexity of nested word automata
- Descriptional complexity of input-driven pushdown automata
- Title not available (Why is that?)
- Limitations of lower bound methods for deterministic nested word automata
- THE LENGTH OF SUBSET REACHABILITY IN NONDETERMINISTIC AUTOMATA
- Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata
- Descriptional and computational complexity of finite automata -- a survey
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Finitely nonstationary nondeterministic automata with random input
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- On NFAs where all states are final, initial, or both
- VC-dimensions of nondeterministic finite automata for words of equal length
- Title not available (Why is that?)
This page was built for publication: Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602795)
