Polynomial time decision algorithms for probabilistic automata

DOI10.1016/j.ic.2015.07.004zbMath1329.68168OpenAlexW1037179907MaRDI QIDQ498403

Andrea Turrini, Holger Hermanns

Publication date: 28 September 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.07.004

zbMATH Keywords

linear programming problemprobabilistic automatabranching probabilistic bisimulationbranching probabilistic simulationpolynomial decision algorithmweak probabilistic bisimulationweak probabilistic simulation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (9)

Deciding probabilistic automata weak bisimulation: theory and practice ⋮ Model independent approach to probabilistic models ⋮ An efficient algorithm to determine probabilistic bisimulation ⋮ On divergence-sensitive weak probabilistic bisimilarity ⋮ On well-founded and recursive coalgebras ⋮ Verifying quantum communication protocols with ground bisimulation ⋮ Unnamed Item ⋮ The quest for minimal quotients for probabilistic and Markov automata ⋮ Raiders of the lost equivalence: probabilistic branching bisimilarity

Uses Software

• SIGREF
• PRISM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interactive Markov chains. And the quest for quantified quality
• CCS expressions, finite state processes, and three problems of equivalence
• Optimal state-space lumping in Markov chains
• Network simplex algorithm for the general equal flow problem.
• The many facets of linear programming
• Automated compositional Markov chain generation for a plain-old telephone system
• Deciding bisimilarity and similarity for probabilistic processes.
• An algorithm to solve the proportional network flow problem
• Branching bisimulation for probabilistic systems: characteristics and decidability
• Finite state Markovian decision processes
• Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time
• On the Semantics of Markov Automata
• Sigref – A Symbolic Bisimulation Tool Box
• A testing scenario for probabilistic processes
• Concurrency and Composition in a Stochastic World
• Towards Performance Prediction of Compositional Models in Industrial GALS Designs
• Three Partition Refinement Algorithms
• Branching time and abstraction in bisimulation semantics
• Probability and Nondeterminism in Operational Models of Concurrency
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• Cost Preserving Bisimulations for Probabilistic Automata
• Cost Preserving Bisimulations for Probabilistic Automata

This page was built for publication: Polynomial time decision algorithms for probabilistic automata