Document Open Access Logo

Computing Probabilistic Bisimilarity Distances via Policy Iteration

Authors Qiyi Tang, Franck van Breugel

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2016.22.pdf
  • Filesize: 467 kB
  • 15 pages

Document Identifiers

Author Details

Qiyi Tang
Franck van Breugel

Cite As Get BibTex

Qiyi Tang and Franck van Breugel. Computing Probabilistic Bisimilarity Distances via Policy Iteration. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CONCUR.2016.22

Abstract

A transformation mapping a labelled Markov chain to a simple stochastic game is presented.  In the resulting simple stochastic game, each vertex corresponds to a pair of states of the labelled Markov chain.  The value of a vertex of the simple stochastic game is shown to be equal to the probabilistic bisimilarity distance, a notion due to Desharnais, Gupta, Jagadeesan and Panangaden, of the corresponding pair of states of the labelled Markov chain.  Bacci, Bacci, Larsen and Mardare introduced an algorithm to compute the probabilistic bisimilarity distances for a labelled Markov chain.  A modification of a basic version of their algorithm for a labelled Markov chain is shown to be the policy iteration algorithm applied to the corresponding simple stochastic game.  Furthermore, it is shown that this algorithm takes exponential time in the worst case.

Subject Classification

Keywords
  • labelled Markov chain
  • simple stochastic game
  • probabilistic bisimilarity
  • pseudometric
  • value function
  • policy iteration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River, NJ, USA, 1993. Google Scholar
  2. Giorgio Bacci, Giovanni Bacci, Kim Larsen, and Radu Mardare. On-the-fly exact computation of bisimilarity distances. In Nir Piterman and Scott Smolka, editors, Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 7795 of Lecture Notes in Computer Science, pages 1-15, Rome, Italy, March 2013. Springer-Verlag. Google Scholar
  3. Christel Baier. Polynomial time algorithms for testing probabilistic bisimulation and simulation. In Rajeev Alur and Thomas Henzinger, editors, Proceedings of the 8th International Conference on Computer Aided Verification, volume 1102 of Lecture Notes in Computer Science, pages 50-61, New Brunswick, NJ, USA, July/August 1996. Springer-Verlag. Google Scholar
  4. Christel Baier and Joost-Pieter Katoen. Principles of Model Checking. The MIT Press, Cambridge, MA, USA, 2008. Google Scholar
  5. Franck van Breugel, Babita Sharma, and James Worrell. Approximating a behavioural pseudometric without discount. Logical Methods in Computer Science, 4(2), April 2008. Google Scholar
  6. Franck van Breugel and James Worrell. The complexity of computing a bisimilarity pseudometric on probabilistic automata. In Franck van Breugel, Elham Kashefi, Catuscia Palamidessi, and Jan Rutten, editors, Horizons of the Mind - A Tribute to Prakash Panangaden, volume 8464 of Lecture Notes in Computer Science, pages 191-213. Springer-Verlag, 2014. Google Scholar
  7. John Canny. Some algebraic and geometric computations in PSPACE. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 460-467, Chicago, IL, USA, May 1988. ACM. Google Scholar
  8. Di Chen, Franck van Breugel, and James Worrell. On the complexity of computing probabilistic bisimilarity. In Lars Birkedal, editor, Proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures, volume 7213 of Lecture Notes in Computer Science, pages 437-451, Tallinn, Estonia, March/April 2012. Springer-Verlag. Google Scholar
  9. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, February 1992. Google Scholar
  10. Anne Condon. On algorithms for simple stochastic games. In Jin-Yi Cai, editor, Advances in Computational Complexity Theory, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 51-73. American Mathematical Society, 1993. Google Scholar
  11. Brian Davey and Hilary Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, United Kingdom, 2002. Google Scholar
  12. Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labelled Markov processes. Theoretical Computer Science, 318(3):323-354, June 2004. Google Scholar
  13. Oliver Friedmann. Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs. PhD thesis, Ludwig-Maximilians-University, Munich, Germany, 2011. Google Scholar
  14. Alessandro Giacalone, Chi-Chang Jou, and Scott Smolka. Algebraic reasoning for probabilistic concurrent systems. In Proceedings of the IFIP WG 2.2/2.3 Working Conference on Programming Concepts and Methods, pages 443-458, Sea of Gallilee, Israel, April 1990. North-Holland. Google Scholar
  15. Alan Hoffman and Richard Karp. On nonterminating stochastic games. Management Science, 12(5):359-370, January 1966. Google Scholar
  16. Bengt Jonsson and Kim Larsen. Specification and refinement of probabilistic processes. In Proceedings of the 6th Annual Symposium on Logic in Computer Science, pages 266-277, Amsterdam, The Netherlands, July 1991. IEEE. Google Scholar
  17. Leonid Kantorovich. On the transfer of masses (in Russian). Doklady Akademii Nauk, 5(1):1-4, 1942. Translated in Management Science, 5(1):1-4, October 1958. Google Scholar
  18. Leonid Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20(1):191-194, 1979. Google Scholar
  19. Kim Larsen and Arne Skou. Bisimulation through probabilistic testing. Information and Computation, 94(1):1-28, September 1991. Google Scholar
  20. Mary Melekopoglou and Anne Condon. On the complexity of the policy iteration algorithm. Computer Science Technical Report 941, University of Wisconsin, Madison, WI, USA, June 1990. Google Scholar
  21. Robin Milner. A Calculus of Communicating Systems, volume 92 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, 1980. Google Scholar
  22. James Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(2):109-129, August 1997. Google Scholar
  23. Prakash Panangaden. Labelled Markov Processes. Imperial College Press, London, United Kingdom, 2009. Google Scholar
  24. David Park. Concurrency and automata on infinite sequences. In Peter Deussen, editor, Proceedings of 5th GI-Conference on Theoretical Computer Science, volume 104 of Lecture Notes in Computer Science, pages 167-183, Karlsruhe, Germany, March 1981. Springer-Verlag. Google Scholar
  25. Davide Sangiorgi. Introduction to Bisimulation and Coinduction. Cambridge University Press, Cambridge, United Kingdom, 2012. Google Scholar
  26. Lloyd Shapley. Stochastic games. Proceedings of the Academy of Sciences, 39(10):1095-1100, October 1953. Google Scholar
  27. James K. Strayer. Linear programming and its applications. Springer-Verlag, New York, NY, USA, 1989. Google Scholar
  28. Alfred Tarski. A decision method for elementary algebra and geometry. University of California Press, Berkeley, CA, USA, 1951. Google Scholar
  29. Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1/2):343-359, May 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact