On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes

DOI10.1007/978-3-540-85780-8_3zbMath1159.68017OpenAlexW1589805592MaRDI QIDQ3532998

Juraj Hromkovič, Georg Schnitger

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_3

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Descriptional and computational complexity of finite automata -- a survey ⋮ Language operations with regular expressions of polynomial size ⋮ Weighted automata are compact and actively learnable

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
• Partial orders on words, minimal elements of regular languages, and state complexity
• Prediction-preserving reducibility
• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• Finite automata and unary languages
• A comparison of two lower-bound methods for communication complexity
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Comparing the size of NFAs with and without \(\epsilon\)-transitions
• Minimizing nfa's and regular expressions
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Number-theoretic constructions of efficient pseudo-random functions
• A geometrical view of the determinization and minimization of finite-state automata
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Minimal NFA Problems are Hard
• Communication Complexity
• Descriptional Complexity of Nondeterministic Finite Automata
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Mathematical Foundations of Computer Science 2003
• Regular Expressions and NFAs Without ε-Transitions
• Natural proofs
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata

This page was built for publication: On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes