YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ) Problem 1: Innermost Equivalent Processor: -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 -> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination. Problem 1: Dependency Pairs Processor: -> Pairs: BSORT(.(x:S,y:S)) -> BSORT(butlast(bubble(.(x:S,y:S)))) BSORT(.(x:S,y:S)) -> BUBBLE(.(x:S,y:S)) BSORT(.(x:S,y:S)) -> BUTLAST(bubble(.(x:S,y:S))) BSORT(.(x:S,y:S)) -> LAST(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(x:S,z:S)) BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) BUTLAST(.(x:S,.(y:S,z:S))) -> BUTLAST(.(y:S,z:S)) LAST(.(x:S,.(y:S,z:S))) -> LAST(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 Problem 1: SCC Processor: -> Pairs: BSORT(.(x:S,y:S)) -> BSORT(butlast(bubble(.(x:S,y:S)))) BSORT(.(x:S,y:S)) -> BUBBLE(.(x:S,y:S)) BSORT(.(x:S,y:S)) -> BUTLAST(bubble(.(x:S,y:S))) BSORT(.(x:S,y:S)) -> LAST(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(x:S,z:S)) BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) BUTLAST(.(x:S,.(y:S,z:S))) -> BUTLAST(.(y:S,z:S)) LAST(.(x:S,.(y:S,z:S))) -> LAST(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: LAST(.(x:S,.(y:S,z:S))) -> LAST(.(y:S,z:S)) ->->-> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->->Cycle: ->->-> Pairs: BUTLAST(.(x:S,.(y:S,z:S))) -> BUTLAST(.(y:S,z:S)) ->->-> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->->Cycle: ->->-> Pairs: BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(x:S,z:S)) BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) ->->-> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->->Cycle: ->->-> Pairs: BSORT(.(x:S,y:S)) -> BSORT(butlast(bubble(.(x:S,y:S)))) ->->-> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 The problem is decomposed in 4 subproblems. Problem 1.1: Subterm Processor: -> Pairs: LAST(.(x:S,.(y:S,z:S))) -> LAST(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Projection: pi(LAST) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: BUTLAST(.(x:S,.(y:S,z:S))) -> BUTLAST(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Projection: pi(BUTLAST) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pairs Processor: -> Pairs: BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(x:S,z:S)) BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 -> Usable rules: Empty ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [bsort](X) = 0 [bubble](X) = 0 [butlast](X) = 0 [last](X) = 0 [.](X1,X2) = 2.X1 + 2.X2 + 2 [0] = 0 [<=](X1,X2) = 0 [fSNonEmpty] = 0 [if](X1,X2,X3) = 0 [nil] = 0 [BSORT](X) = 0 [BUBBLE](X) = 2.X [BUTLAST](X) = 0 [LAST](X) = 0 Problem 1.3: SCC Processor: -> Pairs: BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) ->->-> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 Problem 1.3: Subterm Processor: -> Pairs: BUBBLE(.(x:S,.(y:S,z:S))) -> BUBBLE(.(y:S,z:S)) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Projection: pi(BUBBLE) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Reduction Pairs Processor: -> Pairs: BSORT(.(x:S,y:S)) -> BSORT(butlast(bubble(.(x:S,y:S)))) -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 -> Usable rules: bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [bsort](X) = 0 [bubble](X) = 1/2 [butlast](X) = 1/2.X.X + 1/2.X [last](X) = 0 [.](X1,X2) = 1/2.X1.X2 + 2.X2 + 1/2 [0] = 0 [<=](X1,X2) = 1/2.X1.X2 + 2.X1 [fSNonEmpty] = 0 [if](X1,X2,X3) = 0 [nil] = 0 [BSORT](X) = 1/2.X [BUBBLE](X) = 0 [BUTLAST](X) = 0 [LAST](X) = 0 Problem 1.4: SCC Processor: -> Pairs: Empty -> Rules: bsort(.(x:S,y:S)) -> last(.(bubble(.(x:S,y:S)),bsort(butlast(bubble(.(x:S,y:S)))))) bsort(nil) -> nil bubble(.(x:S,.(y:S,z:S))) -> if(<=(x:S,y:S),.(y:S,bubble(.(x:S,z:S))),.(x:S,bubble(.(y:S,z:S)))) bubble(.(x:S,nil)) -> .(x:S,nil) bubble(nil) -> nil butlast(.(x:S,.(y:S,z:S))) -> .(x:S,butlast(.(y:S,z:S))) butlast(.(x:S,nil)) -> nil butlast(nil) -> nil last(.(x:S,.(y:S,z:S))) -> last(.(y:S,z:S)) last(.(x:S,nil)) -> x:S last(nil) -> 0 ->Strongly Connected Components: There is no strongly connected component The problem is finite.