YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given ETRS could be proven:

(0) ETRS
(1) RRRPoloETRSProof [EQUIVALENT, 798 ms]
(2) ETRS
(3) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
(4) EDP
(5) EDependencyGraphProof [EQUIVALENT, 0 ms]
(6) TRUE


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

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

   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
   sum(cons(0, cons(plus(x, y), l))) -> pred(sum(cons(s(x), cons(y, l))))
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   pred(cons(s(x), nil)) -> cons(x, nil)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))


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

(1) RRRPoloETRSProof (EQUIVALENT)
The following E TRS is given: Equational rewrite system:
The TRS R consists of the following rules:

   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
   sum(cons(0, cons(plus(x, y), l))) -> pred(sum(cons(s(x), cons(y, l))))
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   pred(cons(s(x), nil)) -> cons(x, nil)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))

The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:

   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
   sum(cons(0, cons(plus(x, y), l))) -> pred(sum(cons(s(x), cons(y, l))))
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   pred(cons(s(x), nil)) -> cons(x, nil)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 2
   POL(app(x_1, x_2)) = 1 + 3*x_1 + 2*x_1*x_2 + x_2
   POL(cons(x_1, x_2)) = 3 + 2*x_1 + x_1*x_2 + 2*x_2
   POL(nil) = 0
   POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2
   POL(pred(x_1)) = 1 + x_1
   POL(s(x_1)) = 3 + x_1
   POL(sum(x_1)) = x_1




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

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

   sum(cons(x, nil)) -> cons(x, nil)
   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))


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

(3) EquationalDependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
The TRS P consists of the following rules:

   SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k)))))
   SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k)))

The TRS R consists of the following rules:

   sum(cons(x, nil)) -> cons(x, nil)
   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))

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

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

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

   SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k)))))
   SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k)))

The TRS R consists of the following rules:

   sum(cons(x, nil)) -> cons(x, nil)
   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))

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

(5) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 2 less nodes.
----------------------------------------

(6)
TRUE