Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
From MaRDI portal
Publication:3602795
DOI10.1007/978-3-540-70844-5_1zbMath1172.68511OpenAlexW1843639509MaRDI QIDQ3602795
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
Related Items (7)
Descriptional Complexity of Input-Driven Pushdown Automata ⋮ The tractability frontier for NFA minimization ⋮ Nonterminal complexity of one-sided random context grammars ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ State complexity of binary coded regular languages ⋮ Operational state complexity of nested word automata ⋮ Descriptional and Computational Complexity of Finite Automata
Cites Work
- On the state complexity of reversals of regular languages
- A lower bound technique for the size of nondeterministic finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Minimizing finite automata is computationally hard
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- State complexity of power
- Finite automata and unary languages
- Lower bounds on the size of sweeping automata
- Succinct representation of regular languages by Boolean automata
- Intersection and union of regular languages and state complexity
- The state complexities of some basic operations on regular languages
- 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
- State complexity of some operations on binary regular languages
- Complementing unary nondeterministic automata
- Communication complexity method for measuring nondeterminism in finite automata
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Magic numbers in the state hierarchy of finite automata
- Transition complexity of language operations
- On the average state and transition complexity of finite languages
- Optimal Simulations between Unary Automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- State complexity of cyclic shift
- The Tractability Frontier for NFA Minimization
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Minimal NFA Problems are Hard
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- State-complexity of finite-state devices, state compressibility and incompressibility
- 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
- Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet
- On Transition Minimality of Bideterministic Automata
- Mathematical Foundations of Computer Science 2003
- Regular Expressions and NFAs Without ε-Transitions
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Mathematical Foundations of Computer Science 2005
- On the State Minimization of Nondeterministic Finite Automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- STACS 2005
- Lower Bounds for the Transition Complexity of NFAs
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
