/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) Overlay + Local Confluence [EQUIVALENT, 0 ms]
(2) QTRS
(3) DependencyPairsProof [EQUIVALENT, 0 ms]
(4) QDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) QDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QReductionProof [EQUIVALENT, 0 ms]
        (11) QDP
        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) QDP
        (15) UsableRulesProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) QReductionProof [EQUIVALENT, 0 ms]
        (18) QDP
        (19) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (20) YES
    (21) QDP
        (22) UsableRulesProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QReductionProof [EQUIVALENT, 0 ms]
        (25) QDP
        (26) TransformationProof [EQUIVALENT, 0 ms]
        (27) QDP
        (28) DependencyGraphProof [EQUIVALENT, 0 ms]
        (29) QDP
        (30) UsableRulesProof [EQUIVALENT, 0 ms]
        (31) QDP
        (32) QReductionProof [EQUIVALENT, 0 ms]
        (33) QDP
        (34) TransformationProof [EQUIVALENT, 0 ms]
        (35) QDP
        (36) TransformationProof [EQUIVALENT, 0 ms]
        (37) QDP
        (38) TransformationProof [EQUIVALENT, 0 ms]
        (39) QDP
        (40) UsableRulesProof [EQUIVALENT, 0 ms]
        (41) QDP
        (42) QReductionProof [EQUIVALENT, 0 ms]
        (43) QDP
        (44) TransformationProof [EQUIVALENT, 0 ms]
        (45) QDP
        (46) UsableRulesProof [EQUIVALENT, 0 ms]
        (47) QDP
        (48) QReductionProof [EQUIVALENT, 0 ms]
        (49) QDP
        (50) TransformationProof [EQUIVALENT, 0 ms]
        (51) QDP
        (52) UsableRulesProof [EQUIVALENT, 0 ms]
        (53) QDP
        (54) QReductionProof [EQUIVALENT, 0 ms]
        (55) QDP
        (56) TransformationProof [EQUIVALENT, 0 ms]
        (57) QDP
        (58) UsableRulesProof [EQUIVALENT, 0 ms]
        (59) QDP
        (60) TransformationProof [EQUIVALENT, 0 ms]
        (61) QDP
        (62) QDPOrderProof [EQUIVALENT, 0 ms]
        (63) QDP
        (64) DependencyGraphProof [EQUIVALENT, 0 ms]
        (65) QDP
        (66) QDPOrderProof [EQUIVALENT, 14 ms]
        (67) QDP
        (68) DependencyGraphProof [EQUIVALENT, 0 ms]
        (69) TRUE


----------------------------------------

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   isZero(0) -> true
   isZero(s(x)) -> false
   head(cons(x, xs)) -> x
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   sumList(xs, y) -> if(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   if(true, b, y, xs, ys, x) -> y
   if(false, true, y, xs, ys, x) -> sumList(xs, y)
   if(false, false, y, xs, ys, x) -> sumList(ys, x)
   sum(xs) -> sumList(xs, 0)

Q is empty.

----------------------------------------

(1) Overlay + Local Confluence (EQUIVALENT)
The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
----------------------------------------

(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   isZero(0) -> true
   isZero(s(x)) -> false
   head(cons(x, xs)) -> x
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   sumList(xs, y) -> if(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   if(true, b, y, xs, ys, x) -> y
   if(false, true, y, xs, ys, x) -> sumList(xs, y)
   if(false, false, y, xs, ys, x) -> sumList(ys, x)
   sum(xs) -> sumList(xs, 0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)


----------------------------------------

(3) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(4)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(s(s(x))) -> P(s(x))
   INC(s(x)) -> INC(x)
   SUMLIST(xs, y) -> IF(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   SUMLIST(xs, y) -> ISEMPTY(xs)
   SUMLIST(xs, y) -> ISZERO(head(xs))
   SUMLIST(xs, y) -> HEAD(xs)
   SUMLIST(xs, y) -> TAIL(xs)
   SUMLIST(xs, y) -> P(head(xs))
   SUMLIST(xs, y) -> INC(y)
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUM(xs) -> SUMLIST(xs, 0)

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   isZero(0) -> true
   isZero(s(x)) -> false
   head(cons(x, xs)) -> x
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   sumList(xs, y) -> if(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   if(true, b, y, xs, ys, x) -> y
   if(false, true, y, xs, ys, x) -> sumList(xs, y)
   if(false, false, y, xs, ys, x) -> sumList(ys, x)
   sum(xs) -> sumList(xs, 0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes.
----------------------------------------

(6)
Complex Obligation (AND)

----------------------------------------

(7)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   INC(s(x)) -> INC(x)

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   isZero(0) -> true
   isZero(s(x)) -> false
   head(cons(x, xs)) -> x
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   sumList(xs, y) -> if(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   if(true, b, y, xs, ys, x) -> y
   if(false, true, y, xs, ys, x) -> sumList(xs, y)
   if(false, false, y, xs, ys, x) -> sumList(ys, x)
   sum(xs) -> sumList(xs, 0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(8) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   INC(s(x)) -> INC(x)

R is empty.
The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(10) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)


----------------------------------------

(11)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   INC(s(x)) -> INC(x)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(12) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*INC(s(x)) -> INC(x)
The graph contains the following edges 1 > 1


----------------------------------------

(13)
YES

----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(s(s(x))) -> P(s(x))

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   isZero(0) -> true
   isZero(s(x)) -> false
   head(cons(x, xs)) -> x
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   sumList(xs, y) -> if(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   if(true, b, y, xs, ys, x) -> y
   if(false, true, y, xs, ys, x) -> sumList(xs, y)
   if(false, false, y, xs, ys, x) -> sumList(ys, x)
   sum(xs) -> sumList(xs, 0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(s(s(x))) -> P(s(x))

R is empty.
The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(17) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)


----------------------------------------

(18)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(s(s(x))) -> P(s(x))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(19) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*P(s(s(x))) -> P(s(x))
The graph contains the following edges 1 > 1


----------------------------------------

(20)
YES

----------------------------------------

(21)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(xs, y) -> IF(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   isZero(0) -> true
   isZero(s(x)) -> false
   head(cons(x, xs)) -> x
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   sumList(xs, y) -> if(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   if(true, b, y, xs, ys, x) -> y
   if(false, true, y, xs, ys, x) -> sumList(xs, y)
   if(false, false, y, xs, ys, x) -> sumList(ys, x)
   sum(xs) -> sumList(xs, 0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(22) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(23)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(xs, y) -> IF(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)
   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(24) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   sumList(x0, x1)
   if(true, x0, x1, x2, x3, x4)
   if(false, true, x0, x1, x2, x3)
   if(false, false, x0, x1, x2, x3)
   sum(x0)


----------------------------------------

(25)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(xs, y) -> IF(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y))
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(26) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule SUMLIST(xs, y) -> IF(isEmpty(xs), isZero(head(xs)), y, tail(xs), cons(p(head(xs)), tail(xs)), inc(y)) at position [0] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)),SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)))
   (SUMLIST(nil, y1) -> IF(true, isZero(head(nil)), y1, tail(nil), cons(p(head(nil)), tail(nil)), inc(y1)),SUMLIST(nil, y1) -> IF(true, isZero(head(nil)), y1, tail(nil), cons(p(head(nil)), tail(nil)), inc(y1)))


----------------------------------------

(27)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1))
   SUMLIST(nil, y1) -> IF(true, isZero(head(nil)), y1, tail(nil), cons(p(head(nil)), tail(nil)), inc(y1))

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(28) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(29)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1))
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   isEmpty(cons(x, xs)) -> false
   isEmpty(nil) -> true
   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   tail(nil) -> nil
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(30) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(31)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1))
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isEmpty(cons(x0, x1))
   isEmpty(nil)
   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(32) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   isEmpty(cons(x0, x1))
   isEmpty(nil)


----------------------------------------

(33)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1))
   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(34) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(head(cons(x0, x1))), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)) at position [1,0] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)),SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)))


----------------------------------------

(35)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1))

The TRS R consists of the following rules:

   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(36) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, tail(cons(x0, x1)), cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)) at position [3] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)),SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)))


----------------------------------------

(37)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1))

The TRS R consists of the following rules:

   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(38) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(head(cons(x0, x1))), tail(cons(x0, x1))), inc(y1)) at position [4,0,0] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), tail(cons(x0, x1))), inc(y1)),SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), tail(cons(x0, x1))), inc(y1)))


----------------------------------------

(39)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), tail(cons(x0, x1))), inc(y1))

The TRS R consists of the following rules:

   head(cons(x, xs)) -> x
   isZero(0) -> true
   isZero(s(x)) -> false
   tail(cons(x, xs)) -> xs
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(40) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(41)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), tail(cons(x0, x1))), inc(y1))

The TRS R consists of the following rules:

   isZero(0) -> true
   isZero(s(x)) -> false
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   tail(cons(x, xs)) -> xs
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   head(cons(x0, x1))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(42) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   head(cons(x0, x1))


----------------------------------------

(43)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), tail(cons(x0, x1))), inc(y1))

The TRS R consists of the following rules:

   isZero(0) -> true
   isZero(s(x)) -> false
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   tail(cons(x, xs)) -> xs
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(44) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), tail(cons(x0, x1))), inc(y1)) at position [4,1] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), x1), inc(y1)),SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), x1), inc(y1)))


----------------------------------------

(45)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), x1), inc(y1))

The TRS R consists of the following rules:

   isZero(0) -> true
   isZero(s(x)) -> false
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   tail(cons(x, xs)) -> xs
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(46) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(47)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), x1), inc(y1))

The TRS R consists of the following rules:

   isZero(0) -> true
   isZero(s(x)) -> false
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   tail(cons(x0, x1))
   tail(nil)
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(48) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   tail(cons(x0, x1))
   tail(nil)


----------------------------------------

(49)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), x1), inc(y1))

The TRS R consists of the following rules:

   isZero(0) -> true
   isZero(s(x)) -> false
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(50) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule SUMLIST(cons(x0, x1), y1) -> IF(false, isZero(x0), y1, x1, cons(p(x0), x1), inc(y1)) at position [1] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(p(0), y1), inc(y2)),SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(p(0), y1), inc(y2)))
   (SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2)),SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2)))


----------------------------------------

(51)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(p(0), y1), inc(y2))
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))

The TRS R consists of the following rules:

   isZero(0) -> true
   isZero(s(x)) -> false
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   p(0) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(52) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(53)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(p(0), y1), inc(y2))
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))

The TRS R consists of the following rules:

   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(0) -> 0

The set Q consists of the following terms:

   isZero(0)
   isZero(s(x0))
   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(54) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   isZero(0)
   isZero(s(x0))


----------------------------------------

(55)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(p(0), y1), inc(y2))
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))

The TRS R consists of the following rules:

   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(0) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(56) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(p(0), y1), inc(y2)) at position [4,0] we obtained the following new rules [LPAR04]:

   (SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(0, y1), inc(y2)),SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(0, y1), inc(y2)))


----------------------------------------

(57)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(0, y1), inc(y2))

The TRS R consists of the following rules:

   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0
   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(0) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(58) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(59)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y)
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(0, y1), inc(y2))

The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(60) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule IF(false, true, y, xs, ys, x) -> SUMLIST(xs, y) we obtained the following new rules [LPAR04]:

   (IF(false, true, z1, z0, cons(0, z0), y_0) -> SUMLIST(z0, z1),IF(false, true, z1, z0, cons(0, z0), y_0) -> SUMLIST(z0, z1))


----------------------------------------

(61)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(0, y1), inc(y2))
   IF(false, true, z1, z0, cons(0, z0), y_0) -> SUMLIST(z0, z1)

The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(62) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   IF(false, true, z1, z0, cons(0, z0), y_0) -> SUMLIST(z0, z1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
IF(x1, x2, x3, x4, x5, x6)  =  x5

SUMLIST(x1, x2)  =  x1

cons(x1, x2)  =  cons(x2)


Knuth-Bendix order [KBO] with precedence:trivial

and weight map:

   dummyConstant=1
   cons_1=1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
none


----------------------------------------

(63)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))
   SUMLIST(cons(0, y1), y2) -> IF(false, true, y2, y1, cons(0, y1), inc(y2))

The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(64) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(65)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))
   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)

The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(66) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   IF(false, false, y, xs, ys, x) -> SUMLIST(ys, x)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( IF_6(x_1, ..., x_6) ) = 2x_1 + x_2 + 2x_5 + 1
POL( cons_2(x_1, x_2) ) = max{0, 2x_1 - 2}
POL( p_1(x_1) ) = max{0, x_1 - 2}
POL( s_1(x_1) ) = x_1 + 2
POL( 0 ) = 0
POL( inc_1(x_1) ) = 2
POL( SUMLIST_2(x_1, x_2) ) = 2x_1
POL( false ) = 1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0


----------------------------------------

(67)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SUMLIST(cons(s(x0), y1), y2) -> IF(false, false, y2, y1, cons(p(s(x0)), y1), inc(y2))

The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   p(s(s(x))) -> s(p(s(x)))
   p(s(0)) -> 0

The set Q consists of the following terms:

   p(s(s(x0)))
   p(s(0))
   p(0)
   inc(s(x0))
   inc(0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(68) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(69)
TRUE