An algorithm for probabilistic alternating simulation

Zhang, Chenyi and Pang, Jun (2012). An algorithm for probabilistic alternating simulation. In: Maria Bielikova, Gerhard Friedrich, Georg Gottlob, Stefan Katzenbeisser and Gyorgy Turan, SOFSEM 2012: Theory and Practice of Computer Science : 38th Conference on Current Trends in Theory and Practice of Computer Science. 38th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, (431-442). 21 - 27 January 2012. doi:10.1007/978-3-642-27660-6_35


Author Zhang, Chenyi
Pang, Jun
Title of paper An algorithm for probabilistic alternating simulation
Conference name 38th Conference on Current Trends in Theory and Practice of Computer Science
Conference location Spindleruv Mlyn, Czech Republic
Conference dates 21 - 27 January 2012
Proceedings title SOFSEM 2012: Theory and Practice of Computer Science : 38th Conference on Current Trends in Theory and Practice of Computer Science   Check publisher's open access policy
Journal name Lecture Notes in Computer Science   Check publisher's open access policy
Place of Publication Berlin, Germany
Publisher Springer
Publication Year 2012
Sub-type Fully published paper
DOI 10.1007/978-3-642-27660-6_35
ISBN 9783642276590
3642276598
9783642276606
3642276601
ISSN 0302-9743
Editor Maria Bielikova
Gerhard Friedrich
Georg Gottlob
Stefan Katzenbeisser
Gyorgy Turan
Volume 7147 LNCS
Start page 431
End page 442
Total pages 12
Collection year 2013
Language eng
Formatted Abstract/Summary 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. It is to our knowledge the first such algorithm that works in polynomial time. Our solution extends the generalised coarsest partition problem (GCPP) to 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.
Keyword Algorithms
Alternating simulation
Probabilistic simulation
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Access Statistics: 59 Abstract Views  -  Detailed Statistics
Created: Tue, 28 Feb 2012, 13:51:18 EST by Chenyi Zhang on behalf of School of Information Technol and Elec Engineering