The parallel complexity of finite-state automata problems

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

Dung T. Huynh, Sang Cho

Publication date: 28 June 1992

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

zbMATH Keywords

minimization problem; equivalence problems; degree of ambiguity; parallel complexity classes

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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, 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