Fixed Point Logics and Definable Topological Properties

0563276 - ÚI 2023 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Fernández-Duque, David - Gougeon, P.
Fixed Point Logics and Definable Topological Properties.
Lecture Notes in Computer Science. In: Logic, Language, Information, and Computation. Cham: Springer, 2022 - (Ciabattoni, A.; Pimentel, E.; de Queiroz, R.), Roč. 13468 (2022), s. 36-52. Lecture Notes in Computer Science, 13468. ISBN 978-3-031-15297-9. ISSN 0302-9743.
[WoLLIC 2022: International Workshop on Logic, Language, Information, and Computation /28./. Iași (RO), 20.09.2022-23.09.2022]
Institucionální podpora: RVO:67985807
Klíčová slova: Mu-calculus * Expressivity * Topological semantics
Obor OECD: Pure mathematics

Modal logic enjoys topological semantics that may be traced back to McKinsey and Tarski, and the classification of topological spaces via modal axioms is a lively area of research. In the past two decades, there has been interest in extending topological modal logic to the language of the mu-calculus, but previously no class of topological spaces was known to be mu-calculus definable that was not already modally definable. In this paper we show that the full mu-calculus is indeed more expressive than standard modal logic, in the sense that there are classes of topological spaces (and weakly transitive Kripke frames) which are mu-definable, but not modally definable. The classes we exhibit satisfy a modally definable property outside of their perfect core, and thus we dub them imperfect spaces. We show that the mu-calculus is sound and complete for these classes. Our examples are minimal in the sense that they use a single instance of a greatest fixed point.
Trvalý link: https://hdl.handle.net/11104/0337431