## On the complexity of the equivalence
problem for probabilistic automata

*Stefan Kiefer*, *Andrzej S. Murawski*,
*Joël
Ouaknine*, *Bjorn Wachter*, and *James Worrell*
Deciding equivalence of probabilistic automata is a key problem for
establishing various behavioural and anonymity properties of
probabilistic systems. In recent experiments a randomised equivalence
test based on polynomial identity testing outperformed deterministic
algorithms. In this paper we show that polynomial identity testing
yields efficient algorithms for various generalisations of the
equivalence problem. First, we provide a randomized NC procedure that
also outputs a counterexample trace in case of inequivalence. Second,
we consider equivalence of probabilistic cost automata. In these
automata transitions are labelled with integer costs and each word is
associated with a distribution on costs, corresponding to the
cumulative costs of the accepting runs on that word. Two automata are
equivalent if they induce the same cost distributions on each input
word. We show that equivalence can be checked in randomised polynomial
time. Finally we show that the equivalence problem for probabilistic
visibly pushdown automata is logspace equivalent to the problem of
whether a polynomial represented by an arithmetic circuit is
identically zero.

*Proceedings of FOSSACS 12*, LNCS 7213, 2012. 15 pages.

PDF
© 2012
Springer-Verlag.

Imprint / Data Protection