Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time

DOI10.4230/LIPIcs.FSTTCS.2012.435zbMath1354.68157arXiv1205.0376OpenAlexW2963069146MaRDI QIDQ2957519

Andrea Turrini, Holger Hermanns

Publication date: 26 January 2017

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

zbMATH Keywords

linear programming problemprobabilistic automatapolynomial decision algorithmweak probabilsitic bisimulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Axiomatising infinitary probabilistic weak bisimilarity of finite-state behaviours ⋮ Computing Behavioral Relations for Probabilistic Concurrent Systems ⋮ Equivalence checking 40 years after: a review of bisimulation tools ⋮ Polynomial time decision algorithms for probabilistic automata ⋮ Markov automata: deciding weak bisimulation by means of non-naïvely vanishing states

This page was built for publication: Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time