Tracing Relations Probabilistically

• Autorzy: Doberkat E.-E.
• Języki publikacji: EN

Abstrakty

EN

We investigate similarities between non-deterministic and probabilistic ways of describing a system in terms of computation trees. We show that the construction of traces for both kinds of relations follows the same principles of construction. Representations of measurable trees in terms of probabilistic relations are given. This shows that stochastic relations may serve as refinements of their non-deterministic counterparts. A convexity argument formalizes the observation that non-deterministic system descriptions are underspecified when compared to probabilistic ones. The mathematical tools come essentially from the theory of measurable selections.

Słowa kluczowe

EN

probabilistic relations; specification techniques; representation theorems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 66, nr 3
• Strony: 259--275
• Opis fizyczny: Bibliogr. 22 poz., tab.

Twórcy

autor

Doberkat E.-E.

• Chair for Software Technology University of Dortmund D-44221 Dortmund, Germany,

Bibliografia

• [1] Abramsky, S., Blute, R., Panangaden, P.: Nuclear and Trace Ideal in Tensored *-Categories, Journal of Pure and Applied Algebra, 143(1 – 3), 1999, 3 – 47.
• [2] van Breugel, F., Shalit, S., Worrell, J.: Testing Labelled Markov Processes, Proc. ICALP’2002, 2380, Springer-Verlag, Berlin, 2002.
• [3] Brink, C., Kahl,W., Schmidt, G., Eds.: Relational Methods in Computer Science, Advances in Computing Science, Springer-Verlag,Wien, New York, 1997.
• [4] Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation of Labelled Markov-Processes, Information and Computation, 179(2), 2002, 163 – 193.
• [5] Doberkat, E.-E.: The Demonic Product of Probabilistic Relations, Proc. Foundations of Software Science and Computation Structures’02, 2303, Springer-Verlag, Berlin, 2002.
• [6] Doberkat, E.-E.: Semi-Pullbacks and Bisimulations in Categories of Stochastic Relations, Proc. ICALP’03, 2719, Springer-Verlag, Berlin, 2003.
• [7] Doberkat, E.-E.: The Converse of a Probabilistic Relation, J. Logic and Algebraic Progr., 62(1), 2004, 133 – 154.
• [8] Doberkat, E.-E.: Derandomizing probabilistic semantics through Eilenberg-Moore algebras for the Giry monad, Technical Report 152, Chair for Software-Technology, University of Dortmund, August 2004.
• [9] Doberkat, E.-E.: Stochastic relations: congruences, bisimulations and the Hennessy-Milner Theorem, Technical Report 786, Department of Computer Science, University of Dortmund,May 2004.
• [10] Doberkat, E.-E.: Tracing Relations Probabilistically, Relational and Kleene-Algebraic Methods in Computer Science (R. Berghammer, B. M¨oller, G. Struth, Eds.), 3051, Springer-Verlag, Berlin, 2004, Full version to appear in Fundamenta Informaticae.
• [11] Edalat, A.: Semi-pullbacks and Bisimulation in Categories of Markov Processes, Math. Struct. in Comp. Science, 9(5), 1999, 523 – 543.
• [12] Fuchssteiner, B., Lusky, W.: Convex Cones, vol. 56 of North-Holland Mathematical Studies, North-Holland Publishing Company, Amsterdam, 1981.
• [13] Giry, M.: A categorical approach to probability theory, Categorical Aspects of Topology and Analysis, 915, Springer-Verlag, Berlin, 1981.
• [14] Himmelberg, C. J.: Measurable Relations, Fund. Math., 87, 1975, 53 – 72.
• [15] Kechris, A. S.: Classical Descriptive Set Theory, Graduate Texts in Mathematics, Springer-Verlag, Berlin, Heidelberg, New York, 1994.
• [16] Lane, S.M.: Categories for the Working Mathematician, Graduate Texts in Mathematics, Springer-Verlag, Berlin, 1997.
• [17] Morgan, C., McIver, A., Seidel, K.: Probabilistic Predicate Transformers, ACM Trans. Prog. Lang. Syst., 18(3),May 1996, 325 – 353.
• [18] Panangaden, P.: Probabilistic Relations, Proc. PROBMIV (C. Baier, M. Huth, M. Kwiatkowska, M. Ryan, Eds.), 1998, Also available from the School of Computer Science, McGill University, Montreal.
• [19] Panangaden, P.: Does combining Nondeterminism and Probability make Sense?, Bulletin of the EATCS, (75), Oct. 2001, 182 – 189.
• [20] Parthasarathy, K. R.: Probability Measures on Metric Spaces, Academic Press, New York, 1967.
• [21] Schmidt, G., Str¨ohlein, T.: Relations and Graphs — Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1993.
• [22] Srivastava, S. M.: A Course on Borel Sets, Graduate Texts in Mathematics, Springer-Verlag, Berlin, 1998.