YES Problem 1: (VAR v_NonEmpty:S k:S l:S x:S y:S z:S) (RULES app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ) Problem 1: Dependency Pairs Processor: -> Pairs: APP(cons(x:S,l:S),k:S) -> APP(l:S,k:S) MINUS(minus(x:S,y:S),z:S) -> MINUS(x:S,plus(y:S,z:S)) MINUS(minus(x:S,y:S),z:S) -> PLUS(y:S,z:S) MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 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)) SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> APP(l:S,sum(cons(x:S,cons(y:S,k:S)))) SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> SUM(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> SUM(cons(x:S,cons(y:S,k:S))) SUM(cons(x:S,cons(y:S,l:S))) -> PLUS(x:S,y:S) SUM(cons(x:S,cons(y:S,l:S))) -> SUM(cons(plus(x:S,y:S),l:S)) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) Problem 1: SCC Processor: -> Pairs: APP(cons(x:S,l:S),k:S) -> APP(l:S,k:S) MINUS(minus(x:S,y:S),z:S) -> MINUS(x:S,plus(y:S,z:S)) MINUS(minus(x:S,y:S),z:S) -> PLUS(y:S,z:S) MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 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)) SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> APP(l:S,sum(cons(x:S,cons(y:S,k:S)))) SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> SUM(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> SUM(cons(x:S,cons(y:S,k:S))) SUM(cons(x:S,cons(y:S,l:S))) -> PLUS(x:S,y:S) SUM(cons(x:S,cons(y:S,l:S))) -> SUM(cons(plus(x:S,y:S),l:S)) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) ->->-> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->->Cycle: ->->-> Pairs: SUM(cons(x:S,cons(y:S,l:S))) -> SUM(cons(plus(x:S,y:S),l:S)) ->->-> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->->Cycle: ->->-> Pairs: MINUS(minus(x:S,y:S),z:S) -> MINUS(x:S,plus(y:S,z:S)) MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) ->->-> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->->Cycle: ->->-> Pairs: QUOT(s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) ->->-> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->->Cycle: ->->-> Pairs: APP(cons(x:S,l:S),k:S) -> APP(l:S,k:S) ->->-> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->->Cycle: ->->-> Pairs: SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> SUM(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) ->->-> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) The problem is decomposed in 6 subproblems. Problem 1.1: Subterm Processor: -> Pairs: PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Projection: pi(PLUS) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: SUM(cons(x:S,cons(y:S,l:S))) -> SUM(cons(plus(x:S,y:S),l:S)) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) -> Usable rules: plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [plus](X1,X2) = X2 [0] = 0 [cons](X1,X2) = 2.X1 + X2 + 2 [s](X) = X [SUM](X) = 2.X Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: MINUS(minus(x:S,y:S),z:S) -> MINUS(x:S,plus(y:S,z:S)) MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Projection: pi(MINUS) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Reduction Pair Processor: -> Pairs: QUOT(s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) -> Usable rules: minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [minus](X1,X2) = X1 [plus](X1,X2) = 2.X1 + X2 + 2 [0] = 0 [s](X) = X + 2 [QUOT](X1,X2) = 2.X1 Problem 1.4: SCC Processor: -> Pairs: Empty -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.5: Subterm Processor: -> Pairs: APP(cons(x:S,l:S),k:S) -> APP(l:S,k:S) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Projection: pi(APP) = 1 Problem 1.5: SCC Processor: -> Pairs: Empty -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.6: Reduction Pair Processor: -> Pairs: SUM(app(l:S,cons(x:S,cons(y:S,k:S)))) -> SUM(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) -> Usable rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(x:S,y:S)) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [app](X1,X2) = 2.X1 + 2.X2 + 2 [plus](X1,X2) = 2.X1 + X2 + 2 [sum](X) = 2 [0] = 0 [cons](X1,X2) = X2 + 2 [nil] = 0 [s](X) = X + 1 [SUM](X) = 2.X Problem 1.6: SCC Processor: -> Pairs: Empty -> Rules: app(cons(x:S,l:S),k:S) -> cons(x:S,app(l:S,k:S)) app(nil,k:S) -> k:S app(l:S,nil) -> l:S minus(minus(x:S,y:S),z:S) -> minus(x:S,plus(y:S,z:S)) minus(s(x:S),s(y:S)) -> minus(x:S,y:S) minus(x:S,0) -> x:S 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))) sum(app(l:S,cons(x:S,cons(y:S,k:S)))) -> sum(app(l:S,sum(cons(x:S,cons(y:S,k:S))))) sum(cons(x:S,cons(y:S,l:S))) -> sum(cons(plus(x:S,y:S),l:S)) sum(cons(x:S,nil)) -> cons(x:S,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite.