A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata

DOI10.1137/0221017zbMath0755.68075OpenAlexW2027671360MaRDI QIDQ3990650

Wen-Guey Tzeng

Publication date: 28 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221017

zbMATH Keywords

nondeterministic finite automataapproximate equivalenceunambiguous finite automatapath equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (34)

Porous invariants ⋮ On path equivalence of nondeterministic finite automata ⋮ Unnamed Item ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ A uniform framework for modeling nondeterministic, probabilistic, stochastic, or mixed processes and their behavioral equivalences ⋮ Minimisation of Multiplicity Tree Automata ⋮ Model checking differentially private properties ⋮ Diagnosability of fault patterns with labeled stochastic Petri nets ⋮ Unnamed Item ⋮ Equivalence checking of quantum finite-state machines ⋮ EQUIVALENCE OF LABELED MARKOV CHAINS ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties ⋮ Relations on words ⋮ On the complexity of minimizing probabilistic and quantum automata ⋮ Weighted path queries on semistructured databases ⋮ Hierarchy and equivalence of multi-letter quantum finite automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The quest for minimal quotients for probabilistic and Markov automata ⋮ Unnamed Item ⋮ Quantitative simulations by matrices ⋮ Determining the equivalence for one-way quantum finite automata ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ On finite monoids over nonnegative integer matrices and short killing words ⋮ A note on quantum sequential machines ⋮ Approximating Markovian testing equivalence ⋮ Characterizations of one-way general quantum finite automata ⋮ Multi-letter quantum finite automata: decidability of the equivalence and minimization of states ⋮ On Nonnegative Integer Matrices and Short Killing Words ⋮ Undecidable Problems for Probabilistic Network Programming ⋮ Note on the complexity of Las Vegas automata problems ⋮ On hybrid models of quantum finite automata

This page was built for publication: A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata