Bisimulation Cuts For Structuring Markov Transition Systems

• Autorzy: Doberkat E.-E.

Identyfikatory

DOI

10.3233/FI-2016-1452

• Języki publikacji: EN

Abstrakty

EN

In Universal Algebra the structure of congruences for algebraic systems is fairly well investigated, and the relationship to the structure of the underlying system proper is well known. We propose a first step into this direction for studying the structure of congruences for stochastic relations. A Galois connection to a certain class of Boolean σ-algebras is exploited, atoms and antiatoms are identified, and it is show that a σ-basis exists. These constructions are applied to the problem of finding bisimulation cuts of a congruence. It cuts the relation through a span of morphisms with a minimum of joint events.

Słowa kluczowe

EN

bisimulation; Markov processes; universal algebra; congruences; Galois modules

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 4
• Strony: 363--383
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Doberkat E.-E.

• Math++Software, Bochum, Germany

Bibliografia

• 1] Aczel P. Non-Well-Founded Sets. Number 41 in CSLI Lecture Notes. CSLI Publications, Center for the Study of Language and Information, Stanford, 1988. ISBN:9780937073223.
• [2] Battenfeld I. A domain-theoretic investigation of posets of sub-sigma-algebras (extended abstract). In Xizhong Zheng and Ning Zhong, editors, Proc. Seventh Int. Conf. Computability and Complexity in Analysis, EPTCS, 2010;24:19–28. doi:10.4204/EPTCS.24.7.
• [3] Burris S and Sankappanavar HP. A Course in Universal Algebra. Springer-Verlag (The Millennium Edition), 1981. ISBN:0387905782, 9780387905785.
• [4] Chang CC and Keisler HJ. Model Theory, volume 73 of Studies in Logic and the Foundations of Mathematics. Elsevier, Amsterdam, 1990. ISBN-13:978-0444880543.
• [5] Danos V, Desharnais J, Laviolette F, and Panangaden P. Bisimulation and cocongruence for probabilistic systems. Information and Computation, 2006;204(4):503–523. doi:10.1016/j.ic.2005.02.004.
• [6] Desharnais J, Edalat A, and Panangaden P. Bisimulation of labelled Markov processes. Information and Computation, 2002;179(2):163–193. doi:10.1006/inco.2001.2962.
• [7] Doberkat EE. Stochastic relations: congruences, bisimulations and the Hennessy-Milner theorem. SIAM J. Computing, 2006;35(3):590–626. doi:10.1137/S009753970444346X.
• [8] Doberkat EE. Stochastic Relations. Foundations for Markov Transition Systems. Chapman & Hall/CRC Press, Boca Raton, New York, 2007. ISBN:9781584889410.
• [9] Doberkat EE. Stochastic Coalgebraic Logic. EATCS Monographs in Theoretical Computer Science. Springer-Verlag, Berlin, 2009. doi:10.1007/978-3-642-02995-0.
• [10] Doberkat EE. Algebraic properties of stochastic effectivity functions. J. Logic and Algebraic Progr., 2014;83:339–358. Available from: http://dx.doi.org/10.1016/j.jlamp.2014.03.002.
• [11] Doberkat EE. Special Topics in Mathematics for Computer Science: Sets, Categories, Topologies, Measures. Springer International Publishing Switzerland, Cham, Heidelberg, New York, Dordrecht, London, December 2015. doi:10.1007/978-3-319-22750-4.
• [12] Doberkat EE, and Schubert Ch. Coalgebraic logic over general measurable spaces - a survey. Math. Struct. Comp. Science, 2011;21:175–234. doi:10.1017/S0960129510000526.
• [13] Doberkat EE, and Sànchez Terraf P. Stochastic nondeterminism and effectivity functions. J. Logic and Computation, 2015. doi:10.1093/logcom/exv049.
• [14] Giry M. A categorical approach to probability theory. In: Categorical Aspects of Topology and Analysis, number 915 in Lect. Notes Math., Springer-Verlag, Berlin, 1981 p. 68-85. doi:10.1007/BFb0092872.
• [15] Grätzer G. Universal Algebra. The University Series in Higher Mathematics. Van Nostrand, Princeton, N.J., 1968. Available from: https://books.google.pl/books?id=DjqkAAAAIAAJ.
• [16] Hennessy M, and Milner R. On observing nondeterminism and concurrency. In: Proc. ICALP’80, number 85 in Lect. Notes Comp. Sci., pages 299–309, Berlin, 1980. Springer-Verlag. Available from: http://dl.acm.org/citation.cfm?id=646234.758793.
• [17] Kuratowski K. Topology, volume I. PWN – Polish Scientific Publishers and Academic Press, Warsaw and New York, 1966. ISBN-10:1483242110.
• [18] Parthasarathy KR. Probability Measures on Metric Spaces. Academic Press, New York, 1967. ISBN-10:082183889X, 13:978-0821838891.
• [19] Rao BV. Lattice of Borel structures. Coll. Math., 1971;23(2):213–216.
• [20] Bhaskara Rao KPS, and Rao BV. Borel spaces. Dissertationes Mathematicae, 1981;190:1–63. ISBN: 8301012536, 9788301012533.
• [21] Rutten JJM. Universal coalgebra: a theory of systems. Theor. Comp. Sci., 2000;249(1):3–80. doi:10.1016/S0304-3975(00)00056-6.
• [22] Sarbadhikari H, Bhaskara Rao KPS, and Grzegorek E. Complementation in the lattice of Borel structures. Coll. Math., 1974;31(1):29–32. Available from: http://eudml.org/doc/263892.
• [23] Schubert Ch. Terminal coalgebras for measure-polynomial functors. In: J. Chen and S. B. Cooper, (ed.), Proc. TAMC 2009, Changsha, volume 5532 of Lect. Notes Comp. Sci., Springer-Verlag, 2009 p. 325-334. doi:10.1007/978-3-642-02017-9_35.
• [24] Srivastava SM. A Course on Borel Sets. Graduate Texts in Mathematics, volume 180, Springer-Verlag, Berlin, 1998. doi:10.1007/b98956.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).