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


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


NO
We consider the system theBenchmark.

  Alphabet:

    0 : [] --> b 
    cons : [b * c] --> c 
    eq : [b * b] --> a 
    false : [] --> a 
    hamming : [] --> c 
    if : [a * c * c] --> c 
    list1 : [] --> c 
    list2 : [] --> c 
    list3 : [] --> c 
    lt : [b * b] --> a 
    map : [b -> b * c] --> c 
    merge : [c * c] --> c 
    mult : [b] --> b -> b 
    nil : [] --> c 
    plus : [b * b] --> b 
    s : [b] --> b 
    true : [] --> a 

  Rules:

    if(true, x, y) => x 
    if(false, x, y) => y 
    lt(s(x), s(y)) => lt(x, y) 
    lt(0, s(x)) => true 
    lt(x, 0) => false 
    eq(x, x) => true 
    eq(s(x), 0) => false 
    eq(0, s(x)) => false 
    merge(x, nil) => x 
    merge(nil, x) => x 
    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)))) 
    map(f, nil) => nil 
    map(f, cons(x, y)) => cons(f x, map(f, y)) 
    mult(0) x => 0 
    mult(s(x)) y => plus(y, mult(x) y) 
    plus(0, x) => 0 
    plus(s(x), y) => s(plus(x, y)) 
    list1 => map(mult(s(s(0))), hamming) 
    list2 => map(mult(s(s(s(0)))), hamming) 
    list3 => map(mult(s(s(s(s(s(0)))))), hamming) 
    hamming => cons(s(0), merge(list1, merge(list2, list3))) 

This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).

It is easy to see that this system is non-terminating:

  list1 
    => map(mult(s(s(0))), hamming) 
    => map(mult(s(s(0))), cons(s(0), merge(list1, merge(list2, list3)))) 
    |> list1 

That is, a term s reduces to a term t which has a subterm that is an instance of the original term.