Speaker: Adam Bjorndahl (Carnegie Mellon University, Pittsburgh)
Date and Time: Thursday, October 19th 2017, 16:00-17:30
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: The Epistemology of Nondeterminism.
Abstract. Propositional dynamic logic (PDL) is a framework for reasoning about nondeterministic program execution. In this setting, nondeterminism is taken as a primitive: a program is nondeterministic iff it has multiple possible outcomes. But what is the sense of “possibility” at play here? This talk explores an epistemic interpretation: working in an enriched logical setting, we represent nondeterminism as a relationship between a program and an agent deriving from the agent’s (in)ability to adequately measure the dynamics of the program execution. More precisely, using topology to capture the observational powers of an agent, we define the nondeterministic outcomes of a given program execution to be those outcomes that the agent is unable to rule out in advance, so that nondeterminism is realized, loosely speaking, as discontinuity in the observation topology. This allows us to embed PDL into (dynamic) topological (subset space) logic, laying the groundwork for a deeper investigation into the epistemology (and topology) of nondeterminism.