On the Complexity of the Equivalence Problem for Probabilistic Automata

Details On the Complexity of the Equivalence Problem for Probabilistic Automata On the Complexity of the Equivalence Problem for Probabilistic Automata

2011-12-20

arxiv.org/abs/1112.4644v2

Computer Science

Formal Languages and Automata Theory

technical report for a FoSSaCS'12 paper

Scientific paper

Checking two probabilistic automata for equivalence has been shown to be a key problem for efficiently 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 show how to check for equivalence two probabilistic automata with (cumulative) rewards. Our algorithm runs in deterministic polynomial time, if the number of reward counters is fixed. Finally we show that the equivalence problem for probabilistic visibly pushdown automata is logspace equivalent to the Arithmetic Circuit Identity Testing problem, which is to decide whether a polynomial represented by an arithmetic circuit is identically zero.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of the Equivalence Problem for Probabilistic Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of the Equivalence Problem for Probabilistic Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of the Equivalence Problem for Probabilistic Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56117