An algorithm for probabilistic alternating simulation

DOI10.1007/978-3-642-27660-6_35MaRDI QIDQ2891387zbMATH OpenOpenAlexFDO

Authors Chenyi Zhang, Jun Pang

Publication date 15 June 2012

Published in SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Applications of game theory (91A80) Temporal logic (03B44) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: In probabilistic game structures, probabilistic alternating simulation (PA-simulation) relations preserve formulas defined in probabilistic alternating-time temporal logic with respect to the behaviour of a subset of players. We propose a partition based algorithm for computing the largest PA-simulation, which is to our knowledge the first such algorithm that works in polynomial time, by extending the generalised coarsest partition problem (GCPP) in a game-based setting with mixed strategies. The algorithm has higher complexities than those in the literature for non-probabilistic simulation and probabilistic simulation without mixed actions, but slightly improves the existing result for computing probabilistic simulation with respect to mixed actions.

Recommendations

• On probabilistic alternating simulations
• Probabilistic bisimulation and simulation algorithms by abstract interpretation
• A Space-Efficient Probabilistic Simulation Algorithm
• Deciding bisimilarity and similarity for probabilistic processes.
• Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation

Cites work

• scientific article; zbMATH DE number 3870578 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 1927574 (Why is no real title available?)
• scientific article; zbMATH DE number 794262 (Why is no real title available?)
• scientific article; zbMATH DE number 2209335 (Why is no real title available?)
• A Space-Efficient Probabilistic Simulation Algorithm
• A new polynomial-time algorithm for linear programming
• Algorithms for game metrics
• Alternating-time temporal logic
• Concurrent reachability games
• Correcting a Space-Efficient Simulation Algorithm
• Deciding bisimilarity and similarity for probabilistic processes.
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• From bisimulation to simulation: Coarsest partition problems
• Game Refinement Relations and Metrics
• On probabilistic alternating simulations
• Quantitative solution of omega-regular games
• Quantitative verification and control via the mu-calculus.
• Simulation-based minimization
• Stochastic Games
• The complexity of quantitative concurrent parity games
• Theory of games and economic behavior.

Cited in

(5)

• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• On probabilistic alternating simulations
• Reversible algorithm of simulating multivariate densities with multi-hump
• An Algorithm to Simulate VMA Processes Having a Spectrum with Fixed Condition Number
• Automatic verification of competitive stochastic systems

This page was built for publication: An algorithm for probabilistic alternating simulation

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