×

A stochastic interpretation of propositional dynamic logic: expressivity. (English) Zbl 1252.03074

Summary: We propose a probabilistic interpretation of propositional dynamic logic (PDL). We show that logical and behavioral equivalence are equivalent over general measurable spaces. This is done first for the fragment of straight-line programs and then extended to cater for the nondeterministic nature of choice and iteration, expanded to PDL as a whole. Bisimilarity is also discussed and shown to be equivalent to logical and behavioral equivalence, provided the base spaces are Polish spaces. We adapt techniques from coalgebraic stochastic logic and point out some connections to Souslin’s operation \(\mathcal A\) from descriptive set theory. This leads to a discussion of complete stochastic Kripke models and model completion, which permits an adequate treatment of the test operator.

MSC:

03B70 Logic in computer science
03E15 Descriptive set theory
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] DOI: 10.1090/S0002-9939-1974-0330393-X · doi:10.1090/S0002-9939-1974-0330393-X
[2] Topics in the theory of computation 24 pp 111– (1985)
[3] Stochastic coalgebraic logic (2009) · Zbl 1179.03023
[4] Stochastic relations. Foundations for Markov transition systems (2007) · Zbl 1137.60002
[5] DOI: 10.1016/j.jpaa.2007.03.003 · Zbl 1122.18004 · doi:10.1016/j.jpaa.2007.03.003
[6] SIAM Journal on Computing 35 pp 590– (2006)
[7] DOI: 10.1016/S0019-9958(84)80053-4 · Zbl 0589.68046 · doi:10.1016/S0019-9958(84)80053-4
[8] DOI: 10.1006/inco.2001.2962 · Zbl 1096.68103 · doi:10.1006/inco.2001.2962
[9] DOI: 10.1017/S1357530902000704 · doi:10.1017/S1357530902000704
[10] Handbook of modal logic pp 1– (2007)
[11] Modal logic 53 (2001) · Zbl 0998.03015
[12] The art of computer programming. Volume III, Sorting and searching (1973)
[13] Classical descriptive set theory (1994)
[14] Proceedings of ICALP’80 85 pp 395– (1980)
[15] Fundamenta Informaticae 57 pp 281– (2003)
[16] Measure theory (1950)
[17] Categorical aspects of topology and analysis 915 pp 68– (1981)
[18] DOI: 10.1017/S0960129510000526 · Zbl 1235.03065 · doi:10.1017/S0960129510000526
[19] Mathematical Structures in Computer Science 21 (2011)
[20] Rendiconti dell’Istituto di Matematica dell’Università di Trieste 42 pp 191– (2010)
[21] DOI: 10.1016/S1570-2464(07)80023-1 · doi:10.1016/S1570-2464(07)80023-1
[22] DOI: 10.1016/j.ic.2011.02.003 · Zbl 1216.68196 · doi:10.1016/j.ic.2011.02.003
[23] A course on Borei sets (1998)
[24] Proceedings of ICALP 4596 pp 459– (2007)
[25] DOI: 10.1016/S0304-3975(00)00056-6 · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6
[26] DOI: 10.1023/A:1027354826364 · Zbl 1040.03013 · doi:10.1023/A:1027354826364
[27] DOI: 10.1016/S0304-3975(00)00125-0 · Zbl 0974.68034 · doi:10.1016/S0304-3975(00)00125-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.