Dawar, A. ; Otto, Martin (2005)
Modal characterisation theorems over special classes of frames.
20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05). Chicago, IL, USA (26.06.2005-29.06.2005)
doi: 10.1109/LICS.2005.27
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (Abstract)
We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem's theorem, which says that a first-order formula is invariant under bisimulation if and only if it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes -for instance, rooted connected frames, well-founded frames, finite rooted connected frames, finite transitive frames, finite equivalence frames - as these are not elementary. Instead we develop and extend the game-based analysis (first-order Ehrenfeucht-Fraisse versus bisimulation games) over such classes and provide bisimulation preserving model constructions within these classes.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2005 |
| Autor(en): | Dawar, A. ; Otto, Martin |
| Art des Eintrags: | Bibliographie |
| Titel: | Modal characterisation theorems over special classes of frames |
| Sprache: | Englisch |
| Publikationsjahr: | 2005 |
| Ort: | Piscataway |
| Verlag: | IEEE |
| Buchtitel: | 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05) |
| Veranstaltungstitel: | 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05) |
| Veranstaltungsort: | Chicago, IL, USA |
| Veranstaltungsdatum: | 26.06.2005-29.06.2005 |
| DOI: | 10.1109/LICS.2005.27 |
| Kurzbeschreibung (Abstract): | We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem's theorem, which says that a first-order formula is invariant under bisimulation if and only if it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes -for instance, rooted connected frames, well-founded frames, finite rooted connected frames, finite transitive frames, finite equivalence frames - as these are not elementary. Instead we develop and extend the game-based analysis (first-order Ehrenfeucht-Fraisse versus bisimulation games) over such classes and provide bisimulation preserving model constructions within these classes. |
| Fachbereich(e)/-gebiet(e): | 04 Fachbereich Mathematik |
| Hinterlegungsdatum: | 20 Nov 2008 08:22 |
| Letzte Änderung: | 10 Jan 2025 09:25 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum