The parallel complexity of finite-state automata problems
From MaRDI portal
Publication:1186807
DOI10.1016/0890-5401(92)90002-WzbMath0755.68051MaRDI QIDQ1186807
Publication date: 28 June 1992
Published in: Information and Computation (Search for Journal in Brave)
68Q45: Formal languages and automata
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Minimal Reversible Deterministic Finite Automata, More on Minimizing Finite Automata with Errors — Nondeterministic Machines, Operational State Complexity and Decidability of Jumping Finite Automata, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, Minimal and Hyper-Minimal Biautomata, Descriptional and computational complexity of finite automata -- a survey, Finite-automaton aperiodicity is PSPACE-complete, A note on the space complexity of some decision problems for finite automata, Problems on finite automata and the exponential time hypothesis, On the computational complexity of problems related to distinguishability sets, Problems on Finite Automata and the Exponential Time Hypothesis, Minimisation of Multiplicity Tree Automata, Note on the complexity of Las Vegas automata problems, Descriptional and Computational Complexity of Finite Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The method of forced enumeration for nondeterministic automata
- Matrix systems and principal cones of algebraic power series
- On the finite-valuedness problem for sequential machines
- A taxonomy of problems with fast parallel algorithms
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Nondeterministic Space is Closed under Complementation
- New problems complete for nondeterministic log space
