/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) QTRSRRRProof [EQUIVALENT, 145 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 0 ms]
(4) QTRS
(5) RisEmptyProof [EQUIVALENT, 0 ms]
(6) YES


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

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

   a__eq(0, 0) -> true
   a__eq(s(X), s(Y)) -> a__eq(X, Y)
   a__eq(X, Y) -> false
   a__inf(X) -> cons(X, inf(s(X)))
   a__take(0, X) -> nil
   a__take(s(X), cons(Y, L)) -> cons(Y, take(X, L))
   a__length(nil) -> 0
   a__length(cons(X, L)) -> s(length(L))
   mark(eq(X1, X2)) -> a__eq(X1, X2)
   mark(inf(X)) -> a__inf(mark(X))
   mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
   mark(length(X)) -> a__length(mark(X))
   mark(0) -> 0
   mark(true) -> true
   mark(s(X)) -> s(X)
   mark(false) -> false
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(nil) -> nil
   a__eq(X1, X2) -> eq(X1, X2)
   a__inf(X) -> inf(X)
   a__take(X1, X2) -> take(X1, X2)
   a__length(X) -> length(X)

Q is empty.

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

(1) QTRSRRRProof (EQUIVALENT)
Used ordering:
Quasi precedence:
[a__eq_2, a__length_1, length_1, mark_1] > true > [s_1, cons_2, inf_1]
[a__eq_2, a__length_1, length_1, mark_1] > false > [s_1, cons_2, inf_1]
[a__eq_2, a__length_1, length_1, mark_1] > a__inf_1 > [s_1, cons_2, inf_1]
[a__eq_2, a__length_1, length_1, mark_1] > a__take_2 > nil > 0 > [s_1, cons_2, inf_1]
[a__eq_2, a__length_1, length_1, mark_1] > a__take_2 > take_2 > [s_1, cons_2, inf_1]
[a__eq_2, a__length_1, length_1, mark_1] > eq_2 > [s_1, cons_2, inf_1]


Status:
a__eq_2: multiset status
0: multiset status
true: multiset status
s_1: multiset status
false: multiset status
a__inf_1: multiset status
cons_2: multiset status
inf_1: multiset status
a__take_2: multiset status
nil: multiset status
take_2: multiset status
a__length_1: multiset status
length_1: multiset status
mark_1: multiset status
eq_2: multiset status

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

   a__eq(0, 0) -> true
   a__eq(s(X), s(Y)) -> a__eq(X, Y)
   a__eq(X, Y) -> false
   a__inf(X) -> cons(X, inf(s(X)))
   a__take(0, X) -> nil
   a__take(s(X), cons(Y, L)) -> cons(Y, take(X, L))
   a__length(nil) -> 0
   a__length(cons(X, L)) -> s(length(L))
   mark(eq(X1, X2)) -> a__eq(X1, X2)
   mark(inf(X)) -> a__inf(mark(X))
   mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
   mark(0) -> 0
   mark(true) -> true
   mark(s(X)) -> s(X)
   mark(false) -> false
   mark(cons(X1, X2)) -> cons(X1, X2)
   mark(nil) -> nil
   a__eq(X1, X2) -> eq(X1, X2)
   a__inf(X) -> inf(X)
   a__take(X1, X2) -> take(X1, X2)




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

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

   mark(length(X)) -> a__length(mark(X))
   a__length(X) -> length(X)

Q is empty.

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

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:mark_1 > a__length_1 > length_1

and weight map:

   mark_1=2
   length_1=1
   a__length_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(length(X)) -> a__length(mark(X))
   a__length(X) -> length(X)




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

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

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

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

(6)
YES