NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
From MaRDI portal
Publication:3395129
DOI10.1142/S0129054109006747zbMATH Open1176.68106OpenAlexW2088578754WikidataQ57380806 ScholiaQ57380806MaRDI QIDQ3395129FDOQ3395129
Authors: Markus Holzer, Martin Kutrib 
Publication date: 21 August 2009
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054109006747
Recommendations
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Descriptional Complexity of Nondeterministic Finite Automata
- scientific article; zbMATH DE number 3972192
- Descriptional and computational complexity of finite automata -- a survey
- Descriptional and Computational Complexity of Finite Automata
- On an expansion of nondeterministic finite automata
- On finite automata with limited nondeterminism (extended abstract)
- Finite nondeterministic automata: simulation and minimality
- scientific article; zbMATH DE number 2068876
- Non-deterministic finite cover automata
Cites Work
- Title not available (Why is that?)
- The state complexities of some basic operations on regular languages
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- On the state complexity of reversals of regular languages
- Minimal NFA Problems are Hard
- Finite automata and unary languages
- 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
- 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
- Optimal simulations between unary automata
- 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
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Transition complexity of language operations
- 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
- State complexity of cyclic shift
Cited In (38)
- Cellular Automata: Descriptional Complexity and Decidability
- State complexity of projection on languages recognized by permutation automata and commuting letters
- State complexity of finite partial languages
- Title not available (Why is that?)
- Operational complexity and right linear grammars
- Unambiguous finite automata over a unary alphabet
- State complexity of permutation on finite languages over a binary alphabet
- Lower bounds for the size of deterministic unranked tree automata
- Extended nondeterministic finite automata
- Further Remarks on the Operational Nonterminal Complexity
- Nondeterministic state complexity of star-free languages
- Nondeterministic state complexity of star-free languages
- Run-Length Encoded Nondeterministic KMP and Suffix Automata
- Descriptional and Computational Complexity of Finite Automata
- State trade-offs in unranked tree automata
- Title not available (Why is that?)
- State complexity of finite partial languages
- On the number of active states in finite automata
- Operational state complexity of unary NFAs with finite nondeterminism
- Operational complexity and pumping lemmas
- NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS
- Complexity of exclusive nondeterministic finite automata
- Title not available (Why is that?)
- THE LENGTH OF SUBSET REACHABILITY IN NONDETERMINISTIC AUTOMATA
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata
- Descriptional and computational complexity of finite automata -- a survey
- Incomplete operational transition complexity of regular languages
- Finitely nonstationary nondeterministic automata with random input
- Operational Accepting State Complexity: The Unary and Finite Case
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- On NFAs where all states are final, initial, or both
- The magic number problem for subregular language families
- On an expansion of nondeterministic finite automata
- On Usefulness of Information: Framework and NFA Case
- State complexity of partial word finite automata
- 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 Q3395129)
