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)
Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Problems on finite automata and the exponential time hypothesis ⋮ Unnamed Item ⋮ Minimisation of Multiplicity Tree Automata ⋮ Minimal Reversible Deterministic Finite Automata ⋮ On the computational complexity of problems related to distinguishability sets ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ A note on the space complexity of some decision problems for finite automata ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Minimal and Hyper-Minimal Biautomata ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Unnamed Item ⋮ The complexity of weakly recognizing morphisms ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS ⋮ Note on the complexity of Las Vegas automata problems ⋮ Finite-automaton aperiodicity is PSPACE-complete ⋮ More on Minimizing Finite Automata with Errors — Nondeterministic Machines
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
