An Algorithm for Probabilistic Alternating Simulation

Details An Algorithm for Probabilistic Alternating Simulation An Algorithm for Probabilistic Alternating Simulation

2011-06-10

arxiv.org/abs/1106.1978v2

Computer Science

Computer Science and Game Theory

15 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Algorithm for Probabilistic Alternating Simulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Algorithm for Probabilistic Alternating Simulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithm for Probabilistic Alternating Simulation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319901