Terminating Hybrid Tableaus for Ordered Models Yuki Nishimura Abstract Hybrid logic extends modal logic with special propositions called nominals, each of which is true at only one state in a model. This enables us to describe some properties of binary relations, such as irreflexivity and anti-symmetry, which are essential to treat partial orders. We present terminating tableau calculi complete with respect to some classes of models whose accessibility relations are strictly partially ordered, unbounded strictly partially ordered, partially ordered, strictly totally ordered, and totally ordered. Keywords: Modal logic, hybrid logic, tableau calculus, decision procedure, bulldozing, partial order, total order. 1 Introduction 1.1 Background and Results How does time flow? Prior formalized the tense in natural language using modal logic, which he named tense logic [ 15 ] . Since then, logics dealing with time have been broadly studied under the name of temporal logic . One feature of temporal logic is that transitivity is often imposed on the structure. Indeed, Goldblatt’s textbook [ 10 ] states: “But it is natural also to require a temporal ordering to be transitive.” In addition, temporal logics, such as LTL and CTL, handle ordered structures in reasoning about time (see also [ 8 , 11 ] ). Blackburn [ 3 ] extended Prior’s tense logic by introducing nominal tense logic , which incorporates nominals —propositional variables that are true in exactly one state. This addition allows for defining properties of binary relations, such as irreflexivity, asymmetry, and anti-symmetry, which cannot be expressed in basic modal logic. The paper introduced axioms for these properties and proved the completeness and decidability of logics associated with various order structures, including partial and total orders. Notably, the logic \mathbf{I4D} , corresponding to models with unbounded strict partial orders, remains decidable despite lacking the finite frame property. Blackburn later named this framework hybrid logic , which has since been extensively studied. For more details on hybrid logic, see [ 4 , 2 , 1 , 12 , 7 ] . In this paper, we construct tableau calculi \mathbf{TAB}_{\mathbf{I4}} , \mathbf{TAB}_{\mathbf{I4D}} , \mathbf{TAB}_{\textbf{PO}} , \mathbf{TAB}_{\textbf{STO}} , and \mathbf{TAB}_{\textbf{TO}} for models with strict partial orders, unbounded strict partial orders, partial orders, strict total orders, and total orders, respectively, and demonstrate their completeness and termination. These five systems correspond to the logics \mathbf{I4} , \mathbf{I4D} , and \mathbf{PO} , \mathbf{LIN}_{s} , and \mathbf{LIN} in [ 3 ] , respectively. The key ingredient of our proof is the method called bulldozing , which destroys undesirable states in the model and transforms them into a desirable form. It is important to note that bulldozing transitive models can result in the construction of infinite models. However, even if the counterexample model is infinite, the existence of such a model can be demonstrated through a finite procedure. From this, we can provide a distinct proof of the decidability of the logics, as in [ 3 ] . 1.2 Related Works Here, we review the previous study of tableau calculi for hybrid logic. A tableau calculus for hybrid logic was first proposed by Tzakova [ 17 ] as a prefixed tableau calculus. The tableau calculus proposed by Bolander and Blackburn [ 5 ] is a complete and terminating system for the basic hybrid logic based on \mathbf{K} . Their later research [ 6 ] extended these results, proposing complete and terminating tableau calculi for a wider range of hybrid logics. Using this approach, we can now construct complete and terminating tableau calculi for the hybridized versions of the 15 logics belonging to the so-called modal cube [ 9 , §8] . However, there are tableau calculi for other logics that have not yet been studied. In particular, the difficulty of \mathbf{I4D} is believed to stem from its lack of the finite frame property. In fact, Bolander and Blackburn [ 6 ] describe this challenge as follows. But then we are faced with the task of combining such conditions as (irr), (sym), (asym), (antisym), (intrans), (uniq) and (tree) with (trans), and here matters are likely to be much trickier. Certainly loop-checks will usually be required, but it is unclear to us at present what kinds of general results we can hope for here, or what languages we can prove them for. To give an idea of the difficulties involved, note that even such a simple looking combination as (trans) + (irr) does not have the finite frame property (consider the formula F\top\land GF\top , for example). Takagi and the author [ 13 ] constructed a tableau calculus for hybrid logic corresponding to undirected graphs. To prove completeness, it was necessary to use not only traditional loop-checking but also model surgery. The methods used in that work are the basis for the proofs in this paper. 1.3 Organization of the Paper The rest of this paper is organized as follows. Section 2 reviews the semantics of hybrid logic and basic tableau calculus proposed in [ 5 ] . Section 3 introduces a tableau calculus \mathbf{TAB}_{\mathbf{I4}} for strict partially ordered models. Sections 4 and 5 give proofs of completeness and termination for tableau calculi \mathbf{TAB}_{\mathbf{I4D}} and \mathbf{TAB}_{\textbf{PO}} corresponding to unbounded strict partially ordered models and partially ordered models, respectively. Section 6 shows the completeness and termination for a tableau calculus \mathbf{TAB}_{\textbf{TO}} with respect to the totally ordered models and indicates the proof of that of \mathbf{TAB}_{\textbf{STO}} corresponding to strictly totally ordered models. Section 7 outlines some future prospects of this research. 2 Preliminaries 2.1 Kripke Semantics for Hybrid Logic Here, we review a hybrid logic with the satisfaction operators @_{i} . See [ 7 ] for more details on the semantics of hybrid logic. Definition 2.1 . We have a countably infinite set \mathbf{Prop} of propositional variables and another countably infinite set \mathbf{Nom} of nominals , which is disjoint from \mathbf{Prop} . The formulas \varphi of hybrid logic are defined inductively as follows: \displaystyle\varphi\Coloneqq p\mid i\mid\neg\varphi\mid\varphi\land\varphi\mid\varphi\lor\varphi\mid\Diamond\varphi\mid\Box\varphi\mid@_{i}\varphi, where p\in\mathbf{Prop} and i\in\mathbf{Nom} . We write \varphi\rightarrow\psi to mean \neg\varphi\lor\psi . Definition 2.2 . A Kripke model \mathcal{M}=(W,R,V) , or merely model , is defined as follows: • W is a non-empty set. • R is a binary relation on W . • V is a function V:\mathbf{Prop}\ \cup\ \mathbf{Nom}\to\mathcal{P}(W) such that V(i)=\{w\}\ \text{for some}\ w\in W for each i\in\mathbf{Nom} , where \mathcal{P}(W) denotes the powerset of W . Furthermore, we call a tuple \mathcal{F}=(W,R) that satisfies the first two conditions above a Kripke frame (or, shortly, frame ). This definition reflects the key property of nominals: each nominal is true in only one world. This paper uses wRv to mean (w,v)\in R , and i^{V} to mean the world w\in W such that V(i)=\{w\} . Definition 2.3 . Given a model \mathcal{M} , a possible world w in \mathcal{M} , and a formula \varphi , the satisfaction relation \mathcal{M},w\models\varphi is defined inductively as follows: \displaystyle\mathcal{M},w\models p \displaystyle\iff w\in V(p),\text{where}\ p\in\mathbf{Prop} \displaystyle\mathcal{M},w\models i \displaystyle\iff w=i^{V},\text{where}\ i\in\mathbf{Nom} \displaystyle\mathcal{M},w\models\neg\varphi \displaystyle\iff\text{not}\ \mathcal{M},w\models\varphi\ (\mathcal{M},w\not\models\varphi) \displaystyle\mathcal{M},w\models\varphi\land\psi \displaystyle\iff\mathcal{M},w\models\varphi\ \text{and}\ \mathcal{M},w\models\psi \displaystyle\mathcal{M},w\models\varphi\lor\psi \displaystyle\iff\mathcal{M},w\models\varphi\ \text{or}\ \mathcal{M},w\models\psi \displaystyle\mathcal{M},w\models\Diamond\varphi \displaystyle\iff\text{there exists}\ v\ \text{such that}\ wRv\ \text{and}\ \mathcal{M},v\models\varphi \displaystyle\mathcal{M},w\models\Box\varphi \displaystyle\iff\text{for all}\ v,\ \text{if}\ wRv,\ \text{then}\ \mathcal{M},v\models\varphi \displaystyle\mathcal{M},w\models@_{i}\varphi \displaystyle\iff\mathcal{M},i^{V}\models\varphi. Definition 2.4 . A formula \varphi is said to be valid (denoted by \models\varphi ) if \mathcal{M},w\models\varphi holds for all models \mathcal{M} and all of its worlds w . For simplicity, the rest of the paper deals only with the negation normal form (NNF, in short) of formulas. For the satisfaction operators, a formula \neg@_{i}\varphi is equivalent to @_{i}\neg\varphi . That is, for any model and its possible world w , a formula \varphi , and a nominal i\in\mathbf{Nom} , we have \mathcal{M},w\models\neg@_{i}\varphi\iff\mathcal{M},w\models@_{i}\neg\varphi. Transformations to the NNF involving Boolean and modal operators can be done in the usual way. In the rest of this paper, we only deal with NNF formulas. If we write \neg\varphi , we assume it as the abbreviation of an NNF of it. At last, we review some properties of a binary relation. Definition 2.5 . Given a binary relation R , we define the following properties: \displaystyle R\text{ is \emph{serial} } \displaystyle\iff\forall x\exists y.xRy \displaystyle R\text{ is \emph{reflexive} } \displaystyle\iff\forall x.xRx \displaystyle R\text{ is \emph{irreflexive} } \displaystyle\iff\forall x.\neg(xRx) \displaystyle R\text{ is \emph{anti-symmetric} } \displaystyle\iff\forall xy.(xRy\ \&\ yRx\implies x=y) \displaystyle R\text{ is \emph{transitive} } \displaystyle\iff\forall xyz.(xRy\ \&\ yRz\implies xRz) \displaystyle R\text{ is \emph{trichotomous}} \displaystyle\iff\forall xy.(xRy\text{ or }yRx\text{ or }x=y) \displaystyle R\text{ is \emph{total}} \displaystyle\iff\forall xy.(xRy\text{ or }yRx). Also, we call some types of binary relations by special names: • R is a strict partial order if it is both irreflexive and transitive. • R is an unbounded strict partial order if it is serial, irreflexive, and transitive. • R is a partial order if it is reflexive, anti-symmetric, and transitive. • R is a strict total order if it is irreflexive, transitive, and trichotomous. • R is a partial order if it is reflexive, anti-symmetric, transitive, and total. Given a model \mathcal{M}=(W,R,V) , we say that \mathcal{M} is irreflexive if R is irreflexive. We use the same terminology for other properties of a binary relation. Moreover, we define some classes of models: • \mathcal{M} is a strict partially ordered model , or an SPO model , if R is a strict partial order. • \mathcal{M} is an unbounded strict partially ordered model , or a USPO model , if R is an unbounded strict partial order. • \mathcal{M} is a partially ordered model , or a PO model , if R is a partial order. • \mathcal{M} is a strict totally ordered model , or an STO model , if R is a strict total order. • \mathcal{M} is a totally ordered model , or an TO model , if R is a total order. 2.2 Basic Tableau Calculus \mathbf{K(@)} is an axiomatization of hybrid logic with an operator @ , based on the minimal normal modal logic \mathbf{K} (see [ 2 ] for more details on the axiomatization of hybrid logic). We write \mathbf{TAB} to indicate the tableau calculus for hybrid logic \mathbf{K(@)} . Our presentation is based on [ 5 ] . Definition 2.6 . A tableau is a well-founded tree constructed in the following way: • Start with a formula of the form @_{i}\varphi (called the root formula ), where i\in\mathbf{Nom} does not occur in the formula \varphi . • For each branch, extend it by applying rules (see Definition 1 ). However, we can no longer add any formula in a branch if at least one of the following conditions is satisfied: – Every new formula generated by applying any rule already exists in the branch. – The branch is closed (Definition 2.7 defines what a closed branch is). If a formula \varphi occurs in a branch \Theta , we write \varphi\in\Theta . Definition 2.7 . A branch \Theta of a tableau is closed if there exists a formula \varphi and a nominal i such that @_{i}\varphi,@_{i}\neg\varphi\in\Theta . We say that \Theta is open if it is not closed. A tableau is called closed if all branches in the tableau are closed. Definition 2.8 . We provide the rules of \mathbf{TAB} in Figure 1 . In these rules, the formulas above the line show the formulas that have already occurred in the branch, and the formulas below the line show the formulas that will be added to the branch. The vertical line in the [\lor] means that the branch splits to the left and right. \displaystyle@_{j}j@_{i}\neg j\qquad@_{i}\psi@_{i}\varphi@_{i}(\varphi\land\psi)\qquad@_{i}\varphi\mid@_{i}\psi@_{i}(\varphi\lor\psi) \displaystyle@_{j}\varphi@_{i}\Diamond j@_{i}\Diamond\varphi\qquad@_{j}\varphi@_{i}\Diamond j@_{i}\Box\varphi\qquad@_{j}\varphi@_{i}@_{j}\varphi\qquad@_{j}\varphi@_{i}j@_{i}\varphi *1: j\in\mathbf{Nom} does not occur in the branch above. *2: This rule can be applied only once per formula. *3: The formula above the line is not an accessibility formula. Here, an accessibility formula is the formula of the form @_{i}\Diamond j generated by [ \Diamond ], where j is a new nominal. Figure 1: The rules of \mathbf{TAB} Definition 2.9 . Given a formula \varphi , we say that \varphi is provable in \mathbf{TAB} if there is a closed tableau whose root formula is @_{i}\neg\varphi , where i\in\mathbf{Nom} does not occur in \varphi . \displaystyle 1.\ @_{i}(\Diamond j\land@_{j}p\land\Box\neg p) \displaystyle 2.\ @_{i}\Diamond j \displaystyle[\land] \displaystyle 3.\ @_{i}(@_{j}p\land\Box\neg p) \displaystyle[\land] \displaystyle 4.\ @_{i}@_{j}p \displaystyle[\land] \displaystyle 5.\ @_{i}\Box\neg p \displaystyle[\land] \displaystyle 6.\ {@_{i}\Diamond k}^{*} \displaystyle[\Diamond] \displaystyle 7.\ @_{k}j \displaystyle[\Diamond] \displaystyle 8.\ @_{j}p \displaystyle[@] \displaystyle 9.\ @_{k}\neg p \displaystyle[\Box] \displaystyle 10.\ @_{j}\neg p \displaystyle[\mathit{Id}] ✗ Figure 2: A closed tableau of \mathbf{TAB} . Formulas with ∗ are accessibility formulas. Figure 2 is an example of a tableau proving the hybrid formula (\Diamond j\land@_{j}p)\rightarrow\Diamond p . Here is an intuitive explanation of this formula: if there is a reachable world named j and a formula p holds in the world j , then there is a reachable world in which p holds. It starts from @_{i}(\Diamond j\land@_{j}p\land\Box\neg p) , whose subformula \Diamond j\land@_{j}p\land\Box\neg p is an NNF of the formula we want to prove. There are ten formulas in this branch; however, we can shorten this proof tree by applying [\Box] directly to the second and fifth formulas and deriving @_{j}\neg p . Bolander and Blackburn [ 5 ] showed two significant properties of \mathbf{TAB} . One is the termination property, and the other is completeness. Theorem 2.10 . The tableau calculus \mathbf{TAB} has the termination property . That is, for every formula \varphi , the tableau in \mathbf{TAB} for \varphi is finite. Theorem 2.11 . The tableau calculus \mathbf{TAB} is complete for the class of all frames. 3 Tableau Calculus for Strict Partial Order In this section, we define the tableau calculus \mathbf{TAB}_{\mathbf{I4}} corresponding to the SPO models. 3.1 Definition First of all, we define the tableau calculus \mathbf{TAB}_{\mathbf{I4}} . We then give the details of the definition. Definition 3.1 . The tableau calculus \mathbf{TAB}_{\mathbf{I4}} is constructed by replacing [\neg] with [\mathit{Eq}] and adding the rules [\mathit{Irr}] and [\mathit{Trs}] , and a restriction (\mathcal{D}) to \mathbf{TAB} . The rules [\mathit{Eq}] , [\mathit{Irr}] , and [\mathit{Trs}] are shown in Figure 3 . The restriction (\mathcal{D}) is as follows. (\mathcal{D}) The rule [\Diamond] can only be applied to a formula @_{i}\Diamond\varphi on a branch \Theta if i is a quasi-urfather (the quasi-urfather is defined later in Definition 3.8 ). We introduce the two rules [\mathit{Irr}] and [\mathit{Trs}] in order to express the irreflexivity and transitivity of models in the tableau calculus. By the rule [\mathit{Irr}] , we add a formula @_{i}\Box\neg i , which means “we cannot reach the world named i from the world i itself.” The rule [\mathit{Trs}] corresponds to the fact that if a formula \Box\varphi holds in a world w , then \Box\varphi also holds in all worlds reachable from w . In addition, we replace [\neg] with a new rule [\mathit{Eq}] . This rule allows a formula of the form @_{i}i to be added at any time for a nominal i that already appears on the branch. The rule is named after the initial letters of “equality” because it can be used freely, much like introducing the term x=x in first-order logic. This change makes it easier to prove some lemmas. \displaystyle@_{i}i\quad@_{i}\Diamond j\quad@_{i}\Diamond i@_{i}\Box\neg i\quad@_{j}\Box\varphi@_{i}\Diamond j@_{i}\Box\varphi \displaystyle@_{i}\Box(i\lor\Box\neg i)\quad@_{i}\Diamond j\mid@_{j}\Diamond i\quad@_{i}\Diamond j\mid@_{i}j\mid@_{j}\Diamond i *1: i,j has already occurred in the branch. *2: i is already present in the branch, while j is not. *3: This rule can be applied only once per nominal i . *4: The formula(s) of the form @_{i}\Diamond j below the line is (are) accessibility formula(s). Figure 3: Additional rules Then, what is the role of (\mathcal{D}) ? As pointed out by [ 6 ] , the addition of [\mathit{Trs}] enables us to make an infinite branch, as shown in Figure 4 . To address the problem, we introduce a loop-checking method to add a restriction (\mathcal{D}) to the tableau calculus. This was originally invented to deal with labeled modal tableau with inverse modalities in [ 5 , Section 5.2] . Bolander and Blackburn also showed that this restriction works well with \mathbf{TAB}+[\mathit{Trs}] in [ 6 , Section 7] . \displaystyle 1.\ @_{i}(\Diamond p\land\Box\Diamond p) \displaystyle 2.\ @_{i}\Diamond p \displaystyle[\land] \displaystyle 3.\ @_{i}\Box\Diamond p \displaystyle[\land] \displaystyle 4.\ {@_{i}\Diamond j}^{*} \displaystyle[\Diamond] \displaystyle 5.\ @_{j}p \displaystyle[\Diamond] \displaystyle 6.\ @_{j}\Diamond p \displaystyle[\Box] \displaystyle 7.\ @_{j}\Box\Diamond p \displaystyle[\mathit{Trs}] \displaystyle 8.\ {@_{j}\Diamond k}^{*} \displaystyle[\Diamond] \displaystyle 9.\ @_{k}p \displaystyle[\Diamond] \displaystyle 10.\ @_{k}\Diamond p \displaystyle[\Box] \displaystyle 11.\ @_{k}\Box\Diamond p \displaystyle[\mathit{Trs}] \displaystyle 12.\ {@_{k}\Diamond l}^{*} \displaystyle[\Diamond] \displaystyle 13.\ @_{l}p \displaystyle[\Diamond] \displaystyle 14.\ @_{l}\Diamond p \displaystyle[\Box] \displaystyle 15.\ @_{l}\Box\Diamond p \displaystyle[\mathit{Trs}] \displaystyle\qquad\vdots Figure 4: Non-terminating tableau of \mathbf{TAB} with [\mathit{Trs}] . Formulas with ∗ are accessibility formulas. To understand (\mathcal{D}) , it is necessary to prepare several concepts. Our goal is to define the concept of quasi-urfather , introduced in [ 5 , §5.2] . Intuitively, the quasi-urfather is a representative of the redundant nominals. For example, in Figure 4 , the nominals j,k,l,\ldots play the same role (the worlds they point to verify the same propositions, p , \Diamond p , and \Box\Diamond p ). The quasi-urfather is a representative of these redundant nominals. Definition 3.2 . Given two formulas of the form @_{i}\varphi and @_{j}\psi , @_{i}\varphi is a prefixed subformula of @_{j}\psi if \varphi is a subformula of \psi . Lemma 3.3 . Let \Theta be a branch of a tableau. For every formula of the form @_{i}\varphi in \Theta , at least one of the following conditions is satisfied: • It is a prefixed subformula of the root formula of \Theta . • It is an accessibility formula. • It is a prefixed subformula of @_{j}\Box\neg j for some j . Proof. By induction on the number of applied rules. We provide the proof only for the cases [\mathit{Irr}] and [\mathit{Trs}] . The other cases are left to the reader. [\mathit{Irr}] The formula we add by [\mathit{Irr}] is the very formula of the form @_{j}\Box\neg j for some j that has already occurred in \Theta . [\mathit{Trs}] @_{j}\Box\varphi is a prefixed subformula of @_{i}\Box\varphi . By the induction hypothesis, @_{i}\Box\varphi is either a prefixed subformula of the root formula or the formula of the form @_{i}\Box\neg k . Therefore, @_{j}\Box\varphi is a prefixed subformula of either the root formula or a formula @_{k}\Box\neg k . ∎ Next, we define the set T^{\Theta}(i) for each nominal i occurring in a branch \Theta . This set consists of the formulas in \Theta that have the prefix @_{i} and contain information related to the root formula of \Theta . This definition differs from the one in the proof in [ 5 ] , which defines T^{\Theta}(i) as the set T_{1}^{\Theta}(i) below. This small change has a big effect on coping with both the loop-checking method and irreflexivity. Definition 3.4 . Let \Theta be a branch of a tableau. For every nominal i occurring in \Theta , the set T^{\Theta}(i) is a union of T_{1}^{\Theta}(i) and T_{2}^{\Theta}(i) , where: • T_{1}^{\Theta}(i) is the set of formulas \varphi such that @_{i}\varphi\in\Theta is a prefixed subformula of the root formula of \Theta . • T_{2}^{\Theta}(i) is the set of formulas \psi such that @_{i}\psi\in\Theta is a prefixed subformula of @_{j}\Box\neg j for some j occurring in the root formula of \Theta . Lemma 3.5 . For all i occurring in \Theta , T^{\Theta}(i) is finite. Proof. T_{1}^{\Theta}(i) is finite because for each i , the number of prefixed subformulas of the root formula of \Theta is finite. In turn, T_{2}^{\Theta}(i) is finite because the number of nominals occurring in the root formula of \Theta is finite. ∎ Using this definition, we define the concept of twins , a tool for identifying nominals that perform the same role. Definition 3.6 . Let \Theta be a branch of a tableau. The nominals i,j are twins in \Theta if T^{\Theta}(i)=T^{\Theta}(j) . Next, we define a generating relation between nominals. If j is introduced by applying [\Diamond] to @_{i}\Diamond\varphi , we say that j is generated by i . Since a new nominal is generated if and only if an accessibility formula is added, we can use the following definition. Definition 3.7 . Let \Theta be a tableau branch, and let i and j be nominals occurring in \Theta . We say that j is generated from i (denoted by i\prec_{\Theta}j ) if j is introduced by applying [\Diamond] to @_{i}\Diamond j . In the case of \mathbf{TAB} , this definition is equivalent to the existence of an accessibility formula @_{i}\Diamond j in \Theta . However, later in this paper, we will deal with rules that add accessibility formulas directly without using [\Diamond] —for example, [\mathit{Ref}] and [\mathit{Tot}] . In such cases, this equivalence no longer holds. Based on these preparations, we can give a precise definition of the quasi-urfather. Definition 3.8 . We call a nominal i quasi-urfather on \Theta if there are no twins j,k such that j\neq k and j,k\prec_{\Theta}^{*}i , where \prec_{\Theta}^{*} denotes a reflexive and transitive closure of \prec_{\Theta} . Now, we can understand the statement of (\mathcal{D}) . Before we show the termination property, let us show an example of a tableau whose generation terminates owing to (\mathcal{D}) . Example 3.9 . With (\mathcal{D}) , the tableau generation in Figure 4 stops before adding the twelfth formula @_{k}\Diamond l . In this branch, up to the eleventh formula @_{k}\Box\Diamond k , nominals j and k are twins, since T^{\Theta}(j)=T^{\Theta}(k)=\{p,\Diamond p,\Box\Diamond p\} . Then k is not a quasi-urfather, so we can no longer apply [\Diamond] to the tenth formula @_{k}\Diamond p . To prevent the tableau generation from ending due to (\mathcal{D}) , it is possible to intentionally adjust the application order of the rules to avoid making nominals twins. However, such attempts will eventually fail. For example, in Figure 5 , the restriction of (\mathcal{D}) is circumvented by applying [\Diamond] to the tenth formula @_{k}\Diamond p , generating a new nominal l (consider that j and k are not twins in the branch up to the tenth formula). However, to generate further nominals, the fourteenth formula @_{l}\Diamond p is necessary, at which point l ceases to be a quasi-urfather. This is because j and k are now twins, and j\prec_{\Theta}k\prec_{\Theta}l holds. \displaystyle 1.\ @_{i}(\Diamond p\land\Box\Diamond p) \displaystyle 2.\ @_{i}\Diamond p \displaystyle[\land] \displaystyle 3.\ @_{i}\Box\Diamond p \displaystyle[\land] \displaystyle 4.\ {@_{i}\Diamond j}^{*} \displaystyle[\Diamond] \displaystyle 5.\ @_{j}p \displaystyle[\Diamond] \displaystyle 6.\ @_{j}\Diamond p \displaystyle[\Box] \displaystyle 7.\ @_{j}\Box\Diamond p \displaystyle[\mathit{Trs}] \displaystyle 8.\ {@_{j}\Diamond k}^{*} \displaystyle[\Diamond] \displaystyle 9.\ @_{k}p \displaystyle[\Diamond] \displaystyle 10.\ @_{k}\Diamond p \displaystyle[\Box] \displaystyle 11.\ {@_{k}\Diamond l}^{*} \displaystyle[\Diamond] \displaystyle 12.\ @_{l}p \displaystyle[\Diamond] \displaystyle 13.\ @_{k}\Box\Diamond p \displaystyle[\mathit{Trs}] \displaystyle 14.\ @_{l}\Diamond p \displaystyle[\Box] Figure 5: Another example of tableau terminated due to (\mathcal{D}) (Formulas with ∗ are accessibility formulas.) 3.2 Termination Property Here, we show the termination property for \mathbf{TAB}_{\mathbf{I4}} . The proof can be carried out based on that for the tableau calculus for \mathbf{K4} in [ 6 ] . One reason is that none of the added rules freely introduce formulas containing \Diamond , and another is that the redefined T^{\Theta}(i) remains finite. Lemma 3.10 . Given a branch \Theta of a tableau, we define a structure G^{\Theta}=(N^{\Theta},\prec_{\Theta}) where: • N^{\Theta} is the set of nominals occurring in \Theta . • i\prec_{\Theta}j if j is generated by i (see Definition 3.7 ). Then, G^{\Theta} is a finite disjoint union of well-founded and finitely branching trees. Proof. See the proof of [ 5 , Lemma 6.4] . ∎ Lemma 3.11 . Let \Theta be a branch of a tableau. Then \Theta is infinite if and only if we have the following infinite sequence: i_{0}\prec_{\Theta}i_{1}\prec_{\Theta}\cdots. Proof. The right-to-left direction is straightforward. The other direction is proved from Lemma 3.10 along with König’s lemma. For more detail, see the proof of [ 5 , Lemma 6.5] . ∎ Theorem 3.12 . The tableau calculus \mathbf{TAB}_{\mathbf{I4}} has the termination property. Proof. This proof is written based on that of [ 5 , Theorem 5.8] . We show this theorem by reductio ad absurdum . Suppose there is an infinite branch \Theta . Then by Lemma 3.11 , there is an infinite sequence of nominals as follows: i_{0}\prec_{\Theta}i_{1}\prec_{\Theta}i_{2}\prec_{\Theta}\cdots. For \Theta and its root formula @_{i}\varphi , we define Q and n as follows: \displaystyle Q= \displaystyle\{\psi\mid\psi\text{ is a subformula of }\varphi\} \displaystyle\cup \displaystyle\{\psi\mid\psi\text{ is a subformula of }\Box\neg j\text{ where }j\text{ occurs in }@_{i}\varphi\} and n is the number of elements in Q . Also, let \Theta^{\prime} be a fragment of \Theta up to, but not including, the first occurrence of i_{2^{n}+1} . Then i_{2^{n}+1} is generated by applying [\Diamond] to some @_{i_{2^{n}}}\Diamond\varphi . Taking (\mathcal{D}) into consideration, i_{2^{n}} is a quasi-urfather. However, since all of T^{\Theta^{\prime}}(i_{0}),T^{\Theta^{\prime}}(i_{1}),\ldots,T^{\Theta^{\prime}}(i_{2^{n}}) are subsets of Q and n is the cardinality of Q , there exists a pair 0\leq l,m\leq 2^{n} such that T^{\Theta^{\prime}}(i_{l})=T^{\Theta^{\prime}}(i_{m}) by the pigeonhole principle. Therefore, we find the twins i_{l} and i_{m} such that i_{l},i_{m}\prec_{\Theta}^{*}i_{2^{n}} , but that contradicts that i_{2^{n}} is a quasi-urfather. ∎ 3.3 Completeness Once we construct a proof system, the next work is to show soundness and completeness. The soundness can be shown using faithful models (see, for example, [ 14 ] ). Then, we show that this tableau calculus is complete with respect to the class of SPO models. The basic strategy is the same as in [ 5 , Section 5.2] or [ 13 , Section 3.3] . That is, define identity urfathers , representative nominals in a branch, and use them to create a model from an open saturated branch of a tableau. Definition 3.13 . A branch \Theta of a tableau is saturated if every formula that can be generated by applying some rule already exists in \Theta . We call a tableau saturated if all of its branches are saturated. If \Theta is a saturated branch, the following conditions hold: • If @_{i}(\varphi\land\psi)\in\Theta , then @_{i}\varphi,@_{i}\psi\in\Theta . • If @_{i}\Diamond\varphi\in\Theta which is not an accessibility formula and i is a quasi-urfather, then there exists some j\in\mathbf{Nom} such that @_{i}\Diamond j,@_{j}\varphi\in\Theta . • If @_{i}\Box\varphi,@_{i}\Diamond j\in\Theta , then @_{j}\varphi\in\Theta and @_{j}\Box\varphi\in\Theta . • For all i occurring in \Theta , we have @_{i}\Box\neg i\in\Theta . Definition 3.14 . Let \Theta be a tableau branch and i a nominal occurring in \Theta . The identity urfather of i on \Theta (denoted by v_{\Theta}(i) ) is the earliest introduced nominal j satisfying the following conditions: 1. j is a twin of i . 2. j is a quasi-urfather. Moreover, we say that a nominal i is an identity urfather on \Theta if there is a nominal j such that v_{\Theta}(j)=i . Since not all nominals occurring in a branch have their identity urfather, we write i\in\mathrm{dom}(v_{\Theta}) if v_{\Theta}(i) exists for a nominal i . We show some properties about identity urfathers. Since their proof is the same as that in [ 13 , Lemma 5-9] , only the statements of the lemmas are described. Lemma 3.15 . Let \Theta be a branch of a tableau. Then, the following statements hold: (a) If i occurs in the root formula @_{i_{0}}\varphi_{0} of \Theta , then i\in\mathrm{dom}(v_{\Theta}) . (b) If i is a quasi-urfather on \Theta and i\prec_{\Theta}j , then j\in\mathrm{dom}(v_{\Theta}) . (c) If @_{i}\varphi\in\Theta is a prefixed subformula of the root formula of \Theta and i\in\mathrm{dom}(v_{\Theta}) , then @_{v_{\Theta}(i)}\varphi\in\Theta . (d) A nominal i is the identity urfather if and only if v_{\Theta}(i)=i . Moreover, if \Theta is saturated, the following statement holds. (e) If @_{i}j\in\Theta and i,j\in\mathrm{dom}(v_{\Theta}) , then v_{\Theta}(i)=v_{\Theta}(j) . Now, we construct a model from a tableau with an open branch. Definition 3.16 . Given an open saturated branch \Theta with a root formula @_{i_{0}}\varphi_{0} of a tableau in \mathbf{TAB}_{\mathbf{I4}} , a model \mathcal{M}^{\Theta}=(W^{\Theta},R^{\Theta},V^{\Theta}) is defined as follows: \displaystyle W^{\Theta} \displaystyle=\{i\mid i\text{ is an identity urfather on }\Theta\} \displaystyle R_{e}^{\Theta} \displaystyle=\{(v_{\Theta}(i),v_{\Theta}(j))\mid@_{i}\Diamond j\in\Theta\text{ and }i,j\in\mathrm{dom}(v_{\Theta})\} \displaystyle R^{\Theta} \displaystyle=(R_{e}^{\Theta})^{+} \displaystyle V^{\Theta}(p) \displaystyle=\{v_{\Theta}(i)\mid@_{i}p\in\Theta\},\text{ where }p\in\mathbf{Prop} \displaystyle V^{\Theta}(i) \displaystyle=\begin{cases}\{v_{\Theta}(i)\}&\text{if }i\in\mathrm{dom}(v_{\Theta})\\ \{i_{0}\}&\text{otherwise,}\end{cases}\text{ where }i\in\mathbf{Nom}. Here, R^{+} means the transitive closure of R . Then we obtain the following lemma, which ensures that if we have a tableau with a root formula @_{i_{0}}\varphi_{0} one of whose branches are open and saturated, there exists a model which falsifies \varphi_{0} . Lemma 3.17 . Let \Theta be an open saturated branch of a tableau in \mathbf{TAB}_{\mathbf{I4}} and @_{i}\varphi be a prefixed subformula of the root formula @_{i_{0}}\varphi_{0} of \Theta , where i\in\mathrm{dom}(v_{\Theta}) . Then we have the following proposition: \text{if }@_{i}\varphi\in\Theta,\text{ then }\mathcal{M}^{\Theta},v_{\Theta}(i)\models\varphi. In particular, \mathcal{M}^{\Theta},v_{\Theta}(i_{0})\models\varphi_{0} . Proof. By induction on the complexity of \varphi . Most of the proof is the same as in [ 13 ] , so we only show the case of \varphi=\Box\psi as it differs from the previous proof. Suppose that @_{i}\Box\psi\in\Theta , and take a nominal j\in\mathbf{Nom} such that v_{\Theta}(i)R^{\Theta}j . (If no such nominal exists, \mathcal{M}^{\Theta},v_{\Theta}(i)\models\Box\psi is straightforward.) Then by the definition of R^{\Theta} , there are nominals i_{1},i_{2},\ldots,i_{n} such that v_{\Theta}(i)R_{e}^{\Theta}i_{1}R_{e}^{\Theta}i_{2}R_{e}^{\Theta}\cdots R_{e}^{\Theta}i_{n}R_{e}^{\Theta}j. By the definition of R_{e}^{\Theta} , there are nominals j_{0},j_{1},\ldots,j_{n},k_{1},k_{2},\ldots,k_{n+1} such that v_{\Theta}(j_{0})=v_{\Theta}(i) , v_{\Theta}(j_{m})=v_{\Theta}(k_{m})=i_{m} for all 1\leq m\leq n , v_{\Theta}(k_{n+1})=j , and @_{j_{0}}\Diamond k_{1},@_{j_{1}}\Diamond k_{2},\ldots,@_{j_{n}}\Diamond k_{n+1}\in\Theta. From v_{\Theta}(j_{0})=v_{\Theta}(i) , we have @_{j_{0}}\Box\psi\in\Theta . Since \Theta is saturated, we have @_{k_{1}}\Box\psi\in\Theta by [\mathit{Trs}] . Then, @_{j_{1}}\Box\psi\in\Theta holds since j_{1} and k_{1} are twins. Repeating this, we have @_{j_{1}}\Box\psi,@_{j_{2}}\Box\psi,\ldots,@_{j_{n}}\Box\psi\in\Theta , and finally by [\Box] , @_{k_{n+1}}\psi\in\Theta . By the induction hypothesis, we obtain that \mathcal{M}^{\Theta},j\models\psi . Since we pick j arbitrarily, we have \mathcal{M},v_{\Theta}(i)\models\Box\psi . ∎ From the construction, the transitivity of a model \mathcal{M}^{\Theta} made from an open saturated branch \Theta is guaranteed. However, it is not the case that \mathcal{M}^{\Theta} is always irreflexive. We can check this fact with a simple example. Example 3.18 . Let \Theta be a branch in Figure 6 . Note that the root formula of \Theta is the same as that of Figure 4 ; however, it is open and saturated and terminates owing to (\mathcal{D}) since j and k are twins (we can check that T^{\Theta}(j)=T^{\Theta}(k)=\{p,\Diamond p,\Box\Diamond p,\neg i,\Box\neg i\} ). From the branch, we can construct a model \mathcal{M}^{\Theta}=(W^{\Theta},R^{\Theta},V^{\Theta}) as follows: \displaystyle W^{\Theta} \displaystyle=\{i,j\} \displaystyle R^{\Theta} \displaystyle=\{(i,j),(j,j)\} \displaystyle V^{\Theta}(p) \displaystyle=\{j\} \displaystyle V^{\Theta}(i) \displaystyle=\{i\}. However, this model has the reflexive world j . Figure 7 shows it graphically. \displaystyle 1.\ @_{i}(\Diamond p\land\Box\Diamond p) \displaystyle 2.\ @_{i}i \displaystyle[\mathit{Eq}] \displaystyle 3.\ @_{i}\Box\neg i \displaystyle[\mathit{Irr}] \displaystyle 4.\ @_{i}\Diamond p \displaystyle[\land] \displaystyle 5.\ @_{i}\Box\Diamond p \displaystyle[\land] \displaystyle 6.\ {@_{i}\Diamond j}^{*} \displaystyle[\Diamond] \displaystyle 7.\ @_{j}p \displaystyle[\Diamond] \displaystyle 8.\ @_{j}j \displaystyle[\mathit{Eq}] \displaystyle 9.\ @_{j}\Box\neg j \displaystyle[\mathit{Irr}] \displaystyle 10.\ @_{j}\neg i \displaystyle[\Box] \displaystyle 11.\ @_{j}\Box\neg i \displaystyle[\mathit{Trs}] \displaystyle 12.\ @_{j}\Diamond p \displaystyle[\Box] \displaystyle 13.\ @_{j}\Box\Diamond p \displaystyle[\mathit{Trs}] \displaystyle 14.\ {@_{j}\Diamond k}^{*} \displaystyle[\Diamond] \displaystyle 15.\ @_{k}p \displaystyle[\Diamond] \displaystyle 16.\ @_{k}k \displaystyle[\mathit{Eq}] \displaystyle 17.\ @_{k}\Box\neg k \displaystyle[\mathit{Irr}] \displaystyle 18.\ @_{k}\neg j \displaystyle[\Box] \displaystyle 19.\ @_{k}\Box\neg j \displaystyle[\mathit{Trs}] \displaystyle 20.\ @_{k}\neg i \displaystyle[\Box] \displaystyle 21.\ @_{k}\Box\neg i \displaystyle[\mathit{Trs}] \displaystyle 22.\ @_{k}\Diamond p \displaystyle[\Box] \displaystyle 23.\ @_{k}\Box\Diamond p \displaystyle[\mathit{Trs}] Figure 6: An open saturated branch of \mathbf{TAB}_{\mathbf{I4}} . Formulas with ∗ are accessibility formulas. i j Figure 7: The model \mathcal{M}^{\Theta} constructed from a branch \Theta in Figure 6 We observe that @_{k}\neg j\in\Theta in the branch \Theta in Figure 6 . Since we create a model from an open saturated branch based on identity urfathers, we cannot distinguish twins that are not in the root formula. Then, we cannot rule out the possibility of a cluster defined as follows being formed. Definition 3.19 . Let (W,R) be a transitive frame. A cluster C is a set such that C\subseteq W , R over C is a universal relation, and for any D such that C\subsetneq D\subseteq W , R over D is not a universal relation. A cluster C is simple if C has only one element, and proper if it consists of more than one element. To solve this problem, we bulldoze all the reflexive points and turn a frame into an irreflexive one. This method was initially used by Segerberg [ 16 ] . The procedure for bulldozing is as follows. First, we insert a strict partial order into each cluster, aligning the possible worlds in a single row. Then, we copy this row and concatenate it infinitely. As a result, all clusters are unraveled into irreflexive infinite chains. For us to deal with hybrid logic, we have to make a slight modification to define the valuation function. Since this paper deals only with finite models, it suffices to use the set \mathbb{N} of natural numbers to index clusters. Definition 3.20 . Given a model \mathcal{M}=(W,R,V) , the bulldozed model \mathcal{M}_{B}=(W_{B},R_{B},V_{B}) of \mathcal{M} is defined as follows: 1. Index the clusters in \mathcal{M} by \mathbb{N} , like C_{0},C_{1},\ldots . 2. Insert an arbitrary strict total order <_{n} in each cluster C_{n} . 3. Define C^{\prime}_{n}=C_{n}\times\mathbb{N} (infinitely many copies of C_{n} ). 4. Define W_{B}=W^{-}\cup\bigcup_{n\in\mathbb{N}}C^{\prime}_{n} , where W^{-}=W\setminus\bigcup_{n\in\mathbb{N}}C_{n} is a set of irreflexive worlds. 5. Define \alpha:W_{B}\rightarrow W by \alpha(w)=w if w\in W^{-} and \alpha((w,m))=w otherwise. 6. Define R_{B} . wR_{B}v if and only if one of the following conditions holds: • w\in W^{-} or v\in W^{-} , and \alpha(w)R\alpha(v) (A relation including irreflexive worlds is preserved.) • w\in C^{\prime}_{m} , v\in C^{\prime}_{n} , m\neq n , and \alpha(w)R\alpha(v) (A relation between different clusters is preserved.) • w=(w^{\prime},m) and v=(v^{\prime},n) are in the same C^{\prime}_{l} and: – m