DECIDABILITY AND COMPLEXITY

.

x−→ y, x : A ⇒ B^A 1,. . . , x : A ⇒ Bn, y : B1 y : C

(⇒ L) x−→ y, x : A ⇒ B^A 1,. . . , x : A ⇒ Bn y : C

(⇒ R) x : A⇒ B¹,. . . , x : A ⇒ Bⁿ x : A ⇒ C

4. DECIDABILITY AND COMPLEXITY

In this section we analyze SeqS calculi in order to obtain a decision procedure for all conditional systems under consideration.⁷ We first present some com-mon properties, then we analyze separately systems CK{+ ID}{+ MP}, systems CEM{+ ID} and systems CS*.

7Obviously, we restrict our concern to all cut-free systems, i.e. all SeqS systems except SeqCEM+ MP*.

In general, cut-freeness alone does not ensure termination of proof search in a sequent calculus; the presence of labels and of the (⇒L) rule, which increases the complexity of the sequent in a backward proof search, are potential causes of a nonterminating proof search. In this section we show that SeqS’s rules introduce only a finite number of labels in a backward proof search, and that (⇒L) can be applied in a controlled way: these conditions allow to describe a decision procedure for the corresponding logics. We also give explicit complexity bounds for our systems.

As a first step, we show that it is useless to apply (⇒L) on x : A ⇒ B by introducing (looking backward) the same transition formula x−→ y more than^A once in each branch of a proof tree. More in detail, we have the following:

LEMMA4.1 (CONTROLLED USE OF(⇒L)). If    is derivable, then there is a proof of it that does not contain more than one application of (⇒L) (looking backward) on x : A⇒ B introducing the same transition formula x −→ y in^A each branch.

PROOF. Consider a derivation of   in which (⇒L) is applied to x : A ⇒ B with a transition x−→ y more than once in a branch; in particular, consider^A the two highest⁸applications. We have the following situation:

a

1, x : A⇒ B  1, x−→ y^A b

1, x : A⇒ B, y : B  1

(⇒ L)

1, x : A⇒ B  1

...

  

and inaor inbthe rule (⇒L) is applied (looking backward) to x : A ⇒ B by using x−→ y. If the highest application is in ^A awe have:

2, x : A⇒ B  2, x−→ y^A 2, x : A⇒ B, y : B  2

(⇒ L)

2, x : A⇒ B  2

.. .

1, x : A⇒ B  1, x−→ y^A b

1, x : A⇒ B, y : B  1

(⇒ L)

1, x : A⇒ B  1

The application of (⇒L) in the left branch can be permuted over the other rules ina(remember that (⇒L) is invertible, see Theorem 3.11); we have the following proof tree ( _aisaafter the permutation):

 a

1, x : A⇒ B  1, x−→ y, x^A −→ y · · · y : B  · · ·^A (⇒ L)

1, x : A⇒ B  1, x−→ y^A b

1, x : A⇒ B, y : B  1

(⇒ L)

1, x : A⇒ B  1 8The applications having the greatest distance from the root  .

By contraction (Theorem 3.12), we have a proof  _a of 1, x : A ⇒ B 

1, x −→ y, which does not contain any application of (⇒L) on x : A ⇒ B^A introducing the same transition x −→ y (remember that contraction is rule-^A preserving admissible) and then we have the following proof:

 a

1, x : A⇒ B  1, x−→ y^A b

1, x : A⇒ B, y : B  1

(⇒ L)

1, x : A⇒ B  1

...

  

If the highest application is in b the proof is similar and left to the reader.

From now on, we analyze separately the decidability of systems CK{+ ID}{+

MP}, CEM{+ ID} and CS*.

4.1 Termination and Complexity for CK{+ ID}{+ MP}

In this subsection we prove some properties characterizing calculi SeqS for conditional logics CK{+ ID}{+ MP}, in order to give a decision procedure for these systems. From now on we only refer to calculi for these systems unless stated otherwise.

First of all, observe that the calculi are characterized by the following prop-erty:

THEOREM4.2 (PROPERTY OFRIGHT-TRANSITIONFORMULAS). Let the sequent

  , x−→ y^A

with x = y, be derivable, then one of the following sequents:

(1)   

(2) x −→ y  x^F −→ y, where x^A −→ y ∈ ^F is also derivable.

PROOF. (EQ) is the only rule which operates, considering a backward proof search, on a transition formula on the right hand side (consequent) of a sequent.

Thus, we have to consider three cases, analyzing the proof tree of  , x−→ y:^A

•   , x−→ y is an axiom: we have to consider two subcases:^A

 an atom u : P occurs in both  and , therefore    is derivable;

 w : ⊥ ∈ , then    is derivable;

• x−→ y is never principal in the derivation. In this case,    is deriv-^A able, since we can remove an occurrence of x −→ y from every sequent^A descending (looking forward) from some1 1, x−→ y;^A

• x −→ y is introduced (looking forward) by the (EQ) rule: in this case,^A another transition x −→ y must be in , in order to apply (EQ). To see^F this, observe that the only rule that could introduce a transition formula (looking backward) in the antecedent of a sequent is (⇒ R), but it can only introduce a transition of the form x −→ z, where z does not occur in that^F sequent (it is a new label), thus it cannot introduce the transition x−→ y.^F The (EQ) rule is only applied to transition formulas:

u : F  u : A u : A u : F (E Q ) x −→ y  x^F −→ y^A

therefore we can conclude that x−→ y  x^F −→ y is derivable.^A

Notice that this theorem holds for all the systems under consideration, but only if x = y. In systems with MP, considering a backward proof search, the (MP) rule operates on transitions in the consequent, although only on transi-tions of the form x−→ x. In this case the theorem does not hold, as shown by^A the following counterexample:

x : A x−→ x, x : A, x : B^A (MP ) x : A x−→ x, x : B^A

for A and B arbitrary. The sequent x : A x−→ x, x : B is derivable in SeqMP,^A but x : A x : B is not derivable in this system and the second condition is not applicable (no transition formula occurs in the antecedent). The first hypothesis of the theorem (x= y) excludes this situation.

In order to control the application of (⇒L) we show that it is useless to apply (backward) the (⇒L) rule on x : A ⇒ B by introducing a transition x −→ y if^A no x −→ y belongs to the left-hand side of the sequent, since there will be no^A way to prove that transition. This property is stated by the following:

LEMMA4.3 (CONTROLLED USE OF(⇒L)^FORCK{+ ID}{+ MP}). SeqS calculi for CK{+ ID}{+ MP} are complete even if the (⇒L) rule is applied as follows:

, x : A ⇒ B  , x −→ y^A , x : A ⇒ B, y : B   (⇒ L)

, x : A ⇒ B   by choosing a label y such that:

• (for CK{+ ID}) there is a transition x−→ y ∈ ;^A

• (for CK+ MP {+ ID}) there is a transition x−→ y ∈  or y = x.^A

PROOF. Let us consider a derivation where (⇒L) is applied (backward) to

, x : A ⇒ B   by introducing a transition x−→ y such that no transitions^A of the form x−→ y belong to  and y = x. The left premise of the rule is^A

, x : A ⇒ B  , x −→ y: by Theorem 4.2 we have that , x : A ⇒ B   is^A derivable, then the application of (⇒L) under consideration is useless.

In order to get a decision procedure for these logics we need to control the application of (ID) and (MP), whose premises have a higher complexity than the respective conclusions. We prove that it is useless to apply (ID) and (MP) more than once on the same transition in each derivation branch, as stated by the following lemmas:

LEMMA4.4 (CONTROLLED USE OF(ID)). It is useless to apply (ID) on the same transition x −→ y more than once in a backward proof search in each branch^A of a derivation.

PROOF. Consider a proof where (ID) is applied more than once on the same transition in a derivation and consider the two highest applications: since (ID) is invertible (Theorem 3.11), we can consider, without loss of generality, that the two applications of (ID) are consecutive, as follows:

(1), x−→ y, y : A, y : A  ^A (I D)

, x−→ y, y : A  ^A (I D)

, x−→ y  ^A

From (1) we can find a derivation of (1 ), x −→ y, y : A   by contraction,^A and this derivation does not have any application of (ID) having x −→ y as a^A principal formula (remember that contraction is rule-preserving admissible).

Thus, we can remove one application of (ID) as follows:

(1 ), x−→ y, y : A  ^A (I D)

, x−→ y  ^A

LEMMA4.5 (CONTROLLED USE OF(MP)). It is useless to apply (MP) on the same transition x −→ x more than once in a backward proof search in each branch^A of a derivation.

PROOF. The proof is similar to the proof of Lemma 4.4 and left to the reader.

Now we have all the elements to prove the decidability of systems for CK{+

ID}{+ MP}:

THEOREM4.6 (TERMINATION FORCK{+ MP}{+ ID}). Systems SeqCK, SeqID, SeqMP and SeqID+ MP ensure termination.

PROOF. In all rules the premises have a smaller complexity than the conclu-sion, except (⇒L), (ID) and (MP). However, Lemma 4.1 guarantees that (⇒L) can be applied in a controlled way; that is, one needs to apply (⇒L) only once

on a formula x : A ⇒ B with the same transition x −→ y in each branch.^A Moreover, considering a derivation of a sequent, x : A ⇒ B  , the num-ber of applications of (⇒L) on x : A ⇒ B is bounded by the cardinality of B = {x −→ y | x^A −→ y ∈ }^{A 9} by Lemma 4.3. The number of different y such that x−→ y ∈ B is finite, since labels are introduced only by conditional^A formulas occurring negatively in the initial sequent, which are finite.

Lemmas 4.4 and 4.5 guarantee that we need only a finite number of appli-cations of (ID) and (MP) in a backward proof search. Moreover, observe that the rules are analytic, so that the premises contain only (labeled) subformulas of the formulas in the conclusion. In the search of a proof of x0 : D, with

| D |= n, new labels are introduced only by conditional subformulas occurring negatively in D.

The number of different labels occurring in a proof is O(n), and the length of each branch of a proof tree is bounded by O(n²).

This itself gives decidability:

THEOREM4.7 (CK{+ ID}{+ MP} DECIDABILITY). Logic CK{ + ID} is decidable.

PROOF. We just observe that there is only a finite number of derivations to check of a given sequent x0: D, as both the length of a proof and the number of labelled formulas which may occur in it is finite.

We conclude this subsection by giving an explicit space complexity bound for CK{+ ID}{+ MP}. As usual, a proof may have an exponential size because of the branching introduced by the rules. However we can obtain a much sharper space complexity bound since we do not need to store the whole proof, but only a sequent at a time plus additional information to carry on the proof search; this standard technique in similar to Hudelmaier [1993] and Vigan`o [2000] (more details are given in Theorem 4.6 in Olivetti et al. [2005]).

THEOREM4.8 (SPACECOMPLEXITY OFCK{+ ID}{+ MP}). Provability in CK{+

ID}{+ MP} is decidable in O(n² log n) space.

4.2 Termination and Complexity for CK+ CEM{+ ID}

In this subsection we analyze sequent calculi containing (CEM). In order to show that SeqCEM{+ ID} ensure termination we proceed in a similar manner as we made in the previous subsection; in particular, we have to show that both (CEM) and (⇒L) rules can be applied in a controlled way. The principal formula of these rules is maintained in their premises, and this is a potential cause of nontermination in a backward proof search. However, we prove that the number of applications of both (CEM) and (⇒L) is finite, and this gives the decidability.

9In systems allowing the (MP) rule the number of applications of (⇒L) is bounded by the cardinality ofB = {x−→ y | x^A −→ y ∈ } ∪ {x^A −→ x}.^A

LEMMA4.9 (CONTROLLED USE OF(CEM) (PART1)). SeqCEM{+ ID} are com-plete even if the (CEM) rule is applied with the following restrictions:

, x−→ y  , x^A −→ z^A (, x−→ y  )[ y/u, z/u]^A

(CEM )

, x−→ y  ^A (1) y = z;

(2) there exists a transition x−→ z ∈ .^A

PROOF. Consider the transition x−→ z introduced (backward) by the (CEM)^A rule in its left premise. If it is introduced by weakening, it can be removed and we are done (the application of (CEM) is useless). Otherwise, it derives (forward) from an application of (EQ) or it is used in the derivation of the right premise of another application of (CEM) by the identification of labels (for instance (CEM) is also applied to x −→ y and in the right premise y and z are identified with^B a new label u). In the first case, a transition x −→ z must belong to  and^A the restriction 2. is satisfied. In the second case, we observe that x −→ z still^A appears in the right-hand side of the left premise of the rule, therefore it can be derived by (EQ) or used by (CEM) in the derivation of the right premise, and so on. Obviously, given a proof tree of  , x −→ z, we can repeat this^A reasoning on each left premise of an application of (CEM) using x −→ z in^A its right derivation, until we find that x −→ z is derived by an application^A of (EQ) or by weakening, since the proof tree is finite, as shown below (we can assume, without loss of generality, that all the applications of (CEM) are consecutive, since (CEM) is invertible and then we can permute it over the other rules):



  n, x −→ z^A ...

...

  2, x−→ z^A ...

(C E M )

  1, x−→ z^A ...

(C E M )

  , x−→ z^A

In  the transition x −→ z can only be introduced by weakening or by an^A application of (EQ) with a transition x −→ z in the left-hand side of a sequent.^A In the first case, all instances of x−→ z can be removed; in the second case, we^A can conclude that the transition x −→ z belongs to ^A , since we can reason as in the proof of Theorem 4.2: (⇒ R) is the only rule introducing (looking backward) a transition x −→ z in the left-hand side of a sequent; moreover, z is a new^A label, then it is not possible that x−→ z is introduced in , since z already^A occurs in all sequents; thus, x−→ z ∈ .^A

Notice that the restriction 1. is the initial restriction given in SeqCEM{+ ID}

in order to avoid a looping application of (CEM).

Similarly to (CEM) we can control the application of (⇒L) as stated by the following:

LEMMA4.10 (CONTROLLED USE OF(⇒L)^FORCEM{+ ID}). SeqCEM{+ ID} is complete even if the (⇒L) rule is applied as follows:

, x : A ⇒ B  , x −→ y^A , x : A ⇒ B, y : B   (⇒ L)

, x : A ⇒ B  

by choosing a label y such that there is a transition x−→ y ∈ .^A PROOF. The proof is similar to the proof of Lemma 4.9.

To prove that SeqCEM{+ ID} ensure termination we also need the following:

LEMMA4.11 (CONTROLLED USE OF(CEM) (PART2)). It is useless to apply (CEM) to x−→ y by introducing the same transition x^A −→ z in the left premise^A of the rule more than once in each branch of a backward proof search.

PROOF. Consider a proof where (CEM) is applied to x −→ y more than once^A by introducing the same transition x−→ z in a branch; consider the two highest^A applications: since (CEM) is invertible, it permutes over the other rules, then we can consider, without loss of generality, the following proof:

1

, x−→ y  , x^A −→ z, x^A −→ z (, x^A −→ y  . . .)[ y, z/u]^A (C E M )

, x−→ y  , x^A −→ z^A

2

(, x−→ y  )[ y, z/u]^A (C E M )

, x−→ y  ^A

By contraction, one can find a proof ₁of the sequent, x−→ y  , x^A −→ z,^A then we can conclude as follows, obtaining a proof where the upper application of (CEM) has been removed:

 ₁

, x−→ y  , x^A −→ z^A

2

(, x−→ y  )[ y, z/u]^A

(C E M )

, x−→ y  ^A

By the above Lemmas 4.9, 4.10, and 4.11 we prove the decidability of CK+ CEM{+ ID}:

THEOREM4.12 (TERMINATION FORCK+ CEM{+ID}). Systems SeqCEM{+

ID} ensure termination.

PROOF. We proceed as we made for systems CK{+ID}{+MP}. In particular, one can control the application of (⇒L) and (CEM) by Lemmas 4.9, 4.11, 4.10 and 4.1.

As in the case of CK{+ID}{+MP}, this itself gives decidability:

THEOREM4.13 (DECIDABILITY OFCK+ CEM{+ID}). Logic CK + CEM{+ID}

is decidable.

We can easily extend results for space complexity given in the previous sub-section to systems allowing (CEM):

THEOREM4.14 (SPACECOMPLEXITY OFCK+ CEM{+ID}). Provability in CK + CEM{+ID} is decidable in O(n² log n) space.

4.3 Termination and Complexity for CK+ CS*

As we made in the previous subsections, we have to show that one can apply the (⇒L) rule in a controlled way. We have also to show that (CS) can be controlled too.

However, in these systems we have a problem. Consider the following deriva-tion:

In the above derivation there is a loop by the combination of the following facts:

(1) the conditional formulas x : ⇒ A, y :  ⇒ A, . . . , generate new labels in the proof tree;

(2) one may have transitive transitions, as x−→ y, y^ −→ z . . . , x^ −→ z.^ More generally, we can have sequents of the form , x0

A1

−→ xA n derived by applying the (CS) rule. Intu-itively, the reason is that an application of (CS) on xi−1 Ai

−→ xi has the effect of identifying labels xi−1and xi, therefore several backwards applications of this rule lead to a sequent of the form  , u−→ x^An n   , u −→ x^A n, which can be derived for instance by (EQ).

We can remedy to this problem by restricting the application of (⇒L) on

, x : A ⇒ B   by using only transitions x−→ y such that x^A −→ y ∈ .^A The reason why we can control the application of (⇒L) can be explained as follows: one may have transitive transitions since (CS) identifies two labels in its right premise. Indeed, to prove x −→ y, y^A −→ z  x^A −→ z one can^A apply (CS) on x −→ y: the right premise u^A −→ u, u^A −→ z  u^A −→ z is^A derivable by the identification of labels x and y with u. However, the transition x −→ z is maintained in the left premise, where it can only be introduced by^A

an application of (EQ) or by weakening. The intuition is that if one needs to propagate a conditional x : A⇒ B from x to y, and then to z by an application of (CS), where (CS) has the effect of identifying x and y, then one can first identify labels x and y with u by (CS), and then propagate the conditional u : A⇒ B from u to z by an application of (⇒L).

LEMMA4.16 (CONTROLLED USE OF(⇒L)^FORCS*). SeqCS* are complete even if the (⇒L) rule is applied as follows:

, x : A ⇒ B  , x −→ y^A , x : A ⇒ B, y : B   (⇒ L)

, x : A ⇒ B   by choosing a label y such that:

• (for systems without MP) there is a transition x−→ y ∈ ;^A

• (for systems with MP) there is a transition x−→ y ∈  or y = x.^A

PROOF. Consider a proof tree where (⇒L) is applied introducing transitions by transitivity; the situation is as follows (as usual, we denote with(u) the substitution[x/u, y/u]): where (⇒L) is applied without introducing transitions by transitivity. If x−→ z^A derives in 1 by an application of (EQ), then a transition x −→ z belongs^C to the left-hand side of the sequent, therefore (⇒L) is applied respecting the restriction stated by this lemma. Otherwise, x−→ z can be removed in ^A 1, since it is introduced by weakening.¹⁰ Therefore, there is a proof ₁ of the sequent

, x −→ y, y^A −→ z, x : A ⇒ B  , x : A^A . Moreover, by applying the label substitution (Lemma 3.9) to the sequent derived by proof3 we can obtain a proof ₃ of(u), u −→ u, u^A −→ z, u : A ⇒ B, z : B  (u). We can conclude^A by applying first the (CS) rule (to identify labels x and y with u) and then by propagating the conditional formula from u to z, as follows:

 1

10We can have several consecutive applications of (CS). However, as in the case of (CEM), x−→ z^A can be derived either by (EQ) or by weakening since it is maintained in the consequent of the left premise of (CS).

where the (⇒L) rule has been applied respecting the restriction of this lemma, that is, by introducing (backward) a transition u −→ z such that u^A −→ z^A belongs to the left-hand side of the sequent. We proceed in the same manner if we have a proof where (CS) is applied on y −→ z and also when the transition^A x0

−→ xA nis used to apply (⇒L) on , x0 A1

−→ x1, x1 A2

−→ x2,. . . , xn−1 An

−→ xn. As in the case of (CEM) we need to show that (CS) can be applied in a controlled way, in order to show that SeqCS* ensure termination.

LEMMA4.17 (CONTROLLED USE OF(CS)). It is useless to apply (CS) on the same transition x −→ y more than once in each branch of a backward proof search.^A

PROOF. Consider a branch where (CS) is applied more than once on x−→ y^A and consider the two highest applications; without loss of generality, we can consider the following proof since (CS) is invertible (see Theorem 3.11, as usual we denote(u) = [x/u, y/u]):

(1), x−→ y  , x : A, x : A^A (u), u−→ u  (u), u : A^A

, x−→ y  , x : A^A (CS) (2)(u), u−→ u  (u)^A

, x−→ y  ^A (CS)

By Theorem 3.12 we can find a proof of (1 ), x −→ y  , x : A, thus we^A conclude as follows:

(1 ), x−→ y  , x : A^A (2)(u), u−→ u  (u)^A (CS)

, x−→ y  ^A

We have found a derivation of the initial sequent in which a useless applica-tion of (CS) has been removed.

Now we have all the elements to prove the following:

THEOREM4.18 (TERMINATION FORCK+ CS*). Systems SeqCS* ensure termi-nation.

PROOF. One can control the application of (⇒L) by Lemma 4.16 and of (CS) by Lemma 4.17. For systems with (ID) and/or (MP), one can control the ap-plication of these rules since Lemmas 4.4 and 4.5 hold in systems with (CS) too. In the case of SeqCEM + CS* just observe that one can control the ap-plication of (CEM) in this way: one needs to apply (CEM) on , x−→ y  ^A by using a transition x−→ z (i.e., premises are , x^A −→ y  , x^A −→ z and^A (, x −→ y  )[ y/u, z/u]) such that x^A −→ z ∈ , since Lemma 4.9 holds in^A these systems too. Moreover, one needs to apply (CEM) at most once by using the same transition x −→ z in each branch, since we can easily observe that^A Lemma 4.11 holds in these systems.¹¹The number of applications of (⇒L) and

11We can repeat the same proof of the theorem even if we have (CS), since (CEM) and (CS) are both invertible.

Fig. 4. Rules (ID) and (MP) reformulated for CK{+ID}{+MP}.

(CEM) is finite, since the number of transitions introduced by conditionals oc-curring negatively in the initial sequent of a backward proof search is finite.

As in the previous cases, this itself gives decidability:

THEOREM4.19 (DECIDABILITY OFCK+ CS*). Logics CK + CS* are decidable.

We conclude by giving an explicit space complexity bound:

THEOREM4.20 (SPACECOMPLEXITY OFCK+ CS*). Provability in CK + CS* is decidable in O(n² log n) space.

Nel documento A Sequent Calculus and a Theorem Prover for Standard Conditional Logics (pagine 22-33)