0.00/0.01	NO
0.00/0.01	We consider the system theBenchmark.
0.00/0.01	
0.00/0.01	  Alphabet:
0.00/0.01	
0.00/0.01	    0 : [] --> b 
0.00/0.01	    cons : [b * c] --> c 
0.00/0.01	    eq : [b * b] --> a 
0.00/0.01	    false : [] --> a 
0.00/0.01	    hamming : [] --> c 
0.00/0.01	    if : [a * c * c] --> c 
0.00/0.01	    list1 : [] --> c 
0.00/0.01	    list2 : [] --> c 
0.00/0.01	    list3 : [] --> c 
0.00/0.01	    lt : [b * b] --> a 
0.00/0.01	    map : [b -> b * c] --> c 
0.00/0.01	    merge : [c * c] --> c 
0.00/0.01	    mult : [b] --> b -> b 
0.00/0.01	    nil : [] --> c 
0.00/0.01	    plus : [b * b] --> b 
0.00/0.01	    s : [b] --> b 
0.00/0.01	    true : [] --> a 
0.00/0.01	
0.00/0.01	  Rules:
0.00/0.01	
0.00/0.01	    if(true, x, y) => x 
0.00/0.01	    if(false, x, y) => y 
0.00/0.01	    lt(s(x), s(y)) => lt(x, y) 
0.00/0.01	    lt(0, s(x)) => true 
0.00/0.01	    lt(x, 0) => false 
0.00/0.01	    eq(x, x) => true 
0.00/0.01	    eq(s(x), 0) => false 
0.00/0.01	    eq(0, s(x)) => false 
0.00/0.01	    merge(x, nil) => x 
0.00/0.01	    merge(nil, x) => x 
0.00/0.01	    merge(cons(x, y), cons(z, u)) => if(lt(x, z), cons(x, merge(y, cons(z, u))), if(eq(x, z), cons(x, merge(y, u)), cons(z, merge(cons(x, y), u)))) 
0.00/0.01	    map(f, nil) => nil 
0.00/0.01	    map(f, cons(x, y)) => cons(f x, map(f, y)) 
0.00/0.01	    mult(0) x => 0 
0.00/0.01	    mult(s(x)) y => plus(y, mult(x) y) 
0.00/0.01	    plus(0, x) => 0 
0.00/0.01	    plus(s(x), y) => s(plus(x, y)) 
0.00/0.01	    list1 => map(mult(s(s(0))), hamming) 
0.00/0.01	    list2 => map(mult(s(s(s(0)))), hamming) 
0.00/0.01	    list3 => map(mult(s(s(s(s(s(0)))))), hamming) 
0.00/0.01	    hamming => cons(s(0), merge(list1, merge(list2, list3))) 
0.00/0.01	
0.00/0.01	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
0.00/0.01	
0.00/0.01	It is easy to see that this system is non-terminating:
0.00/0.01	
0.00/0.01	  list1 
0.00/0.01	    => map(mult(s(s(0))), hamming) 
0.00/0.01	    => map(mult(s(s(0))), cons(s(0), merge(list1, merge(list2, list3)))) 
0.00/0.01	    |> list1 
0.00/0.01	
0.00/0.01	That is, a term s reduces to a term t which has a subterm that is an instance of the original term.
0.00/0.01	
0.00/0.01	EOF