Modal Logics for Continuous Dynamics
Jennifer M. Davoren · 1997
This work is a formal investigation of a number of bimodal and polymodal logics built on a base of propositional S4, and is a contribution to the theory of hybrid control systems. It is the first stage of a larger project of developing logics for the design and verification of such systems. A hybrid control system is a network of finite-state digital machines which act on and react to a dynamically changing environment, where such environments may have mixed analog and digital states. Following Nerode, I look to topology to provide a mediating link between the analog and digital worlds; S4 is taken as a logical foundation since from Tarski and McKinsey, it is the logic of topology. The base logic S4F adds to the $\square$ (topological interior) of S4 a modality (a) for representing the effect of an action in an environment; (a) is interpreted by a total function. In this logic, the continuity of a function with respect to a topology is expressible. In the second stage of this study, a fragment of deterministic propositional dynamic logic DPDL is overlaid on S4F to produce a new modal dynamic logic. In the resulting logic, called TPDL (topological propositional dynamic logic), atomic actions are interpreted by continuous functions, and complex actions are formed under the Kleene operations of composition, choice and iteration. Both a Tarski-style topological semantics and a Kripke semantics are presented for the logics. Building on work of Grzegorczyk, I identify a subclass of topological structures naturally dual to Kripke frames. Topologies in this class are such that every point is contained in a smallest open set. As argued by Nerode, these are precisely the topologies needed to give an account of analog-to-digital conversion. In addition to Hilbert-style axiomatizations, tableaux proof systems are presented for each of the logics and proved complete. The tableaux completeness proofs construct countable T$\sb0$ topologies whose elements are functional terms, in which the term constructor functions are continuous. Finite quotients of the term model are obtained, so establishing the decidability of each of the logics.