On path equivalence of nondeterministic finite automata

DOI10.1016/0020-0190(96)00039-7zbMath0875.68650OpenAlexW2012572971MaRDI QIDQ1351166

Wen-Guey Tzeng

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00039-7

zbMATH Keywords

AlgorithmsComputational complexityAutomatonPath equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ Universality Problem for Unambiguous VASS ⋮ Note on the complexity of Las Vegas automata problems ⋮ Image-binary automata

Cites Work

• Space-bounded reducibility among combinatorial problems
• A taxonomy of problems with fast parallel algorithms
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On path equivalence of nondeterministic finite automata