YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ) Problem 1: Dependency Pairs Processor: -> Pairs: MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) QUOT(s(x:S),s(y:S)) -> MINUS(x:S,y:S) QUOT(s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) Problem 1: SCC Processor: -> Pairs: MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) QUOT(s(x:S),s(y:S)) -> MINUS(x:S,y:S) QUOT(s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) ->->-> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->->Cycle: ->->-> Pairs: MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) ->->-> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->->Cycle: ->->-> Pairs: QUOT(s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) ->->-> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) The problem is decomposed in 3 subproblems. Problem 1.1: Reduction Pair Processor: -> Pairs: PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) -> Usable rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [minus](X1,X2) = 2.X1 + 2.X2 [0] = 0 [s](X) = 2.X + 2 [PLUS](X1,X2) = X1 + X2 Problem 1.1: SCC Processor: -> Pairs: PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) ->->-> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) Problem 1.1: Reduction Pair Processor: -> Pairs: PLUS(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> PLUS(minus(y:S,s(s(z:S))),minus(x:S,s(0))) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) -> Usable rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 2 ->Bound: 1 ->Interpretation: [minus](X1,X2) = [1 1;1 1].X1 + [1 0;1 1].X2 [0] = [1;0] [s](X) = [1 1;1 1].X + [1;1] [PLUS](X1,X2) = [1 0;1 1].X1 + [0 1;1 1].X2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->Projection: pi(MINUS) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pair Processor: -> Pairs: QUOT(s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) -> Usable rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [minus](X1,X2) = 2.X1 + 1 [0] = 0 [s](X) = 2.X + 2 [QUOT](X1,X2) = 2.X1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(minus(x:S,s(0)),minus(y:S,s(s(z:S)))) -> plus(minus(y:S,s(s(z:S))),minus(x:S,s(0))) plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) quot(0,s(y:S)) -> 0 quot(s(x:S),s(y:S)) -> s(quot(minus(x:S,y:S),s(y:S))) ->Strongly Connected Components: There is no strongly connected component The problem is finite.