NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
From MaRDI portal
Publication:3395129
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
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
- 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
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Complementing unary nondeterministic automata
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Finite automata and unary languages
- Intersection and union of regular languages and state complexity
- Lower bounds on the size of sweeping automata
- Magic numbers in the state hierarchy of finite automata
- Minimal NFA Problems are Hard
- Minimizing finite automata is computationally hard
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- On the State Minimization of Nondeterministic Finite Automata
- On the average state and transition complexity of finite languages
- On the state complexity of reversals of regular languages
- Optimal simulations between unary automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- State complexity of cyclic shift
- State complexity of some operations on binary regular languages
- State-complexity of finite-state devices, state compressibility and incompressibility
- Succinct representation of regular languages by Boolean automata
- The state complexities of some basic operations on regular languages
- Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
- Transition complexity of language operations
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
Cited in
(38)- Descriptional and computational complexity of finite automata -- a survey
- State complexity of partial word finite automata
- scientific article; zbMATH DE number 3972192 (Why is no real title available?)
- Operational accepting state complexity: the unary and finite case
- State complexity of finite partial languages
- On the number of active states in finite automata
- On an expansion of nondeterministic finite automata
- State complexity of projection on languages recognized by permutation automata and commuting letters
- scientific article; zbMATH DE number 7444008 (Why is no real title available?)
- Unambiguous finite automata over a unary alphabet
- Cellular automata: descriptional complexity and decidability
- Descriptional and Computational Complexity of Finite Automata
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- State trade-offs in unranked tree automata
- Run-Length Encoded Nondeterministic KMP and Suffix Automata
- Operational complexity and right linear grammars
- Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata
- Nondeterministic state complexity of star-free languages
- On Usefulness of Information: Framework and NFA Case
- Extended nondeterministic finite automata
- State complexity of finite partial languages
- Nondeterministic state complexity of star-free languages
- Complexity of exclusive nondeterministic finite automata
- Operational state complexity of unary NFAs with finite nondeterminism
- Finitely nonstationary nondeterministic automata with random input
- Further Remarks on the Operational Nonterminal Complexity
- Lower bounds for the size of deterministic unranked tree automata
- The magic number problem for subregular language families
- State complexity of permutation on finite languages over a binary alphabet
- On NFAs where all states are final, initial, or both
- scientific article; zbMATH DE number 1962794 (Why is no real title available?)
- Incomplete operational transition complexity of regular languages
- Nondeterministic state complexity of proportional removals
- THE LENGTH OF SUBSET REACHABILITY IN NONDETERMINISTIC AUTOMATA
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- scientific article; zbMATH DE number 1670710 (Why is no real title available?)
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Operational complexity and pumping lemmas
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)
