On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
From MaRDI portal
Publication:2271436
DOI10.1016/j.tcs.2009.03.020zbMath1173.68035OpenAlexW2042919731MaRDI QIDQ2271436
Holger Petersen, Georg Schnitger, Juraj Hromkovič
Publication date: 7 August 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.020
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Lifting query complexity to time-space complexity for two-way finite automata ⋮ Probabilism versus Alternation for Automata ⋮ Limitations of lower bound methods for deterministic 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
- Partial orders on words, minimal elements of regular languages, and state complexity
- Finite automata and unary languages
- Intersection and union of regular languages and state complexity
- A comparison of two lower-bound methods for communication complexity
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Communication complexity method for measuring nondeterminism in finite automata
- State complexity of combined operations
- Minimizing nfa's and regular expressions
- A geometrical view of the determinization and minimization of finite-state automata
- STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Minimal NFA Problems are Hard
- Communication Complexity
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- Ambiguity and Communication
- Descriptional Complexity of Nondeterministic Finite Automata
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- On the State Minimization of Nondeterministic Finite Automata
This page was built for publication: On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
