/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR v w x y z) (RULES choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ) Problem 1: Innermost Equivalent Processor: -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil -> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination. Problem 1: Dependency Pairs Processor: -> Pairs: CHOOSE(x,cons(v,w),0,s(z)) -> INSERT(x,w) CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) INSERT(x,cons(v,w)) -> CHOOSE(x,cons(v,w),x,v) SORT(cons(x,y)) -> INSERT(x,sort(y)) SORT(cons(x,y)) -> SORT(y) -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil Problem 1: SCC Processor: -> Pairs: CHOOSE(x,cons(v,w),0,s(z)) -> INSERT(x,w) CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) INSERT(x,cons(v,w)) -> CHOOSE(x,cons(v,w),x,v) SORT(cons(x,y)) -> INSERT(x,sort(y)) SORT(cons(x,y)) -> SORT(y) -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CHOOSE(x,cons(v,w),0,s(z)) -> INSERT(x,w) CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) INSERT(x,cons(v,w)) -> CHOOSE(x,cons(v,w),x,v) ->->-> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->->Cycle: ->->-> Pairs: SORT(cons(x,y)) -> SORT(y) ->->-> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: CHOOSE(x,cons(v,w),0,s(z)) -> INSERT(x,w) CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) INSERT(x,cons(v,w)) -> CHOOSE(x,cons(v,w),x,v) -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Projection: pi(CHOOSE) = 2 pi(INSERT) = 2 Problem 1.1: SCC Processor: -> Pairs: CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) INSERT(x,cons(v,w)) -> CHOOSE(x,cons(v,w),x,v) -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) ->->-> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil Problem 1.1: Subterm Processor: -> Pairs: CHOOSE(x,cons(v,w),s(y),s(z)) -> CHOOSE(x,cons(v,w),y,z) -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Projection: pi(CHOOSE) = 3 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: SORT(cons(x,y)) -> SORT(y) -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Projection: pi(SORT) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: choose(x,cons(v,w),0,s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) choose(x,cons(v,w),y,0) -> cons(x,cons(v,w)) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil) -> cons(x,nil) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite.