On the Complexity of the Equivalence Problem for Probabilistic Automata

On the Complexity of the Equivalence Problem for Probabilistic Automata

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 sho...

Bibliografske podrobnosti
Main Authors:	Kiefer, S, Murawski, A, Ouaknine, J, Wachter, B, Worrell, J
Format:	Journal article
Jezik:	English
Izdano:	2012

Podobne knjige/članki

Language equivalence for probabilistic automata
od: Kiefer, S, et al.
Izdano: (2011)

ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA
od: Kiefer, S, et al.
Izdano: (2013)

On the Complexity of Equivalence and Minimisation for Q-weighted Automata
od: Stefan Kiefer, et al.
Izdano: (2013-03-01)

Algorithmic probabilistic game semantics
od: Kiefer, S, et al.
Izdano: (2013)

APEX: An analyzer for open probabilistic programs
od: Kiefer, S, et al.
Izdano: (2012)

Language Equivalence for Probabilistic Automata
od: Wachter, J
Izdano: (2011)

Revisiting the Equivalence Problem for Finite Multitape Automata
od: Worrell, J
Izdano: (2013)

Complexity of equivalence and learning for multiplicity tree automata
od: Marusic, I, et al.
Izdano: (2015)

Three tokens in Herman's algorithm
od: Kiefer, S, et al.
Izdano: (2012)

Game characterization of probabilistic bisimilarity, and applications to pushdown automata
od: Forejt, V, et al.
Izdano: (2018)

The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata
od: van Breugel, F, et al.
Izdano: (2014)

On automated verification of probabilistic programs
od: Legay, A, et al.
Izdano: (2008)

On the relationship between reachability problems in timed and counter automata
od: Haase, C, et al.
Izdano: (2012)

On the Relationship between Reachability Problems in Timed and Counter Automata
od: Haase, C, et al.
Izdano: (2012)

Game Characterization of Probabilistic Bisimilarity, and Applications to Pushdown Automata
od: Vojtěch Forejt, et al.
Izdano: (2018-11-01)

Probabilistic automata of bounded ambiguity
od: Fijalkow, N, et al.
Izdano: (2017)

Decidability and complexity results for timed automata via channel machines
od: Abdulla, P, et al.
Izdano: (2005)

Bisimulations Meet PCTL Equivalences for Probabilistic Automata
od: Lei Song, et al.
Izdano: (2013-06-01)

Convex language semantics for nondeterministic probabilistic automata
od: Van Heerdt, G, et al.
Izdano: (2018)

DEQ: Equivalence checker for deterministic register automata
od: Murawski, A, et al.
Izdano: (2019)

Undecidability of universality for timed automata with minimal resources
od: Adams, S, et al.
Izdano: (2007)

Undecidability of Universality for Timed Automata with Minimal Resources
od: Adams, S, et al.
Izdano: (2007)

When is containment decidable for probabilistic automata?
od: Daviaud, L, et al.
Izdano: (2018)

Algebraic invariants for linear hybrid automata
od: Majumdar, R, et al.
Izdano: (2020)

The Big-O problem for labelled Markov chains and weighted automata
od: Chistikov, D, et al.
Izdano: (2020)

Reachability in Succinct and Parametric One−Counter Automata
od: Haase, C, et al.
Izdano: (2009)

Reachability in Succinct and Parametric One-Counter Automata
od: Haase, C, et al.
Izdano: (2009)

Minimisation of multiplicity tree automata
od: Worrell, J, et al.
Izdano: (2017)

Polynomial-time equivalence testing for deterministic fresh-register automata
od: Murawski, A, et al.
Izdano: (2018)

Alternating Timed Automata over Bounded Time
od: Jenkins, M, et al.
Izdano: (2010)

Model Checking Succinct and Parametric One-Counter Automata.
od: Göller, S, et al.
Izdano: (2010)

Model Checking Succinct and Parametric One−Counter Automata
od: Göller, S, et al.
Izdano: (2010)

Alternating Timed Automata over Bounded Time
od: Jenkins, M, et al.
Izdano: (2010)

Branching-time model checking of parametric one-counter automata
od: Göller, S, et al.
Izdano: (2012)

Branching−Time Model Checking of Parametric One−Counter Automata
od: Göller, S, et al.
Izdano: (2012)

On stabilization in Herman's algorithm
od: Kiefer, S, et al.
Izdano: (2011)

When are emptiness and containment decidable for probabilistic automata?
od: Daviaud, L, et al.
Izdano: (2021)

Universality Analysis for One-Clock Timed Automata
od: Abdulla, P, et al.
Izdano: (2008)

On the complexity of the orbit problem
od: Chonev, V, et al.
Izdano: (2016)

On the complexity of the orbit problem
od: Chonev, V, et al.
Izdano: (2016)