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, 88 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 0 ms]
(4) QTRS
(5) QTRSRRRProof [EQUIVALENT, 12 ms]
(6) QTRS
(7) QTRSRRRProof [EQUIVALENT, 0 ms]
(8) QTRS
(9) QTRSRRRProof [EQUIVALENT, 4 ms]
(10) QTRS
(11) QTRSRRRProof [EQUIVALENT, 5 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)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

(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)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

(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)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

(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)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

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

Quasi precedence:
mark_1 > [a__nats, a__zeros] > cons_2
mark_1 > [a__nats, a__zeros] > 0
mark_1 > [a__nats, a__zeros] > zeros
mark_1 > [a__nats, a__zeros] > nats


Status:
a__nats: multiset status
a__zeros: multiset status
cons_2: multiset status
0: multiset status
zeros: multiset status
mark_1: multiset status
nats: 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)
   mark(nats) -> a__nats
   mark(zeros) -> a__zeros
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(0) -> 0
   mark(s(X)) -> s(X)
   a__nats -> nats
   a__zeros -> zeros




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

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

   a__nats -> a__adx(a__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(incr(X)) -> a__incr(mark(X))
   a__adx(X) -> adx(X)
   a__incr(X) -> incr(X)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

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

   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(s(x_1)) = x_1
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)




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

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

   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(incr(X)) -> a__incr(mark(X))
   a__adx(X) -> adx(X)
   a__incr(X) -> incr(X)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

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

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

   a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y)))




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

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

   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   mark(adx(X)) -> a__adx(mark(X))
   mark(incr(X)) -> a__incr(mark(X))
   a__adx(X) -> adx(X)
   a__incr(X) -> incr(X)

The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

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

and weight map:

   a__incr_1=1
   s_1=0
   incr_1=1
   mark_1=2
   adx_1=1
   a__adx_1=1
   cons_2=0

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

   a__incr(cons(X, Y)) -> cons(s(X), incr(Y))
   mark(adx(X)) -> a__adx(mark(X))
   mark(incr(X)) -> a__incr(mark(X))
   a__adx(X) -> adx(X)
   a__incr(X) -> incr(X)




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

(14)
Obligation:
Q restricted rewrite system:
R is empty.
The set Q consists of the following terms:

   a__nats
   a__zeros
   mark(nats)
   mark(adx(x0))
   mark(zeros)
   mark(incr(x0))
   mark(hd(x0))
   mark(tl(x0))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   a__adx(x0)
   a__incr(x0)
   a__hd(x0)
   a__tl(x0)


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

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

(16)
YES