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


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

(0) QTRS
(1) QTRSRRRProof [EQUIVALENT, 59 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 17 ms]
(4) QTRS
(5) QTRSRRRProof [EQUIVALENT, 17 ms]
(6) QTRS
(7) QTRSRRRProof [EQUIVALENT, 0 ms]
(8) QTRS
(9) QTRSRRRProof [EQUIVALENT, 12 ms]
(10) QTRS
(11) QTRSRRRProof [EQUIVALENT, 0 ms]
(12) QTRS
(13) QTRSRRRProof [EQUIVALENT, 0 ms]
(14) QTRS
(15) RisEmptyProof [EQUIVALENT, 0 ms]
(16) YES


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

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

   a__nats -> a__adx(a__zeros)
   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   a__hd(cons(X, Y)) -> mark(X)
   a__tl(cons(X, Y)) -> mark(Y)
   mark(nats) -> a__nats
   mark(adx(X)) -> a__adx(mark(X))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(hd(X)) -> a__hd(mark(X))
   mark(tl(X)) -> a__tl(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__nats -> nats
   a__adx(X) -> adx(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)
   a__hd(X) -> hd(X)
   a__tl(X) -> tl(X)

Q is empty.

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

(1) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__adx(x_1)) = x_1
   POL(a__hd(x_1)) = 1 + 2*x_1
   POL(a__incr(x_1)) = x_1
   POL(a__nats) = 0
   POL(a__tl(x_1)) = 1 + 2*x_1
   POL(a__zeros) = 0
   POL(adx(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1 + 2*x_2
   POL(hd(x_1)) = 1 + 2*x_1
   POL(incr(x_1)) = x_1
   POL(mark(x_1)) = 2*x_1
   POL(nats) = 0
   POL(s(x_1)) = x_1
   POL(tl(x_1)) = 1 + 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   a__hd(cons(X, Y)) -> mark(X)
   a__tl(cons(X, Y)) -> mark(Y)
   mark(hd(X)) -> a__hd(mark(X))
   mark(tl(X)) -> a__tl(mark(X))




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

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

   a__nats -> a__adx(a__zeros)
   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   mark(nats) -> a__nats
   mark(adx(X)) -> a__adx(mark(X))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__nats -> nats
   a__adx(X) -> adx(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)
   a__hd(X) -> hd(X)
   a__tl(X) -> tl(X)

Q is empty.

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

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__adx(x_1)) = x_1
   POL(a__hd(x_1)) = 2 + 2*x_1
   POL(a__incr(x_1)) = x_1
   POL(a__nats) = 0
   POL(a__tl(x_1)) = 1 + 2*x_1
   POL(a__zeros) = 0
   POL(adx(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1 + x_2
   POL(hd(x_1)) = 2 + 2*x_1
   POL(incr(x_1)) = x_1
   POL(mark(x_1)) = 2*x_1
   POL(nats) = 0
   POL(s(x_1)) = x_1
   POL(tl(x_1)) = 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   a__tl(X) -> tl(X)




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

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

   a__nats -> a__adx(a__zeros)
   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   mark(nats) -> a__nats
   mark(adx(X)) -> a__adx(mark(X))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__nats -> nats
   a__adx(X) -> adx(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)
   a__hd(X) -> hd(X)

Q is empty.

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

(5) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__adx(x_1)) = x_1
   POL(a__hd(x_1)) = 1 + x_1
   POL(a__incr(x_1)) = x_1
   POL(a__nats) = 0
   POL(a__zeros) = 0
   POL(adx(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1 + x_2
   POL(hd(x_1)) = x_1
   POL(incr(x_1)) = x_1
   POL(mark(x_1)) = 2*x_1
   POL(nats) = 0
   POL(s(x_1)) = x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   a__hd(X) -> hd(X)




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

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

   a__nats -> a__adx(a__zeros)
   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   mark(nats) -> a__nats
   mark(adx(X)) -> a__adx(mark(X))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__nats -> nats
   a__adx(X) -> adx(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)

Q is empty.

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

(7) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__adx(x_1)) = x_1
   POL(a__incr(x_1)) = x_1
   POL(a__nats) = 1
   POL(a__zeros) = 0
   POL(adx(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1 + 2*x_2
   POL(incr(x_1)) = x_1
   POL(mark(x_1)) = 2*x_1
   POL(nats) = 1
   POL(s(x_1)) = x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   a__nats -> a__adx(a__zeros)
   mark(nats) -> a__nats




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

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

   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   mark(adx(X)) -> a__adx(mark(X))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__nats -> nats
   a__adx(X) -> adx(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)

Q is empty.

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

(9) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__adx(x_1)) = x_1
   POL(a__incr(x_1)) = x_1
   POL(a__nats) = 1
   POL(a__zeros) = 0
   POL(adx(x_1)) = x_1
   POL(cons(x_1, x_2)) = 2*x_1 + x_2
   POL(incr(x_1)) = x_1
   POL(mark(x_1)) = x_1
   POL(nats) = 0
   POL(s(x_1)) = x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   a__nats -> nats




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

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

   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   mark(adx(X)) -> a__adx(mark(X))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__adx(X) -> adx(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)

Q is empty.

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

(11) QTRSRRRProof (EQUIVALENT)
Used ordering:
a__zeros/0)
cons/2(YES,YES)
0/0)
zeros/0)
a__incr/1(YES)
s/1)YES(
incr/1(YES)
a__adx/1(YES)
adx/1(YES)
mark/1(YES)

Quasi precedence:
[a__adx_1, adx_1, mark_1] > a__zeros > cons_2
[a__adx_1, adx_1, mark_1] > a__zeros > 0
[a__adx_1, adx_1, mark_1] > a__zeros > zeros
[a__adx_1, adx_1, mark_1] > a__incr_1 > cons_2
[a__adx_1, adx_1, mark_1] > a__incr_1 > incr_1


Status:
a__zeros: multiset status
cons_2: multiset status
0: multiset status
zeros: multiset status
a__incr_1: multiset status
incr_1: multiset status
a__adx_1: multiset status
adx_1: multiset status
mark_1: multiset status

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

   a__zeros -> cons(0, zeros)
   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))
   mark(zeros) -> a__zeros
   mark(incr(X)) -> a__incr(mark(X))
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__zeros -> zeros
   a__incr(X) -> incr(X)




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

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

   mark(adx(X)) -> a__adx(mark(X))
   a__adx(X) -> adx(X)

Q is empty.

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

(13) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:mark_1 > a__adx_1 > adx_1

and weight map:

   mark_1=2
   adx_1=1
   a__adx_1=1

The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   mark(adx(X)) -> a__adx(mark(X))
   a__adx(X) -> adx(X)




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

(14)
Obligation:
Q restricted rewrite system:
R is empty.
Q is empty.

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

(15) RisEmptyProof (EQUIVALENT)
The TRS R is empty. Hence, termination is trivially proven.
----------------------------------------

(16)
YES