Formalizing a Seligman-Style Tableau System for Hybrid Logic

Asta Halkjær From

Research output: Contribution to journalJournal articleResearchpeer-review

35 Downloads (Pure)


This work is a formalization of soundness and completeness proofs for a Seligman-style tableau system for hybrid logic. The completeness result is obtained via a synthetic approach using maximally consistent sets of tableau blocks. The formalization differs from previous work [1, 2] in a few ways. First, to avoid the need to backtrack in the construction of a tableau, the formalized system has no unnamed initial segment, and therefore no Name rule. Second, I show that the full Bridge rule is admissible in the system. Third, I start from rules restricted to only extend the branch with new formulas, including only witnessing diamonds that are not already witnessed, and show that the unrestricted rules are admissible. Similarly, I start from simpler
versions of the @-rules and show that these are sufficient. The GoTo rule is restricted using a notion of potential such that each application consumes potential and potential is earned through applications of the remaining rules. I show that if a branch can be closed then it can be closed starting from a single unit. Finally, Nom is restricted by a fixed set of allowed nominals. The resulting system should be terminating.
Original languageEnglish
Book seriesArchive of Formal Proofs
Number of pages34
Publication statusPublished - 2021


Dive into the research topics of 'Formalizing a Seligman-Style Tableau System for Hybrid Logic'. Together they form a unique fingerprint.

Cite this