/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


NO
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) QTRS
(1) Overlay + Local Confluence [EQUIVALENT, 0 ms]
(2) QTRS
(3) DependencyPairsProof [EQUIVALENT, 30 ms]
(4) QDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) QDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QReductionProof [EQUIVALENT, 0 ms]
        (11) QDP
        (12) ATransformationProof [EQUIVALENT, 0 ms]
        (13) QDP
        (14) QReductionProof [EQUIVALENT, 0 ms]
        (15) QDP
        (16) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (17) YES
    (18) QDP
        (19) UsableRulesProof [EQUIVALENT, 0 ms]
        (20) QDP
        (21) QReductionProof [EQUIVALENT, 0 ms]
        (22) QDP
        (23) ATransformationProof [EQUIVALENT, 0 ms]
        (24) QDP
        (25) QReductionProof [EQUIVALENT, 0 ms]
        (26) QDP
        (27) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (28) YES
    (29) QDP
        (30) UsableRulesProof [EQUIVALENT, 0 ms]
        (31) QDP
        (32) QReductionProof [EQUIVALENT, 0 ms]
        (33) QDP
        (34) ATransformationProof [EQUIVALENT, 0 ms]
        (35) QDP
        (36) QReductionProof [EQUIVALENT, 0 ms]
        (37) QDP
        (38) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (39) YES
    (40) QDP
        (41) UsableRulesProof [EQUIVALENT, 0 ms]
        (42) QDP
        (43) QReductionProof [EQUIVALENT, 0 ms]
        (44) QDP
        (45) ATransformationProof [EQUIVALENT, 0 ms]
        (46) QDP
        (47) QReductionProof [EQUIVALENT, 0 ms]
        (48) QDP
        (49) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (50) YES
    (51) QDP
        (52) UsableRulesProof [EQUIVALENT, 0 ms]
        (53) QDP
        (54) QReductionProof [EQUIVALENT, 0 ms]
        (55) QDP
        (56) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (57) YES
    (58) QDP
        (59) UsableRulesProof [EQUIVALENT, 0 ms]
        (60) QDP
        (61) QReductionProof [EQUIVALENT, 0 ms]
        (62) QDP
        (63) NonTerminationLoopProof [COMPLETE, 0 ms]
        (64) NO


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

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

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

Q is empty.

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

(1) Overlay + Local Confluence (EQUIVALENT)
The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
----------------------------------------

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

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming


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

(3) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(4)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(lt, app(s, x)), app(s, y)) -> APP(app(lt, x), y)
   APP(app(lt, app(s, x)), app(s, y)) -> APP(lt, x)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys))))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(if, app(app(lt, x), y))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(lt, x), y)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(lt, x)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), app(app(cons, y), ys))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(merge, xs)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys)))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys)))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(if, app(app(eq, x), y))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(eq, x), y)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(eq, x)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(cons, x), app(app(merge, xs), ys))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), ys)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, app(app(cons, x), xs)), ys)
   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(cons, app(f, x)), app(app(map, f), xs))
   APP(app(map, f), app(app(cons, x), xs)) -> APP(cons, app(f, x))
   APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)
   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
   APP(app(mult, app(s, x)), y) -> APP(app(plus, y), app(app(mult, x), y))
   APP(app(mult, app(s, x)), y) -> APP(plus, y)
   APP(app(mult, app(s, x)), y) -> APP(app(mult, x), y)
   APP(app(mult, app(s, x)), y) -> APP(mult, x)
   APP(app(plus, app(s, x)), y) -> APP(s, app(app(plus, x), y))
   APP(app(plus, app(s, x)), y) -> APP(app(plus, x), y)
   APP(app(plus, app(s, x)), y) -> APP(plus, x)
   LIST1 -> APP(app(map, app(mult, app(s, app(s, 0)))), hamming)
   LIST1 -> APP(map, app(mult, app(s, app(s, 0))))
   LIST1 -> APP(mult, app(s, app(s, 0)))
   LIST1 -> APP(s, app(s, 0))
   LIST1 -> APP(s, 0)
   LIST1 -> HAMMING
   LIST2 -> APP(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   LIST2 -> APP(map, app(mult, app(s, app(s, app(s, 0)))))
   LIST2 -> APP(mult, app(s, app(s, app(s, 0))))
   LIST2 -> APP(s, app(s, app(s, 0)))
   LIST2 -> APP(s, app(s, 0))
   LIST2 -> APP(s, 0)
   LIST2 -> HAMMING
   LIST3 -> APP(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   LIST3 -> APP(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0)))))))
   LIST3 -> APP(mult, app(s, app(s, app(s, app(s, app(s, 0))))))
   LIST3 -> APP(s, app(s, app(s, app(s, app(s, 0)))))
   LIST3 -> APP(s, app(s, app(s, app(s, 0))))
   LIST3 -> APP(s, app(s, app(s, 0)))
   LIST3 -> APP(s, app(s, 0))
   LIST3 -> APP(s, 0)
   LIST3 -> HAMMING
   HAMMING -> APP(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))
   HAMMING -> APP(cons, app(s, 0))
   HAMMING -> APP(s, 0)
   HAMMING -> APP(app(merge, list1), app(app(merge, list2), list3))
   HAMMING -> APP(merge, list1)
   HAMMING -> LIST1
   HAMMING -> APP(app(merge, list2), list3)
   HAMMING -> APP(merge, list2)
   HAMMING -> LIST2
   HAMMING -> LIST3

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 48 less nodes.
----------------------------------------

(6)
Complex Obligation (AND)

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

(7)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(plus, app(s, x)), y) -> APP(app(plus, x), y)

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(8) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(plus, app(s, x)), y) -> APP(app(plus, x), y)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(10) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   list1
   list2
   list3
   hamming


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

(11)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(plus, app(s, x)), y) -> APP(app(plus, x), y)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(12) ATransformationProof (EQUIVALENT)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 
----------------------------------------

(13)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   plus1(s(x), y) -> plus1(x, y)

R is empty.
The set Q consists of the following terms:

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(14) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)


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

(15)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   plus1(s(x), y) -> plus1(x, y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(16) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*plus1(s(x), y) -> plus1(x, y)
The graph contains the following edges 1 > 1, 2 >= 2


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

(17)
YES

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

(18)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(mult, app(s, x)), y) -> APP(app(mult, x), y)

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(19) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(20)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(mult, app(s, x)), y) -> APP(app(mult, x), y)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(21) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   list1
   list2
   list3
   hamming


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

(22)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(mult, app(s, x)), y) -> APP(app(mult, x), y)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(23) ATransformationProof (EQUIVALENT)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 
----------------------------------------

(24)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   mult1(s(x), y) -> mult1(x, y)

R is empty.
The set Q consists of the following terms:

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(25) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)


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

(26)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   mult1(s(x), y) -> mult1(x, y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(27) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*mult1(s(x), y) -> mult1(x, y)
The graph contains the following edges 1 > 1, 2 >= 2


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

(28)
YES

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

(29)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(lt, app(s, x)), app(s, y)) -> APP(app(lt, x), y)

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(30) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(31)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(lt, app(s, x)), app(s, y)) -> APP(app(lt, x), y)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(32) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   list1
   list2
   list3
   hamming


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

(33)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(lt, app(s, x)), app(s, y)) -> APP(app(lt, x), y)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(34) ATransformationProof (EQUIVALENT)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 
----------------------------------------

(35)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   lt1(s(x), s(y)) -> lt1(x, y)

R is empty.
The set Q consists of the following terms:

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(36) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)


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

(37)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   lt1(s(x), s(y)) -> lt1(x, y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(38) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*lt1(s(x), s(y)) -> lt1(x, y)
The graph contains the following edges 1 > 1, 2 > 2


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

(39)
YES

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

(40)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), ys)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), app(app(cons, y), ys))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, app(app(cons, x), xs)), ys)

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(41) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(42)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), ys)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), app(app(cons, y), ys))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, app(app(cons, x), xs)), ys)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(43) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   list1
   list2
   list3
   hamming


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

(44)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), ys)
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, xs), app(app(cons, y), ys))
   APP(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> APP(app(merge, app(app(cons, x), xs)), ys)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(45) ATransformationProof (EQUIVALENT)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 
----------------------------------------

(46)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   merge1(cons(x, xs), cons(y, ys)) -> merge1(xs, ys)
   merge1(cons(x, xs), cons(y, ys)) -> merge1(xs, cons(y, ys))
   merge1(cons(x, xs), cons(y, ys)) -> merge1(cons(x, xs), ys)

R is empty.
The set Q consists of the following terms:

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(47) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   if(true, x0, x1)
   if(false, x0, x1)
   lt(s(x0), s(x1))
   lt(0, s(x0))
   lt(x0, 0)
   eq(x0, x0)
   eq(s(x0), 0)
   eq(0, s(x0))
   merge(x0, nil)
   merge(nil, x0)
   merge(cons(x0, x1), cons(x2, x3))
   map(x0, nil)
   map(x0, cons(x1, x2))
   mult(0, x0)
   mult(s(x0), x1)
   plus(0, x0)
   plus(s(x0), x1)


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

(48)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   merge1(cons(x, xs), cons(y, ys)) -> merge1(xs, ys)
   merge1(cons(x, xs), cons(y, ys)) -> merge1(xs, cons(y, ys))
   merge1(cons(x, xs), cons(y, ys)) -> merge1(cons(x, xs), ys)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(49) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*merge1(cons(x, xs), cons(y, ys)) -> merge1(xs, ys)
The graph contains the following edges 1 > 1, 2 > 2


*merge1(cons(x, xs), cons(y, ys)) -> merge1(xs, cons(y, ys))
The graph contains the following edges 1 > 1, 2 >= 2


*merge1(cons(x, xs), cons(y, ys)) -> merge1(cons(x, xs), ys)
The graph contains the following edges 1 >= 1, 2 > 2


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

(50)
YES

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

(51)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
   APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(52) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(53)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
   APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(54) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   list1
   list2
   list3
   hamming


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

(55)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
   APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(56) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs)
The graph contains the following edges 1 >= 1, 2 > 2


*APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x)
The graph contains the following edges 1 > 1, 2 > 2


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

(57)
YES

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

(58)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   LIST1 -> HAMMING
   HAMMING -> LIST1
   HAMMING -> LIST2
   LIST2 -> HAMMING
   HAMMING -> LIST3
   LIST3 -> HAMMING

The TRS R consists of the following rules:

   app(app(app(if, true), xs), ys) -> xs
   app(app(app(if, false), xs), ys) -> ys
   app(app(lt, app(s, x)), app(s, y)) -> app(app(lt, x), y)
   app(app(lt, 0), app(s, y)) -> true
   app(app(lt, y), 0) -> false
   app(app(eq, x), x) -> true
   app(app(eq, app(s, x)), 0) -> false
   app(app(eq, 0), app(s, x)) -> false
   app(app(merge, xs), nil) -> xs
   app(app(merge, nil), ys) -> ys
   app(app(merge, app(app(cons, x), xs)), app(app(cons, y), ys)) -> app(app(app(if, app(app(lt, x), y)), app(app(cons, x), app(app(merge, xs), app(app(cons, y), ys)))), app(app(app(if, app(app(eq, x), y)), app(app(cons, x), app(app(merge, xs), ys))), app(app(cons, y), app(app(merge, app(app(cons, x), xs)), ys))))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(mult, 0), x) -> 0
   app(app(mult, app(s, x)), y) -> app(app(plus, y), app(app(mult, x), y))
   app(app(plus, 0), x) -> 0
   app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
   list1 -> app(app(map, app(mult, app(s, app(s, 0)))), hamming)
   list2 -> app(app(map, app(mult, app(s, app(s, app(s, 0))))), hamming)
   list3 -> app(app(map, app(mult, app(s, app(s, app(s, app(s, app(s, 0))))))), hamming)
   hamming -> app(app(cons, app(s, 0)), app(app(merge, list1), app(app(merge, list2), list3)))

The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(59) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(60)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   LIST1 -> HAMMING
   HAMMING -> LIST1
   HAMMING -> LIST2
   LIST2 -> HAMMING
   HAMMING -> LIST3
   LIST3 -> HAMMING

R is empty.
The set Q consists of the following terms:

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(61) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   app(app(app(if, true), x0), x1)
   app(app(app(if, false), x0), x1)
   app(app(lt, app(s, x0)), app(s, x1))
   app(app(lt, 0), app(s, x0))
   app(app(lt, x0), 0)
   app(app(eq, x0), x0)
   app(app(eq, app(s, x0)), 0)
   app(app(eq, 0), app(s, x0))
   app(app(merge, x0), nil)
   app(app(merge, nil), x0)
   app(app(merge, app(app(cons, x0), x1)), app(app(cons, x2), x3))
   app(app(map, x0), nil)
   app(app(map, x0), app(app(cons, x1), x2))
   app(app(mult, 0), x0)
   app(app(mult, app(s, x0)), x1)
   app(app(plus, 0), x0)
   app(app(plus, app(s, x0)), x1)
   list1
   list2
   list3
   hamming


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

(62)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   LIST1 -> HAMMING
   HAMMING -> LIST1
   HAMMING -> LIST2
   LIST2 -> HAMMING
   HAMMING -> LIST3
   LIST3 -> HAMMING

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(63) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

s = HAMMING evaluates to  t =HAMMING

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

HAMMING -> LIST1
with rule HAMMING -> LIST1 at position [] and matcher [ ]

LIST1 -> HAMMING
with rule LIST1 -> HAMMING

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.




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

(64)
NO