Dexter Kozen (Cornell University) Talk - Irif's Distinguished Talk Series

On December 3, 2024 IRIF welcomed Dexter Kozen (Cornell University) for a talk about "Probability and Angelic Nondeterminism with Multiset Semantics" (joint work with Shawn Ong and Stephanie Ma)
Abstract: Many modern computational systems involve both probability and nondeterminism, but the combination of the two in a formal logic is a notoriously challenging problem. One would like to reason about the correctness of programs involving constructs for both probabilistic and nondeterministic choice, but it is known that the standard way of modeling nondeterministic choice as a set of possibilities does not interact well with probabilistic choice, chiefly due to the lack of a suitable distributive law between the two. Many researchers over the years have grappled with this issue and proposed a variety of workarounds.
In this talk I will describe an alternative approach that models nondeterministic choice as a multiset operator instead of a set operator. It turns out that this simple change makes everything work much more smoothly, as there is a distributive law between probability and multisets. I will describe a class of probabilistic automata with nondeterminism modeled by multisets, along with a corresponding class of expressions analogous to regular expressions in this context, and show that they are equivalent in expressive power. In these models, an input string is not just accepted with some probability, but accepted with some finite multiplicity with some probability. I will give several examples and describe exactly why multisets work where sets do not.
__________________________
BIOGRAPHY
Dexter Kozen is the Joseph Newton Pew, Jr. Professor Emeritus at Cornell University. He received his undergraduate degree from Dartmouth College in mathematics in 1974 and his PhD from Cornell in computer science in 1977. After working as a member of the research staff at the IBM Thomas J. Watson Research Center for several years, he returned to Ithaca to join the Cornell faculty in computer science in 1985. He is a former Guggenheim fellow and a fellow of the Association of Computing Machinery, the American Association for the Advancement of Science, and the European Association of Theoretical Computer Science. He is a recipient of several awards for his research, including the 2016 EATCS Award, the 2016 IEEE W. Wallace McDowell Award, and the 2022 Alonzo Church Award. Kozen's research interests span a variety of topics on the boundary of computer science and mathematics: design and analysis of algorithms, computational complexity theory, complexity of decision problems in logic and algebra, and logics and semantics of programming languages. He is the author of over 200 research articles and four books.
Dexter lives in Ithaca with his wife Frances, a Senior Lecturer in Human Centered Design in the College of Human Ecology at Cornell. They have three sons and five grandchildren. For leisure activities, Dexter enjoys music of all types, but especially modern rock. He also enjoys sports, especially rugby, ice hockey, and skiing.