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.68035MaRDI 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
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Probabilism versus Alternation for Automata, Limitations of lower bound methods for deterministic nested word automata, Descriptional complexity of regular languages
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
