Optimizing Proof-Search via Linearization for Gödel-Löb Logic with Tree-Hypersequents Tim S. Lyon Omar Y. A. A. Taher Abstract We answer a question posed by Poggiolesi concerning a syntactic decidability proof for 𝖦𝖫 \mathsf{GL} in the tree-hypersequent system 𝖢𝖲𝖦𝖫 \mathsf{CSGL} , and resolve a challenge identified by Maggesi and Perini Brogi, who sought a 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} proof-search algorithm for 𝖦𝖫 \mathsf{GL} in expressive sequent-based formalisms. We work with a notational variant of 𝖢𝖲𝖦𝖫 \mathsf{CSGL} formulated in terms of (labeled) tree sequents. Our answer is complexity-optimal: we present a proof-search algorithm that decides the (in)validity of formulae and runs in 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} , matching the known 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} -completeness of 𝖦𝖫 \mathsf{GL} . To achieve this, we introduce a linearization method , which constructs only a single branch of a derivation and of a tree sequent at a time, avoiding the exponential blowup typical of naive proof-search in sequent formalisms. We show how to systematically combine fragments of tree sequents generated during proof-search to extract finite counter-models, which serves as a theoretical device for establishing the correctness of the algorithm when proof-search fails. Finally, we show that every valid formula admits a proof consisting solely of line sequents, which correspond to linear nested sequents. This establishes a connection between depth-first proof-search and linear nested sequent calculi. Our results not only answer the aforementioned questions, but also provide new insights into proof-search and correctness arguments in tree sequent systems for modal logics. 1 Introduction Provability logics are a class of modal logics in which the modal operator \Box is interpreted as “it is provable that” with respect to a given arithmetical theory. Among these, Gödel–Löb logic ( \mathsf{GL} ) is particularly prominent. It originates in the work of Löb, who identified a set of conditions satisfied by the provability predicate of Peano Arithmetic (PA), leading to both axiomatic and semantic characterizations of \mathsf{GL} . The logic can be axiomatized as an extension of the basic modal logic \mathsf{K} by adding Löb’s axiom \Box(\Box\varphi\rightarrow\varphi)\rightarrow\Box\varphi and is sound and complete with respect to transitive and conversely well-founded relational models [ 26 ] . In a landmark result, Solovay [ 29 ] showed that \mathsf{GL} precisely captures the provability logic of PA, in the sense that it proves exactly the modal principles that PA can establish about its own provability predicate. The logic \mathsf{GL} has a well-developed structural proof theory and admits a number of cut-free sequent-style calculi. Sequent systems in the style of Gentzen were first provided by Sambin and Valentini in the early 1980s [ 24 , 25 ] ; see also Avron [ 2 ] . Since then, a variety of alternative systems have been introduced, either by enriching the underlying sequent structure or by generalizing the notion of proof itself [ 15 , 18 , 21 , 27 , 28 ] . These systems have proven useful for studying (meta-)logical properties of \mathsf{GL} , including cut-elimination [ 18 ] and constructive Lyndon interpolation [ 27 ] . In this paper, we study proof-search in the tree-hypersequent system \mathsf{CSGL} introduced by Poggiolesi [ 21 ] . Tree-hypersequents are trees of Gentzen sequents and are more traditionally known as nested sequents . This formalism is also known to be equivalent to the formalism of tree sequents , which use labeled sequent notation (cf. [ 7 , 8 , 14 ] ). (NB. In this paper, we take tree-hypersequents, nested sequents, and tree sequents to be synonymous with each other as all formalisms are notational variants of one another.) The formalism was introduced independently by Kashima [ 9 ] and Bull [ 4 ] with further influential works provided by Brünnler [ 3 ] and Poggiolesi [ 22 , 21 ] . Such systems arose out of a call for cut-free sequent-style systems for logics not known to possess a cut-free Gentzen system, such as the tense logic \mathsf{K_{t}} and the modal logic \mathsf{S5} . Such systems exhibit fundamental admissibility and invertibility properties, making them well-suited for automated reasoning tasks [ 16 , 13 ] . For a comprehensive survey on nested (and equivalent) sequent systems, see Lellmann and Poggiolesi [ 11 ] . In the concluding section of Poggiolesi [ 21 ] , the author raises the question of how decidability for \mathsf{GL} might be established using the system \mathsf{CSGL} . More recently, Maggesi and Perini Brogi [ 17 ] implemented a decision procedure for \mathsf{GL} in HOL Light based on Negri’s labeled sequent calculus \mathsf{G3KGL} [ 20 ] . However, they observe that their procedure belongs to \mathsf{EXPSPACE} and identify achieving \mathsf{PSPACE} as “the ideal goal” [ 17 , Section 7] . In this paper, we answer both of these questions: we present a proof-search algorithm for \mathsf{GL} based on \mathsf{CSGL} that runs in \mathsf{PSPACE} , thereby achieving complexity-optimality. Since proofs between \mathsf{CSGL} and \mathsf{G3KGL} are inter-translatable in \mathsf{PTIME} [ 7 , 14 ] , our approach is also applicable to \mathsf{G3KGL} and can be used to resolve the \mathsf{PSPACE} goal for labeled sequent-based proof-search. Our investigation of these problems led to several technical and conceptual insights, which we outline below. We note that we work with a syntactic variant of Poggiolesi’s \mathsf{CSGL} in this paper that uses tree sequents [ 8 ] since it simplifies much of our work and definitions. Our main contributions are as follows: \bullet First, naive proof-search algorithms for nested sequent systems are typically at least exponential in both time and space. This is because derivations in such systems are “trees of trees,” which can produce exponentially large structures. Since \mathsf{GL} is \mathsf{PSPACE} -complete (see [ 5 , Lemma 18.26] ), one should expect the existence of a proof-search algorithm in \mathsf{CSGL} that runs in \mathsf{PSPACE} . To address this, we show how to formulate a proof-search algorithm that constructs only a single branch of a derivation and of a tree sequent at a time. We refer to this method here as linearization . To the best of our knowledge, this is the first proof-search algorithm of this kind for a tree (i.e., nested) sequent system, and the technique appears adaptable to similar systems as well. \bullet Second, because our linearization method generates only single branches of tree sequents at a time, the usual methods for obtaining counter-models from failed proof-search (see, e.g., [ 13 , 30 ] ) are obstructed. Each branch of a tree sequent represents only a fragment of a counter-model, which complicates proving correctness of the algorithm. To address this, we show how all such fragments can be systematically combined when proof-search fails to define a finite counter-model of the input, which constitutes a further contribution. \bullet Third, as a corollary to our proof-search algorithm, we find that every valid formula has a proof in \mathsf{CSGL} in which every tree sequent is actually a line . It is known that such line sequents are notational variants of linear nested sequents , introduced by Lellmann [ 12 ] . Our work shows that “linearized” proof-search can be used to extract linear nested sequent calculi for modal logics. Indeed, the proofs produced by our algorithm are variants of those in the recently introduced linear nested sequent calculus \mathsf{LNGL} for \mathsf{GL} [ 15 ] . \bullet Last, the above results answer the question posed by Poggiolesi in [ 21 ] and the open problem of Maggesi and Perini Brogi [ 17 ] . Sambin and Valentini [ 24 ] and Negri [ 20 ] provided proof-search algorithms for \mathsf{GL} within the Gentzen sequent formalism and labeled sequent formalism, respectively. 1 1 1 Although our paper is concerned with the sequent formalism, we note that Goré and Kelly [ 6 ] implemented a tableau algorithm for \mathsf{GL} in the Tableau Work Bench [ 1 ] ; however, no complexity analysis was provided. We believe their algorithm is likely \mathsf{PSPACE} , yet this is independent of our goal of addressing the challenge of Maggesi and Perini Brogi [ 17 ] . However, neither paper established complexity bounds, and neither procedure appears to run in \mathsf{PSPACE} . In fact, the implementation of proof search in \mathsf{G3KGL} by Maggesi and Perini Brogi [ 17 ] is known to be \mathsf{EXPSPACE} . Our approach differs in that we achieve complexity-optimality within an expressive sequent formalism (tree-hypersequents), demonstrating that the \mathsf{EXPSPACE} blowup observed in [ 17 ] is not inherent to such formalisms but can be overcome with suitable proof-search techniques. The efficiency of our algorithm relies on two key ideas: forgoing the support of counter-model extraction and the use of disjunctive branching. Counter-model extraction is an algorithm design choice that supports the output of a counter-model witnessing the invalidity of the input, in the same way that proofs can be output to witness the validity of the input. The existing proof-search procedures mentioned above all output counter-models when proof-search fails, which causes an exponential blowup since counter-models can be of exponential size. The key to achieving the \mathsf{PSPACE} upper bound is thus the following trade-off: our algorithm forgoes direct counter-model extraction in exchange for reduced space consumption. Our linearization method avoids the exponential blowup by outputting only a Boolean verdict; counter-model extraction is no longer immediate and instead serves as a theoretical device for proving correctness when proof-search fails. The second idea is the concept of disjunctive branching , which was motivated by the work of Mints [ 19 ] . While Mints employs (essentially) hypersequents to perform disjunctive branching, we take an alternative approach and use a ‘disjunctive inference rule’ whose conclusion is provable whenever at least one premise is provable. This allows us to further reduce the space needed to carry out proof-search. We note that our use of disjunctive inference rules is closely related to the disjunctive (or ‘existential’) rules employed in tableau algorithms (cf. [ 1 ] ). However, our approach is distinct in that we perform disjunctive branching at two levels: at the level of branches in a derivation, which is common practice for reducing complexity, but also at the level of tree sequents, which appears to be a new idea. Outline of Paper. In Section 2 , we recall the language and semantics of Gödel-Löb logic \mathsf{GL} . In Section 3 , we recall and discuss Poggiolesi’s tree-hypersequent system \mathsf{CSGL} [ 21 ] and recast the system in the formalism of tree sequents (cf. [ 7 , 8 ] ) to simplify our work. In Section 4 , we introduce our proof-search algorithm, prove it correct and terminating, and briefly discuss the relationship between proofs generated by our algorithm and the linear nested sequent formalism. Last, in Section 5 , we conclude and discuss future work. 2 Gödel-Löb Provability Logic We let \mathsf{Atm}:=\{p,q,r,\ldots\} be a countable set of atoms and define the language \mathscr{L} to be the set of formulae generated by the following grammar in BNF: \varphi::=p\ |\ \bot\ |\ \varphi\rightarrow\varphi\ |\ \Box\varphi where p ranges over \mathsf{Atm} . We use \varphi , \psi , \chi , \ldots to denote formulae in \mathscr{L} and define \neg\varphi:=\varphi\rightarrow\bot . The length of a formula \varphi , denoted |\varphi| , is defined to be the number of symbols it contains and we let \mathsf{sufo}(\varphi) denote the set of all subformulae of \varphi , defined in the expected way. Definition 2.1 (Model) . We define a model to be a tuple \mathbf{M}=(\mathbf{W},\mathbf{R},\mathbf{V}) such that • \mathbf{W} is a non-empty set of worlds w , u , v , \ldots (occasionally annotated); • \mathbf{R}\subseteq\mathbf{W}\times\mathbf{W} is transitive and conversely-wellfounded; 2 2 2 We note that R is conversely-wellfounded iff it is free of infinite ascending R -chains. • \mathbf{V}:\mathsf{Atm}\to 2^{\mathbf{W}} is a valuation function . Definition 2.2 (Semantic Clauses) . We define the satisfaction of a formula \varphi in a model \mathbf{M} at world w , written \mathbf{M},w\models\varphi , recursively as follows: • \mathbf{M},w\models p iff w\in\mathbf{V}(p) ; • \mathbf{M},w\not\models\bot ; • \mathbf{M},w\models\varphi\rightarrow\psi iff \mathbf{M},w\not\models\varphi or \mathbf{M},w\models\psi ; • \mathbf{M},w\models\Box\varphi iff \forall u\in\mathbf{W} , if (w,u)\in\mathbf{R} , then \mathbf{M},u\models\varphi . We define \mathbf{M}\models\varphi iff \forall w\in\mathbf{W} , \mathbf{M},w\models\varphi . We write \models\varphi and say that \varphi is valid iff for all models \mathbf{M} , \mathbf{M}\models\varphi . Gödel-Löb logic ( \mathsf{GL} ) is defined to be the set \mathsf{GL}\subset\mathscr{L} of all valid formulae. As shown by Segerberg [ 26 ] , the logic \mathsf{GL} can be axiomatized by extending the axioms of the modal logic \mathsf{K} with Löb’s axiom \Box(\Box\varphi\rightarrow\varphi)\rightarrow\Box\varphi . 3 Tree Sequents In this section, we review (a notational variant of) Poggiolesi’s tree-hypersequent system \mathsf{CSGL} for \mathsf{GL} [ 21 ] . We opt for a notational variant of \mathsf{CSGL} that uses the labeled sequent syntax (cf. [ 28 , 31 ] ) as it simplifies the formulation of our proof-search algorithm; however, we stress that this system is Poggiolesi’s \mathsf{CSGL} despite the notational change. It was already observed by Goré and Ramanayake [ 7 ] that restricting labeled sequents to be trees, rather than more general, binary graphs (which may be disconnected or include cycles), yields tree sequents (cf. [ 8 ] ), which are a notational variant of tree-hypersequents and nested sequents. Via this observation, we are free to employ the labeled sequent syntax without any negative repercussions, that is, the structural properties of Poggiolesi’s system \mathsf{CSGL} will be retained in spite of this notational change. We let \mathsf{Lab}=\{x,y,z,\ldots\} be a countably infinite set of labels , define a relational atom to be an expression of the form xRy with x,y\in\mathsf{Lab} , and define a labeled formula to be an expression of the form x:\varphi such that x\in\mathsf{Lab} and \varphi\in\mathscr{L} . We use upper-case Greek letters \Gamma,\Delta,\Sigma,\ldots to denote finite sets of labeled formulae. For a set \mathcal{R} of relational atoms and a set \Gamma of labeled formulae, we let \mathsf{Lab}(\mathcal{R}) , \mathsf{Lab}(\Gamma) , and \mathsf{Lab}(\mathcal{R},\Gamma) be the sets of all labels occurring therein. For a set \Gamma of labeled formulae, we define \Gamma(x):=\{\varphi\ |\ x:\varphi\in\Gamma\} and for sets \Gamma and \Delta of labeled formulae, we let \Gamma,\Delta denote the union of the two. \mathsf{id_{1}} \mathcal{T},\Gamma,x:p\vdash x:p,\Delta \mathsf{id_{2}} \mathcal{T},\Gamma,x:\Box\varphi\vdash x:\Box\varphi,\Delta \bot\mathsf{L} \mathcal{T},\Gamma,x:\bot\vdash\Delta \mathcal{T},\Gamma,x:\psi\vdash\Delta \mathcal{T},\Gamma\vdash x:\varphi,\Delta {\rightarrow}\mathsf{L} \mathcal{T},\Gamma,x:\varphi\rightarrow\psi\vdash\Delta \mathcal{T},xRy,\Gamma,x:\Box\varphi,y:\Box\varphi\vdash\Delta \mathsf{4L} \mathcal{T},xRy,\Gamma,x:\Box\varphi\vdash\Delta \mathcal{T},\Gamma,x:\varphi\vdash x:\psi,\Delta {\rightarrow}\mathsf{R} \mathcal{T},\Gamma\vdash x:\varphi\rightarrow\psi,\Delta \mathcal{T},xRy,\Gamma,x:\Box\varphi,y:\varphi\vdash\Delta \Box\mathsf{L} \mathcal{T},xRy,\Gamma,x:\Box\varphi\vdash\Delta \mathcal{T},xRy,\Gamma,y:\Box\varphi\vdash y:\varphi,\Delta \Box\mathsf{R}^{{\dagger}} \mathcal{T},\Gamma\vdash x:\Box\varphi,\Delta Figure 1: Tree Sequent Calculus CSGL for \mathsf{GL} . The \Box\mathsf{R} rule is subject to a side condition {\dagger} , namely, the rule is applicable only if the label y is fresh. A set \mathcal{T} of relational atoms is called a tree iff the graph G(\mathcal{T}):=(V,E) forms a directed tree, where we define V:=\{x\ |\ x\in\mathsf{Lab}(\mathcal{T})\} and E:=\{(x,y)\ |\ xRy\in\mathcal{T}\} . 3 3 3 A tree is a graph such that there exists a unique directed path from a unique vertex x , called the root , to every other vertex. A tree sequent is defined to be an expression of the form \mathcal{T},\Gamma\vdash\Delta such that (1) \mathcal{T} is a tree, (2) if \mathcal{T}\neq\emptyset , then \mathsf{Lab}(\Gamma,\Delta)\subseteq\mathsf{Lab}(\mathcal{T}) , and (3) if \mathcal{T}=\emptyset , then |\mathsf{Lab}(\Gamma,\Delta)|=1 , i.e., all labeled formulae in \Gamma,\Delta share the same label. We note that conditions (1)–(3) ensure that each tree sequent forms a connected graph that is indeed of a tree shape. We use T and annotated versions thereof to denote tree sequents. Given a tree sequent \mathcal{T},\Gamma\vdash\Delta , we refer to \mathcal{T},\Gamma as the antecedent and \Delta as the consequent . The root of a tree sequent \mathcal{T},\Gamma\vdash\Delta is the unique label x such that, for every other label y\in\mathsf{Lab}(\mathcal{T},\Gamma,\Delta) , there exists a directed path of relational atoms in \mathcal{T} from x to y . If \mathcal{T}=\emptyset , the root is the single label x occurring in all formulae of \Gamma and \Delta . We adopt standard tree terminology when discussing tree sequents (e.g. root, branch, ancestor, leaf; see [ 23 , Chapter 11] ). We define a flat sequent to be a tree sequent of the form \Gamma\vdash\Delta , that is, a flat sequent is a sequent \Gamma\vdash\Delta without relational atoms and where every labeled formula in \Gamma,\Delta shares the same label. Furthermore, we define a line sequent \mathcal{T},\Gamma\vdash\Delta to be a tree sequent such that \mathcal{T} is a line, i.e., \mathcal{T} is of the form x_{1}Rx_{2},\ldots,x_{i{-}1}Rx_{i} for i\in\mathbb{N} (cf. [ 10 ] ). For two tree sequents T=\mathcal{T},\Gamma\vdash\Delta and T^{\prime}=\mathcal{T}^{\prime},\Sigma\vdash\Pi , we define their sequent composition T\odot T^{\prime} as: (\mathcal{T},\Gamma\vdash\Delta)\odot(\mathcal{T}^{\prime},\Sigma\vdash\Pi):=\mathcal{T},\mathcal{T}^{\prime},\Gamma,\Sigma\vdash\Delta,\Pi. We note that a sequent composition will only be applied to tree sequents whose shared labels form a single path from the root, ensuring that the resulting sequent retains a tree structure. Every tree sequent encodes a tree of flat sequents. Let T=\mathcal{T},xRy_{1},\ldots,xRy_{n},\Gamma\vdash\Delta be a tree sequent such that x is the root and y_{1},\ldots,y_{n} are all children of x . The tree tr_{x}(T) is graphically depicted below: \textstyle{\overset{x}{\boxed{x:\Gamma(x)\vdash x:\Delta(x)}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \textstyle{tr_{y_{1}}(\mathcal{T},\Gamma\vdash\Delta)} \textstyle{\ldots} \textstyle{tr_{y_{n}}(\mathcal{T},\Gamma\vdash\Delta)} As defined below, tree sequents may be interpreted directly over models. Definition 3.1 . Let \mathbf{M}=(\mathbf{W},\mathbf{R},\mathbf{V}) be a model. An \mathbf{M} -assignment is a function \mu\colon\mathsf{Lab}\to\mathbf{W} . A tree sequent \mathcal{T},\Gamma\vdash\Delta is satisfied on \mathbf{M} with an \mathbf{M} -assignment \mu iff the following holds: if for all xRy\in\mathcal{T} and x:\varphi\in\Gamma , (\mu(x),\mu(y))\in\mathbf{R} and \mathbf{M},\mu(x)\models\varphi , then there exists a y:\psi\in\Delta such that \mathbf{M},\mu(y)\models\psi . A tree sequent is defined to be valid iff it is satisfied on all models \mathbf{M} with all \mathbf{M} -assignments; a tree sequent is defined to be invalid otherwise. The tree sequent calculus \mathsf{CSGL} is shown in Figure 1 . 4 4 4 We remark that Poggiolesi’s original system uses multisets rather than sets in sequents; however, in our setting we may work with sets without any loss of generality. It consists of three initial rules \mathsf{id_{1}} , \mathsf{id_{2}} , and \bot\mathsf{L} . We call the conclusion of such a rule an initial sequent . The remaining rules are called logical rules and introduce complex logical formulae into either the antecedent or consequent of the rule’s conclusion. We note that the \Box\mathsf{R} rule is subject to a side condition, namely, the label y must be fresh in any application of the rule, i.e., the label y is forbidden to occur in the conclusion. We remark that the freshness condition on y ensures that \Box\mathsf{R} preserves the tree structure of sequents when applied bottom-up: since y does not occur in the conclusion, adjoining the relational atom xRy extends the tree by a fresh leaf rather than introducing a cycle or disconnected region. We refer to the distinguished formulae in the conclusion (premises) of a rule as the principal formulae ( auxiliary formulae , respectively). For example, x:\Box\varphi is principal in \Box\mathsf{R} and xRy,y:\Box\varphi,y:\varphi are auxiliary. We also refer to the auxiliary formula y:\Box\varphi as the diagonal formula in \Box\mathsf{R} . In the subsequent section, we will explain how the diagonal formula helps ensure the termination of proof-search. Remark 3.2 . Poggiolesi’s original system included the following \Box\mathsf{L}^{\prime} rule rather than the \Box\mathsf{L} rule. (NB. We have expressed this rule in labeled notation.) However, the left premise of the \Box\mathsf{L}^{\prime} rule is provable in \mathsf{CSGL} using \mathsf{4L} , \Box\mathsf{L} , and \Box\mathsf{R} . We therefore opt to use the simpler \Box\mathsf{L} rule in \mathsf{CSGL} rather than the \Box\mathsf{L}^{\prime} rule to simplify our work. \mathcal{T},xRy,\Gamma,x:\Box\varphi\vdash y:\Box\varphi,\Delta \mathcal{T},xRy,\Gamma,x:\Box\varphi,y:\varphi\vdash\Delta \Box\mathsf{L}^{\prime} \mathcal{T},xRy,\Gamma,x:\Box\varphi\vdash\Delta \mathcal{T},\Gamma\vdash\Delta \mathsf{w} \mathcal{T},\mathcal{T}^{\prime},\Gamma,\Gamma^{\prime}\vdash\Delta,\Delta^{\prime} \mathcal{T},\Gamma\vdash x:\varphi,\Delta \mathcal{T},\Gamma,x:\varphi\vdash\Delta \mathsf{cut} \mathcal{T},\Gamma\vdash\Delta Figure 2: Admissible rules. A derivation of a tree sequent \mathcal{T},\Gamma\vdash\Delta is defined to be a (potentially infinite) tree whose nodes are labeled with tree sequents such that (1) \mathcal{T},\Gamma\vdash\Delta is the root of the tree and (2) each parent node is the conclusion of a rule with its children the corresponding premises. A proof is a finite derivation such that every leaf is an instance of an initial sequent. We use \pi (potentially annotated) to denote derivations and proofs throughout the remainder of the paper. We define a branch \mathcal{B}=T_{0},T_{1},\ldots,T_{n},\ldots to be a maximal path of tree sequents in a derivation such that T_{0} is the conclusion of the derivation and each nested sequent T_{i+1} (if it exists) is a child of T_{i} . The height of a derivation is defined in the usual way as the maximal length of a branch in the derivation. The rules displayed in Figure 2 are admissible in \mathsf{CSGL} . We define a rule to be admissible ( height-preserving admissible ) iff the following holds: if the premises of the rule have proofs (of height h_{1},\ldots,h_{n} ), then the conclusion of the rule has a proof (of height h\leq\max\{h_{1},\ldots,h_{n}\} ). If we let \mathsf{r}^{-1}_{i} be the i -inverse of a n -ary rule \mathsf{r} whose conclusion is the i^{th} premise and premise is the conclusion of \mathsf{r} , then we say that \mathsf{r} is (height-preserving) invertible iff \mathsf{r}^{-1}_{i} is (height-preserving) admissible for each i\in[n] . 5 5 5 We define [n]=\{1,\ldots,n\} and therefore use i\in[n] as a shorthand for 1\leq i\leq n . We refer to height-preserving admissible and invertible rules as hp-admissible and hp-invertible , respectively. Theorem 3.3 ( [ 18 , 21 ] ) . The tree sequent calculus \mathsf{CSGL} satisfies the following: (1) Each tree sequent of the form \mathcal{T},\Gamma,x:\varphi\vdash x:\varphi,\Delta is provable in \mathsf{CSGL} ; (2) All non-initial rules are hp-invertible in \mathsf{CSGL} ; (3) The \mathsf{w} rule is hp-admissible in \mathsf{CSGL} ; 6 6 6 In the setting of tree sequents, the weakening rule \mathsf{w} is assumed to preserve the ‘tree shape’ of tree sequents when applied. (4) The \mathsf{cut} rule is admissible in \mathsf{CSGL} ; 7 7 7 Maniwa and Kashima proved that the cut-elimination algorithm given in [ 21 ] is incorrect and provided an alternative, correct algorithm that eliminates cuts from proofs in \mathsf{CSGL} . (5) \varphi is valid iff \vdash x:\varphi is provable in \mathsf{CSGL} . 4 Complexity-Optimal Proof-Search We provide an answer to a question posed by Poggiolesi [ 21 , p. 610] concerning a syntactic decision procedure for \mathsf{GL} using \mathsf{CSGL} . More precisely, we present a proof-search algorithm that decides the (in)validity of formulae in \mathsf{PSPACE} , thereby matching the known \mathsf{PSPACE} -completeness of \mathsf{GL} . Since \mathsf{CSGL} and \mathsf{G3KGL} are \mathsf{PTIME} -equivalent [ 7 , 14 ] , our method is adaptable to labeled sequent-based proof-search as well, and thus resolves the open problem of Maggesi and Perini Brogi [ 17 , Section 7] . Several insights emerge from the design and analysis of this algorithm. First, in order to ensure the \mathsf{PSPACE} upper-bound, we develop a ‘depth-first’ proof-search procedure that generates only a single branch of a derivation at a time, as well as a single branch of the underlying tree sequents. While this strategy significantly reduces space consumption, it complicates the proof of correctness. In particular, demonstrating the existence of a counter-model when proof-search fails becomes difficult because the algorithm only produces partial fragments of a counter-model in each branch. We show how these fragments can nevertheless be combined to yield a genuine counter-model for the input sequent when proof-search fails. Second, we observe that proof-search in \mathsf{CSGL} terminates automatically . In particular, the diagonal formula occurring in the \Box\mathsf{R} rule provides a natural bound on the depth of tree sequents generated during proof-search, eliminating the need for loop checking, despite the presence of transitivity, viz., the \mathsf{4L} rule. A similar observation was made for proof-search with Gentzen sequent calculi [ 24 ] and full labeled sequent calculi [ 20 ] . Finally, when the algorithm succeeds and produces a proof, each tree sequent appearing in the derivation is in fact a line sequent (cf. [ 10 ] ), as a direct consequence of the depth-first nature of the search. We argue that the resulting derivations can be viewed as linear nested sequent (LNS) proofs, which are variants of those in the recently introduced LNS calculus \mathsf{LNGL} [ 15 ] . This demonstrates that LNS systems can be extracted from depth-first proof-search procedures for tree (i.e., nested) sequent calculi. We now turn to the description of our proof-search algorithm. To detect termination, we introduce two syntactic properties of tree sequents. Intuitively, a tree sequent is said to be saturated if \Box\mathsf{R} is the only rule that can be applied non-redundantly (to a leaf), whereas a tree sequent is stable if no rule is non-redundantly applicable (to a leaf). Throughout this section, when we say that a rule is applicable , we mean bottom-up applicable, unless stated otherwise. Definition 4.1 (Saturated, Stable) . Let T= \mathcal{T},\Gamma\vdash\Delta be a tree sequent. We define T to be saturated iff T satisfies the following saturation conditions : (\mathsf{id}) if x:p\in\Gamma or x:\Box\varphi\in\Gamma , then x:p\notin\Delta or x:\Box\varphi\notin\Delta , respectively; (\bot\mathsf{L}) x:\bot\notin\Gamma ; ({\rightarrow}\mathsf{L}) if x:\varphi\rightarrow\psi\in\Gamma , then either x:\psi\in\Gamma or x:\varphi\in\Delta ; ({\rightarrow}\mathsf{R}) if x:\varphi\rightarrow\psi\in\Delta , then x:\varphi\in\Gamma and x:\psi\in\Delta ; (\Box\mathsf{4L}) if xRy\in\mathcal{T} and x:\Box\varphi\in\Gamma , then y:\Box\varphi,y:\varphi\in\Gamma ; A tree sequent T=\mathcal{T},\Gamma\vdash\Delta is stable iff (1) it is saturated and (2) \{x:\Box\varphi\in\Delta\mid x\text{ is a leaf in }T\}=\emptyset . Our proof-search algorithm \mathtt{prove} is presented as Algorithm 1. We remark that since \mathsf{CSGL} has the subformula property, only subformulae of the input will appear during the computation of \mathtt{prove} . We say that proof-search succeeds when it outputs \mathtt{true} , and we say that proof-search fails when it outputs \mathtt{false} . Lines 1–2 implement the \mathsf{id_{1}} , \mathsf{id_{2}} , and \bot\mathsf{L} rules. Lines 3–4 test whether the current sequent is stable, meaning, any further rule application would be unnecessary, and the algorithm can safely halt. Lines 5-7, 8-10, and 11-13 respectively encode {\rightarrow}\mathsf{L} , {\rightarrow}\mathsf{R} , and a simultaneous application of \Box\mathsf{L} and \mathsf{4L} . For the binary rule {\rightarrow}\mathsf{L} , the algorithm may perform two recursive calls, as specified by the following expression, where the symbol \&\& denotes conjunction: \mathtt{prove}(\mathcal{T},\Gamma^{\prime}\vdash\Delta)\ \&\&\ \mathtt{prove}(\mathcal{T},\Gamma\vdash\Delta^{\prime}) . We assume that the call \mathtt{prove}(\mathcal{T},\Gamma^{\prime}\vdash\Delta) is executed first, and that the second call \mathtt{prove}(\mathcal{T},\Gamma\vdash\Delta^{\prime}) is invoked only if the former returns \mathtt{true} . In particular, if \mathtt{prove}(\mathcal{T},\Gamma^{\prime}\vdash\Delta)=\mathtt{false} , the conjunction immediately evaluates to \mathtt{false} and the second call is skipped; if it returns \mathtt{true} , the second call is executed to determine the value of the conjunction. This evaluation strategy ensures that the algorithm generates at most one branch of a derivation at any given time and avoids unnecessary work. Moreover, this corresponds to conjunctive branching : a proof is found only if both recursive calls succeed. One interesting aspect of our algorithm concerns lines 14-19, which encode multiple, simultaneous applications of the \Box\mathsf{R} rules. The algorithm may invoke up to n many recursive calls via the line: \mathtt{prove}(\mathcal{T}_{1},\Gamma_{1}\vdash\Delta_{1})\ \|\ \cdots\ \|\ \mathtt{prove}(\mathcal{T}_{n},\Gamma_{n}\vdash\Delta_{n}). Here the symbol \| stands for disjunction. We assume that \mathtt{prove}(\mathcal{T}_{1},\Gamma_{1}\vdash\Delta_{1}) is executed first, and depending on the output, \mathtt{prove}(\mathcal{T}_{2},\Gamma_{2}\vdash\Delta_{2}) may be executed second, and so on. Each successive call \mathtt{prove}(\mathcal{T}_{i+1},\Gamma_{i+1}\vdash\Delta_{i+1}) is only executed if the former call \mathtt{prove}(\mathcal{T}_{i},\Gamma_{i}\vdash\Delta_{i}) returns \mathtt{false} . In particular, if \mathtt{prove}(\mathcal{T}_{i},\Gamma_{i}\vdash\Delta_{i})=\mathtt{true} , the disjunction immediately evaluates to \mathtt{true} and all remaining calls are skipped; if it returns \mathtt{false} , the next call is executed to determine the value of the disjunction. This evaluation strategy ensures that the algorithm generates at most one branch of a tree sequent at any given time. This contrasts with conjunctive branching, which restricts exploration of proof-search to a single branch of a derivation at a time. Therefore, line 19 corresponds to disjunctive branching in the procedure: a proof is found if at least one recursive call succeeds (cf. [ 19 ] ). One can view this operation in \mathtt{prove} as a rule application, that is, one can view lines 14-19 as encoding a bottom-up application of the \Box_{\mathsf{DB}} rule, defined below: \{\mathcal{T},xRy_{i},\Gamma,y_{i}:\Box\varphi_{i}\vdash y_{i}:\varphi_{i},\Sigma_{\Box\varphi_{i}},\Delta\mid i\in[n] } \Box_{\mathsf{DB}}^{{\dagger}} \mathcal{T},\Gamma\vdash x:\Box\varphi_{1},\ldots,x:\Box\varphi_{n},\Delta The \Box_{\mathsf{DB}} rule is subject to a side condition {\dagger} stipulating that the rule can be applied only if (1) x is a leaf in \mathcal{T} , (2) each y_{i} is fresh, and (3) \Delta\cap\{x:\Box\varphi\mid\varphi\in\mathscr{L}\}=\emptyset . Also, we define the set \Sigma_{\Box\varphi_{i}} appearing in each premise of \Box_{\mathsf{DB}} for i\in[n] accordingly: \Sigma_{\Box\varphi_{i}}:=\{x:\Box\varphi_{1},\ldots,x:\Box\varphi_{n}\}\setminus\{x:\Box\varphi_{i}\} . Input: A tree sequent T=\mathcal{T},\Gamma\vdash\Delta Output: A Boolean: \mathtt{true} , \mathtt{false} if x:p\in\Gamma\cap\Delta , x:\Box\varphi\in\Gamma\cap\Delta , or x:\bot\in\Gamma then 1 return \mathtt{true} ; if T=\mathcal{T},\Gamma\vdash\Delta is stable then 2 return \mathtt{false} ; if x:\varphi\rightarrow\psi\in\Gamma,x:\psi\not\in\Gamma,x:\varphi\not\in\Delta then 3 Set \Gamma^{\prime}:=\Gamma,x:\psi and \Delta^{\prime}:=\Delta,x:\varphi ; return \mathtt{prove}(\mathcal{T},\Gamma^{\prime}\vdash\Delta) && \mathtt{prove}(\mathcal{T},\Gamma\vdash\Delta^{\prime}) ; if x:\varphi\rightarrow\psi\in\Delta and either x:\varphi\not\in\Gamma or x:\psi\not\in\Delta then 4 Set \Gamma^{\prime}:=\Gamma,x:\varphi and \Delta^{\prime}:=\Delta,x:\psi ; return \mathtt{prove}(\mathcal{T},\Gamma^{\prime}\vdash\Delta^{\prime}) ; if x:\Box\varphi\in\Gamma , xRy\in\mathcal{T} , but y:\Box\varphi,y:\varphi\not\in\Gamma then 5 Set \Gamma^{\prime}:=\Gamma,y:\Box\varphi,y:\varphi ; return \mathtt{prove}(\mathcal{T},\Gamma^{\prime}\vdash\Delta) ; if \mathcal{T},\Gamma\vdash\Delta is saturated then 6 Let \{x:\Box\varphi\in\Delta\mid\forall y\in\mathsf{Lab}(T),xRy\not\in\mathcal{T}\}=\{x:\Box\varphi_{1},\ldots,x:\Box\varphi_{n}\} ; Let y_{1},\ldots,y_{n}\in\mathsf{Lab}\setminus\mathsf{Lab}(\mathcal{T},\Gamma\vdash\Delta) ; Set \mathcal{T}_{i}:=\mathcal{T},xRy_{i} ; Set \Gamma_{i}:=\Gamma,y_{i}:\Box\varphi_{i} and \Delta_{i}:=\Delta,y_{i}:\varphi_{i} , for i\in[n] ; return \mathtt{prove}(\mathcal{T}_{1},\Gamma_{1}\vdash\Delta_{1})\ \|\ \cdots\ \|\ \mathtt{prove}(\mathcal{T}_{n},\Gamma_{n}\vdash\Delta_{n}) ; Algorithm 1 \mathtt{prove} Based on the above description of \mathtt{prove} , one can see that the algorithm operates between two phases: in one phase of the algorithm, it attempts to generate a saturated sequent. Once such a sequent is generated, it is checked to see if it is stable. If so, the algorithm may halt; however, if a box formula occurs at a leaf, then this signals that the \Box\mathsf{R} rule (and thus, the \Box_{\mathsf{DB}} rule) can be applied bottom-up. Example 4.2 . To demonstrate the functionality of \Box_{\mathsf{DB}} , we give an example application with principal formulae y:\Box C and y:\Box D : xRy,yRz_{1},x:A,z_{1}:\Box C\vdash z_{1}:C,x:\Box B,y:\Box D\quad xRy,yRz_{2},x:A,z_{2}:\Box D\vdash z_{2}:D,x:\Box B,y:\Box C \Box_{\mathsf{DB}} xRy,x:A\vdash x:\Box B,y:\Box C,y:\Box D Since lines 14–19 correspond to applications of the \Box_{\mathsf{DB}} rule, we may regard the structure generated by a run of \mathtt{prove} as a kind of derivation that employs rules in (\mathsf{CSGL}\setminus\{\Box\mathsf{R}\})\cup\{\Box_{\mathsf{DB}}\} . This perspective motivates the definition of a computation tree , a structure that plays a crucial role in extracting proofs and defining counter-models, used to establish the correctness of terminating proof-search. Definition 4.3 (Computation Tree) . A computation tree is a tuple \mathsf{ct}:=(\mathsf{V},\mathsf{E},\mathsf{L}) such that \mathsf{V} is a non-empty set of tree sequents, \mathsf{E}\subseteq\mathsf{V}\times\mathsf{V} , and \mathsf{L}:\mathsf{V}\to\{\mathtt{true},\mathtt{false}\} , which satisfies the following condition: each parent node T\in\mathsf{V} is the conclusion of a rule in (\mathsf{CSGL}\setminus\{\Box\mathsf{R}\})\cup\{\Box_{\mathsf{DB}}\} with its children the corresponding premises. We note that a computation tree is essentially a derivation in the ‘calculus’ (\mathsf{CSGL}\setminus\{\Box\mathsf{R}\})\cup\{\Box_{\mathsf{DB}}\} . As discussed above, \mathtt{prove}(\vdash x:\varphi) builds one branch of a computation tree at a time, in a depth-first manner, during its execution. Still, to establish the correctness of our algorithm (see Theorems 4.6 and 4.8 ), it will be helpful to have the entire computation tree traced by \mathtt{prove}(\vdash x:\varphi) , that is, the entire tree structure and all branches explored by a terminating execution of the algorithm. We therefore define \mathsf{ct}(x:\varphi):=(\mathsf{V},\mathsf{E},\mathsf{L}) to be the computation tree built by \mathtt{prove}(\vdash x:\varphi) during its execution such that for all T\in\mathsf{V} , (1) \mathsf{L}(T)=\mathtt{true} iff \mathtt{prove}(T)=\mathtt{true} and (2) \mathsf{L}(T)=\mathtt{false} iff \mathtt{prove}(T)=\mathtt{false} . For completeness, the formal definition of \mathsf{ct}(x:\varphi) is given in the appendix. \mathsf{ct}= \mathtt{true} \mathsf{id_{1}} xRz,zRw,z:\psi,w:\Box(p\rightarrow p),w:p\vdash w:p,z:\Box q,x:\varphi {\rightarrow}\mathsf{R} xRz,zRw,z:\psi,w:\Box(p\rightarrow p)\vdash w:p\rightarrow p,z:\Box q,x:\varphi T \Box_{\mathsf{DB}} xRz,z:\psi\vdash z:\Box(p\rightarrow p),z:\Box q,x:\varphi \mathtt{false} xRy,y:\varphi,y:p\vdash y:q,x:\psi {\rightarrow}\mathsf{R} xRy,y:\varphi\vdash y:p\rightarrow q,x:\psi \mathtt{true} \bot\mathsf{L} xRz,z:\psi,z:\bot\vdash z:\Box q,x:\varphi \mathsf{ct} {\rightarrow}\mathsf{L} xRz,z:\psi,z:\neg\Box(p\rightarrow p)\vdash z:\Box q,x:\varphi {\rightarrow}\mathsf{R} xRz,z:\psi\vdash z:\neg\Box(p\rightarrow p)\rightarrow\Box q,x:\varphi \Box_{\mathsf{DB}} \vdash x:\Box(p\rightarrow q),x:\Box(\neg\Box(p\rightarrow p)\rightarrow\Box q) Figure 3: Computation tree and successful proof-search example. Example 4.4 . We first provide an example of how a proof can be extracted from a computation tree if proof-search succeeds. To improve readability, we let \varphi=\Box(p\rightarrow q) and \psi=\Box(\neg\Box(p\rightarrow p)\rightarrow\Box q) . The computation tree corresponding to \mathtt{prove}(\vdash x:\varphi,x:\psi) is displayed in Figure 3 , where we let T=xRz,zRu,z:\psi,u:\Box q\vdash u:q,z:\Box(p\rightarrow p),x:\varphi . We have also indicated which branch outputs \mathtt{true} or \mathtt{false} by placing the output at the top of the branch; one can determine the labels \mathtt{true} or \mathtt{false} of each tree sequent in the computation tree based on this information. The algorithm will generate one branch of the computation tree at a time, working its way from left to right. Observe that the following proof can be extracted from the computation tree by ‘pruning’ each \Box_{\mathsf{DB}} application and only preserving a ‘successful’ branch. \bot\mathsf{L} xRz,z:\psi,z:\bot\vdash z:\Box q,x:\varphi \mathsf{id_{1}} xRz,zRw,z:\psi,z:\Box(p\rightarrow p),w:p\vdash w:p,z:\Box q,x:\varphi {\rightarrow}\mathsf{R} xRz,zRw,z:\psi,z:\Box(p\rightarrow p)\vdash w:p\rightarrow p,z:\Box q,x:\varphi \Box\mathsf{R} xRz,z:\psi\vdash z:\Box(p\rightarrow p),z:\Box q,x:\varphi {\rightarrow}\mathsf{L} xRz,z:\psi,z:\neg\Box(p\rightarrow p)\vdash z:\Box q,x:\varphi {\rightarrow}\mathsf{R} xRz,z:\psi\vdash z:\neg\Box(p\rightarrow p)\rightarrow\Box q,x:\varphi \Box\mathsf{R} \vdash x:\Box(p\rightarrow q),x:\Box(\neg\Box(p\rightarrow p)\rightarrow\Box q) By selecting a single premise of \Box_{\mathsf{DB}} that outputs \mathtt{true} , each \Box_{\mathsf{DB}} application is transformed into a \Box\mathsf{R} application, yielding a proof in \mathsf{CSGL} . We remark that since the first premise of \Box_{\mathsf{DB}} in the top computation tree \mathsf{ct} outputs \mathtt{true} , \mathtt{prove} will not recursively call the second premise T . Also, note that {\rightarrow}\mathsf{L} is applied to \neg\Box(p\rightarrow p):=\Box(p\rightarrow p)\rightarrow\bot . Last, we make two important observations: first, all tree sequents are line sequents in the computation tree, arising from the fact that each premise of \Box_{\mathsf{DB}} ‘unpacks’ a single box formula at a leaf. Second, every bottom-up application of a rule is end-active (cf. [ 12 ] ), that is, the auxiliary labeled formulae occur at leaves in all line sequents. Before turning to the general procedure for extracting proofs from successful computation trees, we examine the structure of the computation trees generated by \mathtt{prove} . In the sequel, we assume that \mathtt{prove} is invoked on an initial input of the form \vdash x:\varphi . Since every tree sequent admits a \mathsf{PTIME} -computable formula interpretation of linear size (cf. [ 21 ] ), this assumption is made without a loss of generality. Starting from such an input, \mathtt{prove} exhaustively applies the rules {\rightarrow}\mathsf{L} and {\rightarrow}\mathsf{R} (viz. lines 5-10) with auxiliary formulae at the label x , until an initial sequent, a stable sequent, or a saturated but non-stable sequent is reached. In the latter case, the rule \Box_{\mathsf{DB}} is applied, introducing a relational atom xRy along the current branch with y fresh. The algorithm then continues by exhaustively applying the rules {\rightarrow}\mathsf{L} , {\rightarrow}\mathsf{R} , \Box\mathsf{L} , and \mathsf{4L} (viz. lines 5-13) with auxiliary formulae at the new label y , again until an initial, stable, or saturated non-stable sequent is encountered. If the latter occurs, \Box_{\mathsf{DB}} is applied once more, introducing a further relational atom yRz along the current branch with z fresh, and the process repeats. This iterative pattern shows that, along any branch of a computation tree produced by \mathtt{prove} , the sequents encountered are always line sequents. Moreover, all auxiliary formulae introduced during proof-search occur at leaf nodes. Definition 4.5 (Line-Like, End-Active) . We define a derivation or computation tree to be line-like iff it consists solely of line sequents. We define a derivation or computation tree to be end-active iff all rule applications have auxiliary formulae at leaf nodes and the principal formulae in \mathsf{id_{1}} , \mathsf{id_{2}} , and \bot\mathsf{L} applications occur at leaf nodes. One can extract line-like, end-active proofs from successful proof-search by pruning computation trees as follows: starting at the root, retain all nodes labeled with \mathtt{true} ; for {\rightarrow}\mathsf{L} applications, keep both premises (which must both be labeled \mathtt{true} for the conclusion to be labeled \mathtt{true} ); and for \Box_{\mathsf{DB}} applications, retain only a single premise labeled \mathtt{true} , thereby transforming each \Box_{\mathsf{DB}} application into a \Box\mathsf{R} application. The result is a proof in \mathsf{CSGL} since all leaves are initial sequents (as they are labeled \mathtt{true} and triggered lines 1-2 of the algorithm). The proof is line-like and end-active because each premise of \Box_{\mathsf{DB}} introduces a single relational atom at a leaf, preserving the line structure, and all auxiliary formulae are introduced at leaf labels throughout the computation. Therefore, the following theorem holds; a formal proof is given in the appendix. Theorem 4.6 . If \mathtt{prove}(\vdash x:\varphi)=\mathtt{true} , then \vdash x:\varphi has a line-like, end-active proof in \mathsf{CSGL} , that is, the input \varphi is valid. The above theorem confirms that when proof-search succeeds a proof of the input exists. However, we still need to confirm that when proof-search fails a counter-model of the input exists. Let us first provide an example showing how a counter-model can be extracted via failed proof-search. \mathtt{true} \bot\mathsf{L} x:\bot\vdash x:\Box((p\rightarrow q)\rightarrow q) \mathtt{false} xRy,y:\varphi,y:p\vdash y:\bot,x:\psi {\rightarrow}\mathsf{R} xRy,y:\varphi\vdash y:\neg p,x:\psi \mathtt{true} \mathsf{id_{1}} T_{1} \mathtt{false} T_{2} {\rightarrow}\mathsf{L} xRz,z:\psi,z:p\rightarrow q\vdash x:\varphi,z:q {\rightarrow}\mathsf{R} xRz,z:\psi\vdash x:\varphi,z:(p\rightarrow q)\rightarrow q \Box_{\mathsf{DB}} \vdash x:\Box\neg p,x:\Box((p\rightarrow q)\rightarrow q) {\rightarrow}\mathsf{L} x:\neg\Box\neg p\vdash x:\Box((p\rightarrow q)\rightarrow q) {\rightarrow}\mathsf{R} \vdash x:\neg\Box\neg p\rightarrow(\Box((p\rightarrow q)\rightarrow q)) Figure 4: Failed proof-search and counter-model extraction example. Example 4.7 . In Figure 4 , we give an example of a computation tree for failed proof-search. To improve readability, we use the abbreviations: \varphi:=\Box\neg p , \psi:=\Box((p\rightarrow q)\rightarrow q) , T_{1}:=xRz,z:\psi,z:q\vdash x:\varphi,z:q , and T_{2}:=xRz,z:\psi\vdash x:\varphi,z:q,z:p . To build a counter-model, we take the two stable line sequents that output \mathtt{false} and perform a sequent composition to recover a tree sequent as shown below: T=xRy,xRz,y:\varphi,y:p,z:\psi\vdash y:\bot,x:\psi,x:\varphi,z:q,z:p We define a model \mathbf{M}=(\mathbf{W},\mathbf{R},\mathbf{V}) using T as follows: \mathbf{W}:=\mathsf{Lab}(T)=\{x,y,z\} , \mathbf{R}=\{(x,y),(x,z)\} , and V(p)=\{y\} . In other words, the labels are the worlds in \mathbf{W} , the relational atoms define the accessibility relation \mathbf{R} , and propositional atoms are true at worlds iff they occur in the antecedent of T associated with that world. One can confirm that \mathbf{M},x\not\models\neg\Box\neg p\rightarrow(\Box((p\rightarrow q)\rightarrow q)) . Theorem 4.8 . If \mathtt{prove}(\vdash x:\varphi)=\mathtt{false} , then a model \mathbf{M}=(\mathbf{W},\mathbf{R},\mathbf{V}) can be extracted from the corresponding computation tree such that \mathbf{M}\not\models\varphi . Proof. Suppose \mathtt{prove}(\vdash x:\varphi)=\mathtt{false} and let \mathsf{ct}(x:\varphi)=(\mathsf{V},\mathsf{E},\mathsf{L}) be the corresponding computation tree. We prune the computation tree to obtain a structure (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) from which we can extract a counter-model for \varphi . Let us define (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) as follows: (1) Let (\vdash x:\varphi)\in\mathsf{V}^{\prime} and observe that \mathsf{L}(\vdash x:\varphi)=\mathtt{false} by assumption; (2) If \mathsf{L}(T)=\mathtt{false} and T\in\mathsf{V}^{\prime} concludes a unary rule \mathsf{r}\in\mathsf{CSGL}\setminus\{\Box\mathsf{R}\} in \mathsf{ct}(x:\varphi) with T^{\prime}\in\mathsf{V} the premise, then T^{\prime}\in\mathsf{V}^{\prime} and (T,T^{\prime})\in\mathsf{E}^{\prime} ; (3) If \mathsf{L}(T)=\mathtt{false} and T\in\mathsf{V}^{\prime} is the conclusion of {\rightarrow}\mathsf{L} in \mathsf{ct}(x:\varphi) with T_{1},T_{2}\in\mathsf{V} the premises, then for some i\in\{1,2\} , \mathsf{L}(T_{i})=\mathtt{false} , so for exactly one such i , we let T_{i}\in\mathsf{V}^{\prime} and (T,T_{i})\in\mathsf{E}^{\prime} ; (4) If \mathsf{L}(T)=\mathtt{false} and T\in\mathsf{V}^{\prime} concludes \Box_{\mathsf{DB}} in \mathsf{ct}(x:\varphi) with T_{1},\ldots,T_{n}\in\mathsf{V} the premises, then we let T_{1},\ldots,T_{n}\in\mathsf{V}^{\prime} and (T,T_{1}),\ldots,(T,T_{n})\in\mathsf{E}^{\prime} . Observe that the structure (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) is obtained by starting at the root and taking the downward closure of sequents labeled with \mathtt{false} , with the exception that only a single premise of an {\rightarrow}\mathsf{L} application is retained (i.e., one premise labeled with \mathtt{false} is retained while the other is ignored, regardless of its label). Hence, any branching that occurs in (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) is due to a \Box_{\mathsf{DB}} rule application. Let T_{1},\ldots,T_{n}\in\mathsf{V}^{\prime} be all stable leaves in the structure (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) , and define T^{*}:=T_{1}\odot\cdots\odot T_{n} . We let T_{i}:=\mathcal{T}_{i},\Gamma_{i}\vdash\Delta_{i} for i\in[n] , \mathcal{T}:=\bigcup_{i\in[n]}\mathcal{T}_{i} , \Gamma:=\bigcup_{i\in[n]}\Gamma_{i} , and \Delta:=\bigcup_{i\in[n]}\Delta_{i} , so that \mathcal{T}^{*}=\mathcal{T},\Gamma\vdash\Delta . Recall that T_{1},\ldots,T_{n} must be line sequents. We now define the model \mathbf{M}=(\mathbf{W},\mathbf{R},\mathbf{V}) such that (1) \mathbf{W}:=\mathsf{Lab}(T^{*}) , (2) (y,z)\in\mathbf{R} iff there exist u_{1},\ldots,u_{n}\in\mathsf{Lab}(T^{*}) such that yRu_{1},\ldots,u_{n}Rz\in\mathcal{T} , and (3) y\in\mathbf{V}(p) iff y:p\in\Gamma . We now prove that \mathbf{M} is indeed a model. First, since \vdash x:\varphi was the input to proof-search, we know that x\in\mathbf{W} , and so, \mathbf{W}\neq\emptyset . Second, by construction, we know that \mathcal{T} is a finite tree, meaning, \mathbf{R} is a finite transitively-closed tree. Hence, \mathbf{R} is both transitive and conversely-wellfounded. Last, observe that \mathbf{V} is well-defined. To finish the proof, one proves the following two claims by a mutual induction on the length of \varphi and \psi , for all y\in\mathsf{Lab}(T^{*}) : (i) if y:\varphi\in\Gamma , then \mathbf{M},y\models\varphi and (ii) if y:\psi\in\Delta , then \mathbf{M},y\not\models\psi . We only show the \Box -cases and note that the remaining cases can be found in the appendix. \varphi=\Box\chi. Suppose y:\Box\chi\in\Gamma . Let z\in\mathbf{W} with (y,z)\in\mathbf{R} . Then, there exist u_{1},\ldots,u_{n}\in\mathsf{Lab}(T^{*}) such that yRu_{1},\ldots,u_{n}Rz\in\mathcal{T} by definition. Since \mathcal{T} is the composition of n line sequents, we know that some i\in[n] exists such that yRu_{1},\ldots,u_{n}Rz\in\mathcal{T}_{i} for T_{i}=\mathcal{T}_{i},\Gamma_{i}\vdash\Delta_{i} . As T_{i} is saturated, we know that z\in\chi\in\Gamma_{i}\subseteq\Gamma . By IH, \mathbf{M},z\models\chi , meaning, \mathbf{M},y\models\Box\chi since z was arbitrary. \psi=\Box\chi. Suppose y:\Box\chi\in\Delta . Then, there exists some stable line sequent T_{i}=\mathcal{T}_{i},\Gamma_{i}\vdash\Delta_{i} such that y:\Box\chi\in\Delta_{i} . Since T_{i} is stable and y:\Box\chi\in\Delta_{i} , it cannot be the case that y is a leaf; otherwise, T_{i} would not be stable. Hence, there must exist a z\in\mathsf{Lab}(T^{*}) such that yRz\in\mathcal{T}_{i} . Let us consider the \Box_{\mathsf{DB}} application on the path from T_{i} to the root of (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) which introduced yRz with z fresh, and let T_{i}^{\prime}=\mathcal{T}_{i}^{\prime},\Gamma_{i}^{\prime}\vdash\Delta_{i}^{\prime} be the conclusion of \Box_{\mathsf{DB}} . Since y:\Box\chi\in\Delta_{i} , by inspection of the rules applied during proof-search, one will find that y:\Box\chi\in\Delta_{i}^{\prime} . Furthermore, observe that \mathsf{L}(T_{i}^{\prime})=\mathtt{false} , meaning, every premise of the \Box_{\mathsf{DB}} application will be labeled with \mathtt{false} as well. Thus, there will exist some premise T_{j}^{\prime}=\mathcal{T}_{j}^{\prime},\Gamma_{j}^{\prime}\vdash\Delta_{j}^{\prime} such that yRu\in\mathcal{T}_{j}^{\prime} and u:\chi\in\Delta_{j}^{\prime} . By the definition of (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) , there will exist a stable tree sequent T_{j}=\mathcal{T}_{j},\Gamma_{j}\vdash\Delta_{j} that is a leaf in (\mathsf{V}^{\prime},\mathsf{E}^{\prime}) above T_{j}^{\prime} such that yRu\in\mathcal{T}_{j} and u:\chi\in\Delta_{j} . Consequently, yRu\in\mathcal{T} and u:\chi\in\Delta , so by the definition of \mathbf{M} and IH, we know that there exists a u\in\mathbf{W} such that (y,u)\in\mathbf{R} and \mathbf{M},u\not\models\chi . This implies that \mathbf{M},y\not\models\Box\chi . This concludes the proof. ∎ Finally, we show that \mathtt{prove} terminates within \mathsf{PSPACE} . The proof of this result demonstrates the interaction between termination and the diagonal formula y:\Box\varphi introduced by the \Box\mathsf{R} rule. In particular, the presence of the diagonal formula bounds the depth of tree sequents generated during proof-search, eliminating the need for loop-checking despite the presence of transitivity–a phenomenon previously observed in Gentzen sequent calculi [ 24 ] and labeled sequent calculi [ 20 ] . Theorem 4.9 . For any \varphi\in\mathscr{L} , \mathtt{prove}(\vdash x:\varphi) terminates in \mathsf{PSPACE} . Proof. Let N:=|\mathsf{sufo}(\varphi)| , that is, N is the number of subformulae of \varphi . Recall that every computation tree generated by \mathtt{prove} is line-like and end-active. We first show that for every line sequent of the form xRy_{1},\ldots,y_{n{-}1}Ry_{n},\Gamma\vdash\Delta generated during the computation of \mathtt{prove}(\vdash x:\varphi) , we have n\leq N . In other words, the length (i.e., number of relational atoms) of any line sequent is bounded by N . For a contradiction, suppose the opposite, i.e., a line sequent xRy_{1},\ldots,y_{n{-}1}Ry_{n},\Gamma\vdash\Delta was generated by \mathtt{prove}(\vdash x:\varphi) such that n>N . Let \Box\psi_{1},\ldots,\Box\psi_{k}\in\mathsf{sufo}(\varphi) be all \Box -subformulae of \varphi . By the definition of a subformula, it must be the case that k\leq N . Observe that each relational atom was introduced via a \Box_{\mathsf{DB}} application with a principal formula \Box\psi_{i} , and so, there must exist n applications of \Box_{\mathsf{DB}} along the branch \mathcal{B} of the computation tree from the input \vdash x:\varphi to xRy_{1},\ldots,y_{n{-}1}Ry_{n},\Gamma\vdash\Delta . By the pigeonhole principle, it follows that a subformula \Box\psi_{\ell} was principal twice along the branch \mathcal{B} , i.e., for some i