Lower bounds for the transition complexity of NFAs

DOI10.1016/j.jcss.2008.02.007zbMath1152.68028OpenAlexW2091741450MaRDI QIDQ955341

Michael Domaratzki, Kai Salomaa

Publication date: 19 November 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.02.007

zbMATH Keywords

regular languagesdescriptional complexitynondeterministic finite automatafinite projective planes

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

State complexity of permutation on finite languages over a binary alphabet ⋮ STATE COMPLEXITY AND APPROXIMATION ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Nondeterministic state complexity of nested word automata ⋮ State Complexity of Nested Word Automata ⋮ Descriptional complexity of regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Minimizing finite automata is computationally hard
• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• Comparing the size of NFAs with and without \(\epsilon\)-transitions
• Transition complexity of language operations
• On the average state and transition complexity of finite languages
• Minimizing nfa's and regular expressions
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Minimal NFA Problems are Hard
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Regular Expressions and NFAs Without ε-Transitions
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Lower Bounds for the Transition Complexity of NFAs
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata

This page was built for publication: Lower bounds for the transition complexity of NFAs