YES
proof of /export/starexec/sandbox/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, 31 ms]
(2) QTRS
(3) RisEmptyProof [EQUIVALENT, 0 ms]
(4) YES


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

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

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   appendAll(@l) -> appendAll#1(@l)
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
   appendAll#1(nil) -> nil
   appendAll2(@l) -> appendAll2#1(@l)
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
   appendAll2#1(nil) -> nil
   appendAll3(@l) -> appendAll3#1(@l)
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
   appendAll3#1(nil) -> nil

The set Q consists of the following terms:

   append(x0, x1)
   append#1(::(x0, x1), x2)
   append#1(nil, x0)
   appendAll(x0)
   appendAll#1(::(x0, x1))
   appendAll#1(nil)
   appendAll2(x0)
   appendAll2#1(::(x0, x1))
   appendAll2#1(nil)
   appendAll3(x0)
   appendAll3#1(::(x0, x1))
   appendAll3#1(nil)


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

(1) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:appendAll3#1_1 > appendAll3_1 > appendAll2#1_1 > append_2 > append#1_2 > appendAll2_1 > ::_2 > appendAll_1 > appendAll#1_1 > nil

and weight map:

   nil=1
   appendAll_1=2
   appendAll#1_1=2
   appendAll2_1=2
   appendAll2#1_1=1
   appendAll3_1=1
   appendAll3#1_1=0
   append_2=0
   append#1_2=0
   ::_2=3

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

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   appendAll(@l) -> appendAll#1(@l)
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
   appendAll#1(nil) -> nil
   appendAll2(@l) -> appendAll2#1(@l)
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
   appendAll2#1(nil) -> nil
   appendAll3(@l) -> appendAll3#1(@l)
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
   appendAll3#1(nil) -> nil




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

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

   append(x0, x1)
   append#1(::(x0, x1), x2)
   append#1(nil, x0)
   appendAll(x0)
   appendAll#1(::(x0, x1))
   appendAll#1(nil)
   appendAll2(x0)
   appendAll2#1(::(x0, x1))
   appendAll2#1(nil)
   appendAll3(x0)
   appendAll3#1(::(x0, x1))
   appendAll3#1(nil)


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

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

(4)
YES