Note on the complexity of Las Vegas automata problems
From MaRDI portal
Publication:3421911
DOI10.1051/ita:2006033zbMath1110.68051MaRDI QIDQ3421911
Publication date: 8 February 2007
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_3_501_0
computational complexity; deterministic and nondeterministic finite automata; Las Vegas finite automata
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- The method of forced enumeration for nondeterministic automata
- A note on the space complexity of some decision problems for finite automata
- The parallel complexity of finite-state automata problems
- Space-bounded reducibility among combinatorial problems
- On the equivalence, containment, and covering problems for the regular and context-free languages
- On path equivalence of nondeterministic finite automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Nondeterministic Space is Closed under Complementation
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- New problems complete for nondeterministic log space
- Minimal NFA Problems are Hard
- Lower Bounds for Las Vegas Automata by Information Theory
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the power of Las Vegas II: Two-way finite automata
