Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
From MaRDI portal
Publication:3602795
DOI10.1007/978-3-540-70844-5_1zbMath1172.68511MaRDI 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
68Q45: Formal languages and automata
Related Items
The tractability frontier for NFA minimization, Limitations of lower bound methods for deterministic nested word automata, Operational state complexity of nested word automata, Nonterminal complexity of one-sided random context grammars, Descriptional Complexity of Input-Driven Pushdown Automata, Descriptional and Computational Complexity of Finite Automata
Cites Work
- 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
- 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
