Combining probabilistic and non-deterministic choice via weak distributive laws. (English) Zbl 1502.68171
Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 454-464 (2020).
MSC:
| 68Q55 | Semantics in the theory of computing |
| 18C50 | Categorical semantics of formal languages |
| 60B99 | Probability theory on algebraic and topological structures |
Keywords:
behavioral equivalence; convex powerset monad; finite distribution monad; non-determinism; probabilistic automata; probability; trace semantics; weak distributive law; weak liftingReferences:
| [1] | Michael Barr. 1970. Relational algebras. In Reports of the Midwest Category Seminar IV. Springer, 39-55. · Zbl 0204.33202 |
| [2] | Jon Beck. 1969. Distributive laws. In Seminar on Triples and Categorical Homology Theory, B. Eckmann (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 119-140. · Zbl 0186.02902 |
| [3] | Filippo Bonchi, Daniela Petrisan, Damien Pous, and Jurriaan Rot. 2014. Coinduction up-to in a fibrational setting. In CSL-LICS. ACM, 20:1-20:9. · Zbl 1395.68195 |
| [4] | Filippo Bonchi, Daniela Petrisan, Damien Pous, and Jurriaan Rot. 2017. A general account of coinduction up-to. Acta Inf. 54, 2 (2017), 127-190. · Zbl 1371.68186 |
| [5] | Filippo Bonchi, Alexandra Silva, and Ana Sokolova. 2017. The Power of Convex Algebras. In 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany. 23:1-23:18. https://doi.org/10.4230/LIPIcs.CONCUR.2017.23 · Zbl 1442.68085 |
| [6] | Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli. 2019. The Theory of Traces for Systems with Nondeterminism and Probability. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. 1-14. https://doi.org/10.1109/LICS.2019.8785673 · Zbl 07566077 |
| [7] | Gabriella Böhm. 2010. The weak theory of monads. Advances in Mathematics 225, 1 (2010), 1-32. https://doi.org/10.1016/j.aim.2010.02.015 · Zbl 1206.18004 |
| [8] | E. P. de Vink and J. J. M. M. Rutten. 1997. Bisimulation for probabilistic transition systems: A coalgebraic approach. In Automata, Languages and Programming, Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 460-470. · Zbl 1401.68236 |
| [9] | Ernst-Erich Doberkat. 2006. Eilenberg-Moore algebras for stochastic relations. Information and Computation 204, 12 (2006), 1756-1781. https://doi.org/10.1016/j.ic.2006.09.001 · Zbl 1116.18002 |
| [10] | J Farkas. 1902. Ober die Theorie der einfachen Ungleichungen. J. Reine Angew. Math 124 (1902), 1-24. |
| [11] | Richard Garner. 2019. The Vietoris Monad and Weak Distributive Laws. Applied Categorical Structures (16 Oct 2019). https://doi.org/10.1007/s10485-019-09582-w · Zbl 1442.18010 |
| [12] | Bart Jacobs. 2008. Coalgebraic Trace Semantics for Combined Possibilitistic and Probabilistic Systems. Electr. Notes Theor. Comput. Sci. 203, 5 (2008), 131-152. · Zbl 1279.68232 |
| [13] | Bart Jacobs, Alexandra Silva, and Ana Sokolova. 2015. Trace semantics via determinization. J. Comput. System Sci. 81, 5 (2015), 859-879. https://doi.org/10.1016/j.jcss.2014.12.005 11th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2012 (Selected Papers). · Zbl 1327.68158 |
| [14] | C. Jones and Gordon D. Plotkin. 1989. A Probabilistic Powerdomain of Evaluations. In LICS. IEEE Computer Society, 186-195. · Zbl 0716.06003 |
| [15] | Achim Jung and Regina Tix. 1998. The Troublesome Probabilistic Powerdomain. Electronic Notes in Theoretical Computer Science 13 (1998), 70-91. https://doi.org/10.1016/S1571-0661(05)80216-6 Comprox III, Third Workshop on Computation and Approximation. · Zbl 0917.68135 |
| [16] | Klaus Keimel and Gordon D. Plotkin. 2017. Mixed powerdomains for probability and nondeterminism. Logical Methods in Computer Science Volume 13, Issue 1 (Jan. 2017). https://doi.org/10.23638/LMCS-130:2)2017 · Zbl 1448.06002 |
| [17] | Bartek Klin and Julian Salamanca. 2018. Iterated Covariant Powerset is not a Monad. Electronic Notes in Theoretical Computer Science 341 (2018), 261-276. https://doi.org/10.1016/j.entcs.2018.11.013 Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). · Zbl 1528.18007 |
| [18] | Alexander Kurz and Jiri Velebil. 2016. Relation lifting, a survey. J. Log. Algebr. Meth. Program. 85, 4 (2016), 475-499. · Zbl 1344.68167 |
| [19] | Saunders MacLane. 1971. Categories for the Working Mathematician. Springer-Verlag, New York. Graduate Texts in Mathematics, Vol. 5. · Zbl 0705.18001 |
| [20] | Matteo Mio. 2014. Upper-Expectation Bisimilarity and Łukasiewicz μ-Calculus. In Foundations of Software Science and Computation Structures, Anca Muscholl (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 335-350. · Zbl 1405.68218 |
| [21] | Michael Mislove. 2000. Nondeterminism and Probabilistic Choice: Obeying the Laws. In CONCUR 2000 — Concurrency Theory, Catuscia Palamidessi (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 350-365. · Zbl 0999.68147 |
| [22] | Lawrence S. Moss. 1999. Coalgebraic logic. Annals of Pure and Applied Logic 96, 1 (1999), 277-317. https://doi.org/10.1016/S0168-0072(98) 00042-6 · Zbl 0969.03026 |
| [23] | G. D. Plotkin. 1976. A powerdomain construction. SIAM J. OF COMPUTING (1976). · Zbl 0355.68015 |
| [24] | Damien Pous and Davide Sangiorgi. 2011. Enhancements of the bisimulation proof method. Cambridge University Press, 233-289. https://doi.org/10.1017/CBO9780511792588.007 · Zbl 1285.68111 |
| [25] | N. Saheb-Djahromi. 1980. Cpo’s of measures for nondeterminism. Theoretical Computer Science 12, 1 (1980), 19-37. https://doi.org/10.1016/0304-3975(80)90003-1 · Zbl 0433.68017 |
| [26] | Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. 2010. Generalizing the powerset construction, coalgebraically. In FSTTCS (LIPIcs), Vol. 8. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 272-283. · Zbl 1245.68141 |
| [27] | Ana Sokolova and Harald Woracek. 2015. Congruences of convex algebras. Journal of Pure and Applied Algebra 219, 8 (2015), 3110-3148. https://doi.org/10.1016/j.jpaa.2014.10.005 · Zbl 1320.08003 |
| [28] | Ross Street. 2009. Weak distributive laws. Theory and Applications of Categories 22, 12 (2009), 313-320. · Zbl 1201.18004 |
| [29] | Regina Tix, Klaus Keimel, and Gordon Plotkin. 2009. Semantic Domains for Combining Probability and Non-Determinism. Electronic Notes in Theoretical Computer Science 222 (2009), 3-99. https://doi.org/10.1016/j.entcs.2009.01.002 · Zbl 1271.68005 |
| [30] | Daniele Varacca. 2003. Probability, Nondeterminism and Concurrency: Two Denotational Models for Probabilistic Computation. Technical Report. PhD thesis, Univ. Aarhus, 2003. BRICS Dissertation Series. |
| [31] | Daniele Varacca and Glynn Winskel. 2006. Distributing probability over non-determinism. Mathematical Structures in Computer Science 16, 1 (2006), 87-113. https://doi.org/10.1017/S0960129505005074 · Zbl 1093.18002 |
| [32] | M. Zwart and D. Marsden. 2019. No-Go Theorems for Distributive Laws. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, Los Alamitos, CA, USA, 1-13. https://doi.org/10.1109/LICS.2019.8785707 · Zbl 07471702 |
| [33] | T. Šwirszcz. 1974. Monadic functors and convexity. Bulletin de l’Académie Polonaise des Sciences, Ser. Sci. Math. Astronom. Phys. 22 (1974), 39-42. https://www.fuw.edu.pl/ kostecki/scans/swirszcz1974.pdf · Zbl 0276.46036 |
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.
