YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ) Problem 1: Innermost Equivalent Processor: -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(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: DEL(x:S,.(y:S,z:S)) -> DEL(x:S,z:S) MIN(x:S,.(y:S,z:S)) -> MIN(x:S,z:S) MIN(x:S,.(y:S,z:S)) -> MIN(y:S,z:S) MSORT(.(x:S,y:S)) -> DEL(min(x:S,y:S),.(x:S,y:S)) MSORT(.(x:S,y:S)) -> MIN(x:S,y:S) MSORT(.(x:S,y:S)) -> MSORT(del(min(x:S,y:S),.(x:S,y:S))) -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil Problem 1: SCC Processor: -> Pairs: DEL(x:S,.(y:S,z:S)) -> DEL(x:S,z:S) MIN(x:S,.(y:S,z:S)) -> MIN(x:S,z:S) MIN(x:S,.(y:S,z:S)) -> MIN(y:S,z:S) MSORT(.(x:S,y:S)) -> DEL(min(x:S,y:S),.(x:S,y:S)) MSORT(.(x:S,y:S)) -> MIN(x:S,y:S) MSORT(.(x:S,y:S)) -> MSORT(del(min(x:S,y:S),.(x:S,y:S))) -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: MIN(x:S,.(y:S,z:S)) -> MIN(x:S,z:S) MIN(x:S,.(y:S,z:S)) -> MIN(y:S,z:S) ->->-> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->->Cycle: ->->-> Pairs: DEL(x:S,.(y:S,z:S)) -> DEL(x:S,z:S) ->->-> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->->Cycle: ->->-> Pairs: MSORT(.(x:S,y:S)) -> MSORT(del(min(x:S,y:S),.(x:S,y:S))) ->->-> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: MIN(x:S,.(y:S,z:S)) -> MIN(x:S,z:S) MIN(x:S,.(y:S,z:S)) -> MIN(y:S,z:S) -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->Projection: pi(MIN) = 2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: DEL(x:S,.(y:S,z:S)) -> DEL(x:S,z:S) -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->Projection: pi(DEL) = 2 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pairs Processor: -> Pairs: MSORT(.(x:S,y:S)) -> MSORT(del(min(x:S,y:S),.(x:S,y:S))) -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil -> Usable rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [del](X1,X2) = 1 [min](X1,X2) = 2.X1 [msort](X) = 0 [.](X1,X2) = 2.X2 + 2 [<=](X1,X2) = X1 + 2 [=](X1,X2) = X1 + 2 [fSNonEmpty] = 0 [if](X1,X2,X3) = 0 [nil] = 1 [DEL](X1,X2) = 0 [MIN](X1,X2) = 0 [MSORT](X) = X Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: del(x:S,.(y:S,z:S)) -> if(=(x:S,y:S),z:S,.(y:S,del(x:S,z:S))) del(x:S,nil) -> nil min(x:S,.(y:S,z:S)) -> if(<=(x:S,y:S),min(x:S,z:S),min(y:S,z:S)) min(x:S,nil) -> x:S msort(.(x:S,y:S)) -> .(min(x:S,y:S),msort(del(min(x:S,y:S),.(x:S,y:S)))) msort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite.