On the Complexity of the Equivalence Problem for Probabilistic Automata

DOI10.1007/978-3-642-28729-9_31MaRDI QIDQ2892790zbMATH OpenOpenAlexFDO

Authors Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, James Worrell

Publication date 22 June 2012

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.4644

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• scientific article; zbMATH DE number 3240399
• scientific article; zbMATH DE number 20623
• On the computational complexity of approximating distributions by probabilistic automata
• scientific article; zbMATH DE number 1809724
• L_p DISTANCE AND EQUIVALENCE OF PROBABILISTIC AUTOMATA
• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• Equivalence of probabilistic \(\mu\)-calculus and p-automata

Cited in

(19)

• On the computational complexity of approximating distributions by probabilistic automata
• The quest for minimal quotients for probabilistic and Markov automata
• Language equivalence of probabilistic pushdown automata
• One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• scientific article; zbMATH DE number 3854424 (Why is no real title available?)
• Efficient Computation of the Relative Entropy of Probabilistic Automata
• scientific article; zbMATH DE number 5734241 (Why is no real title available?)
• scientific article; zbMATH DE number 17834 (Why is no real title available?)
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• scientific article; zbMATH DE number 1836414 (Why is no real title available?)
• scientific article; zbMATH DE number 7439745 (Why is no real title available?)
• Relations on words
• Universal Equivalence and Majority of Probabilistic Programs over Finite Fields
• Undecidable Problems for Probabilistic Network Programming
• Universal equivalence and majority of probabilistic programs over finite fields
• Stability and Complexity of Minimising Probabilistic Automata
• Artin’s Conjecture and Size of Finite Probabilistic Automata
• The complexity of probabilistic versus deterministic finite automata

This page was built for publication: On the Complexity of the Equivalence Problem for Probabilistic Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2892790)