The parallel complexity of finite-state automata problems

DOI10.1016/0890-5401(92)90002-WzbMath0755.68051MaRDI QIDQ1186807

Sang Cho, Dung T. Huynh

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

minimization problemequivalence problemsdegree of ambiguityparallel complexity classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (17)

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

This page was built for publication: The parallel complexity of finite-state automata problems