YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ) Problem 1: Dependency Pairs Processor: -> Pairs: F(0,s(0),s(s(z:S))) -> F(0,s(0),z:S) F(0,s(s(y:S)),s(0)) -> F(0,y:S,s(0)) F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) F(0,s(s(y:S)),s(s(z:S))) -> F(0,y:S,f(0,s(s(y:S)),s(z:S))) F(s(0),y:S,z:S) -> F(0,s(y:S),s(z:S)) F(s(x:S),0,s(z:S)) -> F(x:S,s(0),z:S) F(s(x:S),s(y:S),0) -> F(x:S,y:S,s(0)) F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) F(s(x:S),s(y:S),s(z:S)) -> F(x:S,y:S,f(s(x:S),s(y:S),z:S)) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) Problem 1: SCC Processor: -> Pairs: F(0,s(0),s(s(z:S))) -> F(0,s(0),z:S) F(0,s(s(y:S)),s(0)) -> F(0,y:S,s(0)) F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) F(0,s(s(y:S)),s(s(z:S))) -> F(0,y:S,f(0,s(s(y:S)),s(z:S))) F(s(0),y:S,z:S) -> F(0,s(y:S),s(z:S)) F(s(x:S),0,s(z:S)) -> F(x:S,s(0),z:S) F(s(x:S),s(y:S),0) -> F(x:S,y:S,s(0)) F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) F(s(x:S),s(y:S),s(z:S)) -> F(x:S,y:S,f(s(x:S),s(y:S),z:S)) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: F(0,s(s(y:S)),s(0)) -> F(0,y:S,s(0)) ->->-> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->->Cycle: ->->-> Pairs: F(0,s(0),s(s(z:S))) -> F(0,s(0),z:S) ->->-> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->->Cycle: ->->-> Pairs: F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) F(0,s(s(y:S)),s(s(z:S))) -> F(0,y:S,f(0,s(s(y:S)),s(z:S))) ->->-> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->->Cycle: ->->-> Pairs: F(s(x:S),0,s(z:S)) -> F(x:S,s(0),z:S) F(s(x:S),s(y:S),0) -> F(x:S,y:S,s(0)) F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) F(s(x:S),s(y:S),s(z:S)) -> F(x:S,y:S,f(s(x:S),s(y:S),z:S)) ->->-> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) The problem is decomposed in 4 subproblems. Problem 1.1: Subterm Processor: -> Pairs: F(0,s(s(y:S)),s(0)) -> F(0,y:S,s(0)) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Projection: pi(F) = 2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: F(0,s(0),s(s(z:S))) -> F(0,s(0),z:S) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Projection: pi(F) = 3 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) F(0,s(s(y:S)),s(s(z:S))) -> F(0,y:S,f(0,s(s(y:S)),s(z:S))) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Projection: pi(F) = 2 Problem 1.3: SCC Processor: -> Pairs: F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) ->->-> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) Problem 1.3: Subterm Processor: -> Pairs: F(0,s(s(y:S)),s(s(z:S))) -> F(0,s(s(y:S)),s(z:S)) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Projection: pi(F) = 3 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Subterm Processor: -> Pairs: F(s(x:S),0,s(z:S)) -> F(x:S,s(0),z:S) F(s(x:S),s(y:S),0) -> F(x:S,y:S,s(0)) F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) F(s(x:S),s(y:S),s(z:S)) -> F(x:S,y:S,f(s(x:S),s(y:S),z:S)) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Projection: pi(F) = 1 Problem 1.4: SCC Processor: -> Pairs: F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) ->->-> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) Problem 1.4: Subterm Processor: -> Pairs: F(s(x:S),s(y:S),s(z:S)) -> F(s(x:S),s(y:S),z:S) -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Projection: pi(F) = 3 Problem 1.4: SCC Processor: -> Pairs: Empty -> Rules: f(0,0,z:S) -> s(z:S) f(0,s(0),s(0)) -> s(s(0)) f(0,s(0),s(s(z:S))) -> f(0,s(0),z:S) f(0,s(s(y:S)),s(0)) -> f(0,y:S,s(0)) f(0,s(s(y:S)),s(s(z:S))) -> f(0,y:S,f(0,s(s(y:S)),s(z:S))) f(0,y:S,0) -> s(y:S) f(s(0),y:S,z:S) -> f(0,s(y:S),s(z:S)) f(s(x:S),0,s(z:S)) -> f(x:S,s(0),z:S) f(s(x:S),s(y:S),0) -> f(x:S,y:S,s(0)) f(s(x:S),s(y:S),s(z:S)) -> f(x:S,y:S,f(s(x:S),s(y:S),z:S)) f(x:S,0,0) -> s(x:S) ->Strongly Connected Components: There is no strongly connected component The problem is finite.