YES Problem 1: (VAR v_NonEmpty:S v:S w:S x:S y:S z:S) (RULES choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ) Problem 1: Innermost Equivalent Processor: -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) 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:S,cons(v:S,w:S),0,s(z:S)) -> INSERT(x:S,w:S) CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) INSERT(x:S,cons(v:S,w:S)) -> CHOOSE(x:S,cons(v:S,w:S),x:S,v:S) SORT(cons(x:S,y:S)) -> INSERT(x:S,sort(y:S)) SORT(cons(x:S,y:S)) -> SORT(y:S) -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil Problem 1: SCC Processor: -> Pairs: CHOOSE(x:S,cons(v:S,w:S),0,s(z:S)) -> INSERT(x:S,w:S) CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) INSERT(x:S,cons(v:S,w:S)) -> CHOOSE(x:S,cons(v:S,w:S),x:S,v:S) SORT(cons(x:S,y:S)) -> INSERT(x:S,sort(y:S)) SORT(cons(x:S,y:S)) -> SORT(y:S) -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CHOOSE(x:S,cons(v:S,w:S),0,s(z:S)) -> INSERT(x:S,w:S) CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) INSERT(x:S,cons(v:S,w:S)) -> CHOOSE(x:S,cons(v:S,w:S),x:S,v:S) ->->-> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->->Cycle: ->->-> Pairs: SORT(cons(x:S,y:S)) -> SORT(y:S) ->->-> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: CHOOSE(x:S,cons(v:S,w:S),0,s(z:S)) -> INSERT(x:S,w:S) CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) INSERT(x:S,cons(v:S,w:S)) -> CHOOSE(x:S,cons(v:S,w:S),x:S,v:S) -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->Projection: pi(CHOOSE) = 2 pi(INSERT) = 2 Problem 1.1: SCC Processor: -> Pairs: CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) INSERT(x:S,cons(v:S,w:S)) -> CHOOSE(x:S,cons(v:S,w:S),x:S,v:S) -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) ->->-> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil Problem 1.1: Subterm Processor: -> Pairs: CHOOSE(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> CHOOSE(x:S,cons(v:S,w:S),y:S,z:S) -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->Projection: pi(CHOOSE) = 3 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) 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:S,y:S)) -> SORT(y:S) -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->Projection: pi(SORT) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: choose(x:S,cons(v:S,w:S),0,s(z:S)) -> cons(v:S,insert(x:S,w:S)) choose(x:S,cons(v:S,w:S),s(y:S),s(z:S)) -> choose(x:S,cons(v:S,w:S),y:S,z:S) choose(x:S,cons(v:S,w:S),y:S,0) -> cons(x:S,cons(v:S,w:S)) insert(x:S,cons(v:S,w:S)) -> choose(x:S,cons(v:S,w:S),x:S,v:S) insert(x:S,nil) -> cons(x:S,nil) sort(cons(x:S,y:S)) -> insert(x:S,sort(y:S)) sort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite.