## On the complexity of equivalence and minimisation for
Q-weighted automata

*Stefan Kiefer*, *Andrzej Murawski*,
*Joël
Ouaknine*, *Bjoern Wachter*, and *James Worrell*
This paper is concerned with the computational complexity of
equivalence and minimisation for automata with transition weights in
the field **Q** of rational numbers. We use polynomial identity
testing and the Isolation Lemma to obtain complexity bounds, focussing
on the class NC of problems within P solvable in polylogarithmic
parallel time. For finite **Q**-weighted automata, we give a
randomised NC procedure that either outputs that two automata are
equivalent or returns a word on which they differ. We also give an NC
procedure for deciding whether a given automaton is minimal, as well
as a randomised NC procedure that minimises an automaton. We consider
probabilistic automata with rewards, similar to Markov Decision
Processes. For these automata we consider two notions of equivalence:
expectation equivalence and distribution equivalence. The former
requires that two automata have the same expected reward on each input
word, while the latter requires that each input word induce the same
distribution on rewards in each automaton. For both notions we give
algorithms for deciding equivalence by reduction to equivalence
of **Q**-weighted automata. Finally we show that the equivalence
problem for **Q**-weighted visibly pushdown automata is logspace
equivalent to the polynomial identity testing problem.

*Logical Methods in Computer Science* 9(1), 2013. 22 pages.

PDF
© 2013 Stefan Kiefer, Andrzej Murawski,
Joël Ouaknine, Bjoern Wachter, and James Worrell.

Imprint / Data Protection