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, 30 ms]
(2) QTRS
(3) RisEmptyProof [EQUIVALENT, 0 ms]
(4) YES


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

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

   group3(@l) -> group3#1(@l)
   group3#1(::(@x, @xs)) -> group3#2(@xs, @x)
   group3#1(nil) -> nil
   group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y)
   group3#2(nil, @x) -> nil
   group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs))
   group3#3(nil, @x, @y) -> nil
   zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3)
   zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs)
   zip3#1(nil, @l2, @l3) -> nil
   zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys)
   zip3#2(nil, @l3, @x, @xs) -> nil
   zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs))
   zip3#3(nil, @x, @xs, @y, @ys) -> nil

The set Q consists of the following terms:

   group3(x0)
   group3#1(::(x0, x1))
   group3#1(nil)
   group3#2(::(x0, x1), x2)
   group3#2(nil, x0)
   group3#3(::(x0, x1), x2, x3)
   group3#3(nil, x0, x1)
   zip3(x0, x1, x2)
   zip3#1(::(x0, x1), x2, x3)
   zip3#1(nil, x0, x1)
   zip3#2(::(x0, x1), x2, x3, x4)
   zip3#2(nil, x0, x1, x2)
   zip3#3(::(x0, x1), x2, x3, x4, x5)
   zip3#3(nil, x0, x1, x2, x3)


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

(1) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:zip3#2_4 > nil > group3#2_2 > zip3#1_3 > group3_1 > ::_2 > zip3#3_5 > zip3_3 > tuple#3_3 > group3#3_3 > group3#1_1

and weight map:

   nil=1
   group3_1=2
   group3#1_1=1
   ::_2=2
   group3#2_2=1
   group3#3_3=3
   tuple#3_3=0
   zip3_3=1
   zip3#1_3=0
   zip3#2_4=1
   zip3#3_5=2

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

   group3(@l) -> group3#1(@l)
   group3#1(::(@x, @xs)) -> group3#2(@xs, @x)
   group3#1(nil) -> nil
   group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y)
   group3#2(nil, @x) -> nil
   group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs))
   group3#3(nil, @x, @y) -> nil
   zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3)
   zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs)
   zip3#1(nil, @l2, @l3) -> nil
   zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys)
   zip3#2(nil, @l3, @x, @xs) -> nil
   zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs))
   zip3#3(nil, @x, @xs, @y, @ys) -> nil




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

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

   group3(x0)
   group3#1(::(x0, x1))
   group3#1(nil)
   group3#2(::(x0, x1), x2)
   group3#2(nil, x0)
   group3#3(::(x0, x1), x2, x3)
   group3#3(nil, x0, x1)
   zip3(x0, x1, x2)
   zip3#1(::(x0, x1), x2, x3)
   zip3#1(nil, x0, x1)
   zip3#2(::(x0, x1), x2, x3, x4)
   zip3#2(nil, x0, x1, x2)
   zip3#3(::(x0, x1), x2, x3, x4, x5)
   zip3#3(nil, x0, x1, x2, x3)


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

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

(4)
YES