NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
From MaRDI portal
Publication:3395129
DOI10.1142/S0129054109006747zbMath1176.68106OpenAlexW2088578754WikidataQ57380806 ScholiaQ57380806MaRDI QIDQ3395129
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
Related Items
State complexity of permutation on finite languages over a binary alphabet ⋮ State complexity of projection on languages recognized by permutation automata and commuting letters ⋮ THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ Operational complexity and pumping lemmas ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Further Remarks on the Operational Nonterminal Complexity ⋮ Unambiguous finite automata over a unary alphabet ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Complexity of exclusive nondeterministic finite automata ⋮ Nondeterministic state complexity of star-free languages ⋮ Incomplete operational transition complexity of regular languages ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ State complexity of finite partial languages ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ State Trade-Offs in Unranked Tree Automata ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ Operational complexity and right linear grammars ⋮ On the number of active states in finite automata ⋮ State complexity of partial word finite automata ⋮ State complexity of finite partial languages
Cites Work
- 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
- 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
- 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
- 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
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- On the State Minimization of Nondeterministic Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
