YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ) Problem 1: Dependency Pairs Processor: -> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(div(x:S,y:S),z:S) -> TIMES(zero(y:S),z:S) DIV(div(x:S,y:S),z:S) -> ZERO(y:S) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) DIVIDES(y:S,x:S) -> DIV(x:S,y:S) DIVIDES(y:S,x:S) -> EQ(x:S,times(div(x:S,y:S),y:S)) DIVIDES(y:S,x:S) -> TIMES(div(x:S,y:S),y:S) EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PLUS(s(x:S),y:S) -> P(s(x:S)) PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) PLUS(x:S,s(y:S)) -> P(s(y:S)) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) PR(x:S,s(s(y:S))) -> DIVIDES(s(s(y:S)),x:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) PRIME(s(s(x:S))) -> PR(s(s(x:S)),s(x:S)) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) TIMES(s(x:S),y:S) -> PLUS(y:S,times(x:S,y:S)) TIMES(s(x:S),y:S) -> TIMES(x:S,y:S) ZERO(s(x:S)) -> EQ(x:S,s(0)) ZERO(s(x:S)) -> IF(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ZERO(s(x:S)) -> PLUS(zero(0),0) ZERO(s(x:S)) -> PLUS(0,zero(0)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) Problem 1: SCC Processor: -> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(div(x:S,y:S),z:S) -> TIMES(zero(y:S),z:S) DIV(div(x:S,y:S),z:S) -> ZERO(y:S) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) DIVIDES(y:S,x:S) -> DIV(x:S,y:S) DIVIDES(y:S,x:S) -> EQ(x:S,times(div(x:S,y:S),y:S)) DIVIDES(y:S,x:S) -> TIMES(div(x:S,y:S),y:S) EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PLUS(s(x:S),y:S) -> P(s(x:S)) PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) PLUS(x:S,s(y:S)) -> P(s(y:S)) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) PR(x:S,s(s(y:S))) -> DIVIDES(s(s(y:S)),x:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) PRIME(s(s(x:S))) -> PR(s(s(x:S)),s(x:S)) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) TIMES(s(x:S),y:S) -> PLUS(y:S,times(x:S,y:S)) TIMES(s(x:S),y:S) -> TIMES(x:S,y:S) ZERO(s(x:S)) -> EQ(x:S,s(0)) ZERO(s(x:S)) -> IF(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ZERO(s(x:S)) -> PLUS(zero(0),0) ZERO(s(x:S)) -> PLUS(0,zero(0)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->->Cycle: ->->-> Pairs: TIMES(s(x:S),y:S) -> TIMES(x:S,y:S) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->->Cycle: ->->-> Pairs: EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->->Cycle: ->->-> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(div(x:S,y:S),z:S) -> ZERO(y:S) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) DIVIDES(y:S,x:S) -> DIV(x:S,y:S) IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PR(x:S,s(s(y:S))) -> DIVIDES(s(s(y:S)),x:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) ZERO(s(x:S)) -> IF(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) The problem is decomposed in 4 subproblems. Problem 1.1: Reduction Pair Processor: -> Pairs: PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(s(x:S),y:S) -> PLUS(x:S,y:S) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Usable rules: p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [p](X) = X [0] = 1 [s](X) = 2.X + 2 [PLUS](X1,X2) = 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) Problem 1.1: Reduction Pair Processor: -> Pairs: PLUS(s(x:S),y:S) -> PLUS(p(s(x:S)),y:S) PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Usable rules: p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [p](X) = 1/2.X [0] = 0 [s](X) = 2.X + 1/2 [PLUS](X1,X2) = 2.X1 Problem 1.1: SCC Processor: -> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) Problem 1.1: Reduction Pair Processor: -> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,p(s(y:S))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Usable rules: p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [p](X) = 1/2.X + 1/2 [0] = 1/2 [s](X) = 2.X + 2 [PLUS](X1,X2) = 2.X2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: TIMES(s(x:S),y:S) -> TIMES(x:S,y:S) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Projection: pi(TIMES) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Projection: pi(EQ) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Reduction Pair Processor: -> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(div(x:S,y:S),z:S) -> ZERO(y:S) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) DIVIDES(y:S,x:S) -> DIV(x:S,y:S) IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PR(x:S,s(s(y:S))) -> DIVIDES(s(s(y:S)),x:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) ZERO(s(x:S)) -> IF(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Usable rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Mace4 Output: ============================== Mace4 ================================= Mace4 (64) version 2009-11A, November 2009. Process 11952 was started by sandbox2 on n190.star.cs.uiowa.edu, Mon Jun 22 09:19:26 2020 The command was "./mace4 -c -f /tmp/mace41431419379620145550.in". ============================== end of head =========================== ============================== INPUT ================================= % Reading from file /tmp/mace41431419379620145550.in assign(max_seconds,20). formulas(assumptions). gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility). arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f4(x1,x2),f4(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f4(x1,x2),f4(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f5(x1,x2,x3),f5(y,x2,x3)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f5(x1,x2,x3),f5(x1,y,x3)) # label(congruence). arrow_s0(x3,y) -> arrow_s0(f5(x1,x2,x3),f5(x1,x2,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f6(x1),f6(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f7(x1,x2),f7(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f7(x1,x2),f7(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f8(x1,x2),f8(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f8(x1,x2),f8(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f9(x1),f9(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f10(x1,x2,x3),f10(y,x2,x3)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f10(x1,x2,x3),f10(x1,y,x3)) # label(congruence). arrow_s0(x3,y) -> arrow_s0(f10(x1,x2,x3),f10(x1,x2,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f12(x1),f12(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f16(x1),f16(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f19(x1,x2),f19(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f19(x1,x2),f19(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f20(x1,x2),f20(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f20(x1,x2),f20(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f21(x1,x2),f21(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f21(x1,x2),f21(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f22(x1,x2,x3),f22(y,x2,x3)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f22(x1,x2,x3),f22(x1,y,x3)) # label(congruence). arrow_s0(x3,y) -> arrow_s0(f22(x1,x2,x3),f22(x1,x2,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f23(x1),f23(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f24(x1,x2),f24(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f24(x1,x2),f24(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f25(x1,x2),f25(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f25(x1,x2),f25(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f26(x1),f26(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f27(x1,x2,x3),f27(y,x2,x3)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f27(x1,x2,x3),f27(x1,y,x3)) # label(congruence). arrow_s0(x3,y) -> arrow_s0(f27(x1,x2,x3),f27(x1,x2,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f28(x1,x2),f28(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f28(x1,x2),f28(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f29(x1),f29(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f30(x1,x2),f30(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f30(x1,x2),f30(x1,y)) # label(congruence). arrow_s0(f2(f2(x1,x2),x3),f2(x1,f11(f12(x2),x3))) # label(replacement). arrow_s0(f2(f13,x2),f13) # label(replacement). arrow_s0(f2(x1,x2),f10(x1,x2,x2)) # label(replacement). arrow_s0(f3(x2,x1),f4(x1,f11(f2(x1,x2),x2))) # label(replacement). arrow_s0(f4(f13,f13),f17) # label(replacement). arrow_s0(f4(f13,f16(x2)),f15) # label(replacement). arrow_s0(f4(f16(x1),f13),f15) # label(replacement). arrow_s0(f4(f16(x1),f16(x2)),f4(x1,x2)) # label(replacement). arrow_s0(f5(f15,x1,x2),f8(x1,x2)) # label(replacement). arrow_s0(f5(f17,x1,x2),f15) # label(replacement). arrow_s0(f6(f13),f13) # label(replacement). arrow_s0(f6(f16(x1)),x1) # label(replacement). arrow_s0(f7(f13,x2),x2) # label(replacement). arrow_s0(f7(f16(x1),x2),f16(f7(f6(f16(x1)),x2))) # label(replacement). arrow_s0(f7(f16(x1),x2),f16(f7(x1,x2))) # label(replacement). arrow_s0(f7(x1,f13),x1) # label(replacement). arrow_s0(f7(x1,f16(x2)),f16(f7(x1,f6(f16(x2))))) # label(replacement). arrow_s0(f8(x1,f16(f13)),f17) # label(replacement). arrow_s0(f8(x1,f16(f16(x2))),f5(f3(f16(f16(x2)),x1),x1,f16(x2))) # label(replacement). arrow_s0(f10(f12(x2),f16(x2),x3),f13) # label(replacement). arrow_s0(f10(f16(x1),f16(x2),x3),f10(x1,x2,x3)) # label(replacement). arrow_s0(f10(x1,f13,f16(x3)),f16(f2(x1,f16(x3)))) # label(replacement). arrow_s0(f11(f13,x2),f13) # label(replacement). arrow_s0(f11(f16(f13),x2),x2) # label(replacement). arrow_s0(f11(f16(x1),x2),f7(x2,f11(x1,x2))) # label(replacement). arrow_s0(f12(f2(x1,x1)),x1) # label(replacement). arrow_s0(f12(f3(x1,x1)),x1) # label(replacement). arrow_s0(f12(f10(x1,x1,x1)),x1) # label(replacement). arrow_s0(f12(f11(x1,x1)),x1) # label(replacement). arrow_s0(f12(f16(x1)),f5(f4(x1,f16(f13)),f7(f12(f13),f13),f16(f7(f13,f12(f13))))) # label(replacement). arrow_s0(f30(x4,x5),x4) # label(replacement). arrow_s0(f30(x4,x5),x5) # label(replacement). arrow_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion). sqsupset_s0(f19(f2(x1,x2),x3),f29(x2)) # label(replacement). succeq_s0(f19(f2(x1,x2),x3),f19(x1,f11(f12(x2),x3))) # label(replacement). succeq_s0(f19(x1,x2),f27(x1,x2,x2)) # label(replacement). succeq_s0(f20(x2,x1),f19(x1,x2)) # label(replacement). succeq_s0(f22(f15,x1,x2),f25(x1,x2)) # label(replacement). succeq_s0(f25(x1,f16(f16(x2))),f20(f16(f16(x2)),x1)) # label(replacement). succeq_s0(f25(x1,f16(f16(x2))),f22(f3(f16(f16(x2)),x1),x1,f16(x2))) # label(replacement). succeq_s0(f27(f16(x1),f16(x2),x3),f27(x1,x2,x3)) # label(replacement). succeq_s0(f27(x1,f13,f16(x3)),f19(x1,f16(x3))) # label(replacement). succeq_s0(f29(f16(x1)),f22(f4(x1,f16(f13)),f7(f12(f13),f13),f16(f7(f13,f12(f13))))) # label(replacement). sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion). sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility). end_of_list. formulas(goals). (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness). end_of_list. ============================== end of input ========================== ============================== PROCESS NON-CLAUSAL FORMULAS ========== % Formulas that are not ordinary clauses: 1 gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 2 succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 3 gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 4 arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence) # label(non_clause). [assumption]. 5 arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence) # label(non_clause). [assumption]. 6 arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence) # label(non_clause). [assumption]. 7 arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence) # label(non_clause). [assumption]. 8 arrow_s0(x1,y) -> arrow_s0(f4(x1,x2),f4(y,x2)) # label(congruence) # label(non_clause). [assumption]. 9 arrow_s0(x2,y) -> arrow_s0(f4(x1,x2),f4(x1,y)) # label(congruence) # label(non_clause). [assumption]. 10 arrow_s0(x1,y) -> arrow_s0(f5(x1,x2,x3),f5(y,x2,x3)) # label(congruence) # label(non_clause). [assumption]. 11 arrow_s0(x2,y) -> arrow_s0(f5(x1,x2,x3),f5(x1,y,x3)) # label(congruence) # label(non_clause). [assumption]. 12 arrow_s0(x3,y) -> arrow_s0(f5(x1,x2,x3),f5(x1,x2,y)) # label(congruence) # label(non_clause). [assumption]. 13 arrow_s0(x1,y) -> arrow_s0(f6(x1),f6(y)) # label(congruence) # label(non_clause). [assumption]. 14 arrow_s0(x1,y) -> arrow_s0(f7(x1,x2),f7(y,x2)) # label(congruence) # label(non_clause). [assumption]. 15 arrow_s0(x2,y) -> arrow_s0(f7(x1,x2),f7(x1,y)) # label(congruence) # label(non_clause). [assumption]. 16 arrow_s0(x1,y) -> arrow_s0(f8(x1,x2),f8(y,x2)) # label(congruence) # label(non_clause). [assumption]. 17 arrow_s0(x2,y) -> arrow_s0(f8(x1,x2),f8(x1,y)) # label(congruence) # label(non_clause). [assumption]. 18 arrow_s0(x1,y) -> arrow_s0(f9(x1),f9(y)) # label(congruence) # label(non_clause). [assumption]. 19 arrow_s0(x1,y) -> arrow_s0(f10(x1,x2,x3),f10(y,x2,x3)) # label(congruence) # label(non_clause). [assumption]. 20 arrow_s0(x2,y) -> arrow_s0(f10(x1,x2,x3),f10(x1,y,x3)) # label(congruence) # label(non_clause). [assumption]. 21 arrow_s0(x3,y) -> arrow_s0(f10(x1,x2,x3),f10(x1,x2,y)) # label(congruence) # label(non_clause). [assumption]. 22 arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence) # label(non_clause). [assumption]. 23 arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence) # label(non_clause). [assumption]. 24 arrow_s0(x1,y) -> arrow_s0(f12(x1),f12(y)) # label(congruence) # label(non_clause). [assumption]. 25 arrow_s0(x1,y) -> arrow_s0(f16(x1),f16(y)) # label(congruence) # label(non_clause). [assumption]. 26 arrow_s0(x1,y) -> arrow_s0(f19(x1,x2),f19(y,x2)) # label(congruence) # label(non_clause). [assumption]. 27 arrow_s0(x2,y) -> arrow_s0(f19(x1,x2),f19(x1,y)) # label(congruence) # label(non_clause). [assumption]. 28 arrow_s0(x1,y) -> arrow_s0(f20(x1,x2),f20(y,x2)) # label(congruence) # label(non_clause). [assumption]. 29 arrow_s0(x2,y) -> arrow_s0(f20(x1,x2),f20(x1,y)) # label(congruence) # label(non_clause). [assumption]. 30 arrow_s0(x1,y) -> arrow_s0(f21(x1,x2),f21(y,x2)) # label(congruence) # label(non_clause). [assumption]. 31 arrow_s0(x2,y) -> arrow_s0(f21(x1,x2),f21(x1,y)) # label(congruence) # label(non_clause). [assumption]. 32 arrow_s0(x1,y) -> arrow_s0(f22(x1,x2,x3),f22(y,x2,x3)) # label(congruence) # label(non_clause). [assumption]. 33 arrow_s0(x2,y) -> arrow_s0(f22(x1,x2,x3),f22(x1,y,x3)) # label(congruence) # label(non_clause). [assumption]. 34 arrow_s0(x3,y) -> arrow_s0(f22(x1,x2,x3),f22(x1,x2,y)) # label(congruence) # label(non_clause). [assumption]. 35 arrow_s0(x1,y) -> arrow_s0(f23(x1),f23(y)) # label(congruence) # label(non_clause). [assumption]. 36 arrow_s0(x1,y) -> arrow_s0(f24(x1,x2),f24(y,x2)) # label(congruence) # label(non_clause). [assumption]. 37 arrow_s0(x2,y) -> arrow_s0(f24(x1,x2),f24(x1,y)) # label(congruence) # label(non_clause). [assumption]. 38 arrow_s0(x1,y) -> arrow_s0(f25(x1,x2),f25(y,x2)) # label(congruence) # label(non_clause). [assumption]. 39 arrow_s0(x2,y) -> arrow_s0(f25(x1,x2),f25(x1,y)) # label(congruence) # label(non_clause). [assumption]. 40 arrow_s0(x1,y) -> arrow_s0(f26(x1),f26(y)) # label(congruence) # label(non_clause). [assumption]. 41 arrow_s0(x1,y) -> arrow_s0(f27(x1,x2,x3),f27(y,x2,x3)) # label(congruence) # label(non_clause). [assumption]. 42 arrow_s0(x2,y) -> arrow_s0(f27(x1,x2,x3),f27(x1,y,x3)) # label(congruence) # label(non_clause). [assumption]. 43 arrow_s0(x3,y) -> arrow_s0(f27(x1,x2,x3),f27(x1,x2,y)) # label(congruence) # label(non_clause). [assumption]. 44 arrow_s0(x1,y) -> arrow_s0(f28(x1,x2),f28(y,x2)) # label(congruence) # label(non_clause). [assumption]. 45 arrow_s0(x2,y) -> arrow_s0(f28(x1,x2),f28(x1,y)) # label(congruence) # label(non_clause). [assumption]. 46 arrow_s0(x1,y) -> arrow_s0(f29(x1),f29(y)) # label(congruence) # label(non_clause). [assumption]. 47 arrow_s0(x1,y) -> arrow_s0(f30(x1,x2),f30(y,x2)) # label(congruence) # label(non_clause). [assumption]. 48 arrow_s0(x2,y) -> arrow_s0(f30(x1,x2),f30(x1,y)) # label(congruence) # label(non_clause). [assumption]. 49 arrow_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 50 sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 51 sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 52 (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness) # label(non_clause) # label(goal). [goal]. ============================== end of process non-clausal formulas === ============================== CLAUSES FOR SEARCH ==================== formulas(mace4_clauses). -gtrsim_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). -succeq_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). -gtrsim_s0(x,y) | -succeq_s0(y,z) | gtrsim_s0(x,z) # label(compatibility). -arrow_s0(x,y) | arrow_s0(f2(x,z),f2(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f2(z,x),f2(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f3(x,z),f3(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f3(z,x),f3(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f4(x,z),f4(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f4(z,x),f4(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(x,z,u),f5(y,z,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(z,x,u),f5(z,y,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(z,u,x),f5(z,u,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f6(x),f6(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f7(x,z),f7(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f7(z,x),f7(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f8(x,z),f8(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f8(z,x),f8(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f9(x),f9(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f10(x,z,u),f10(y,z,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f10(z,x,u),f10(z,y,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f10(z,u,x),f10(z,u,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f11(x,z),f11(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f11(z,x),f11(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f12(x),f12(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f16(x),f16(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f19(x,z),f19(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f19(z,x),f19(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f20(x,z),f20(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f20(z,x),f20(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f21(x,z),f21(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f21(z,x),f21(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f22(x,z,u),f22(y,z,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f22(z,x,u),f22(z,y,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f22(z,u,x),f22(z,u,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f23(x),f23(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f24(x,z),f24(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f24(z,x),f24(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f25(x,z),f25(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f25(z,x),f25(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f26(x),f26(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f27(x,z,u),f27(y,z,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f27(z,x,u),f27(z,y,u)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f27(z,u,x),f27(z,u,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f28(x,z),f28(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f28(z,x),f28(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f29(x),f29(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f30(x,z),f30(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f30(z,x),f30(z,y)) # label(congruence). arrow_s0(f2(f2(x,y),z),f2(x,f11(f12(y),z))) # label(replacement). arrow_s0(f2(f13,x),f13) # label(replacement). arrow_s0(f2(x,y),f10(x,y,y)) # label(replacement). arrow_s0(f3(x,y),f4(y,f11(f2(y,x),x))) # label(replacement). arrow_s0(f4(f13,f13),f17) # label(replacement). arrow_s0(f4(f13,f16(x)),f15) # label(replacement). arrow_s0(f4(f16(x),f13),f15) # label(replacement). arrow_s0(f4(f16(x),f16(y)),f4(x,y)) # label(replacement). arrow_s0(f5(f15,x,y),f8(x,y)) # label(replacement). arrow_s0(f5(f17,x,y),f15) # label(replacement). arrow_s0(f6(f13),f13) # label(replacement). arrow_s0(f6(f16(x)),x) # label(replacement). arrow_s0(f7(f13,x),x) # label(replacement). arrow_s0(f7(f16(x),y),f16(f7(f6(f16(x)),y))) # label(replacement). arrow_s0(f7(f16(x),y),f16(f7(x,y))) # label(replacement). arrow_s0(f7(x,f13),x) # label(replacement). arrow_s0(f7(x,f16(y)),f16(f7(x,f6(f16(y))))) # label(replacement). arrow_s0(f8(x,f16(f13)),f17) # label(replacement). arrow_s0(f8(x,f16(f16(y))),f5(f3(f16(f16(y)),x),x,f16(y))) # label(replacement). arrow_s0(f10(f12(x),f16(x),y),f13) # label(replacement). arrow_s0(f10(f16(x),f16(y),z),f10(x,y,z)) # label(replacement). arrow_s0(f10(x,f13,f16(y)),f16(f2(x,f16(y)))) # label(replacement). arrow_s0(f11(f13,x),f13) # label(replacement). arrow_s0(f11(f16(f13),x),x) # label(replacement). arrow_s0(f11(f16(x),y),f7(y,f11(x,y))) # label(replacement). arrow_s0(f12(f2(x,x)),x) # label(replacement). arrow_s0(f12(f3(x,x)),x) # label(replacement). arrow_s0(f12(f10(x,x,x)),x) # label(replacement). arrow_s0(f12(f11(x,x)),x) # label(replacement). arrow_s0(f12(f16(x)),f5(f4(x,f16(f13)),f7(f12(f13),f13),f16(f7(f13,f12(f13))))) # label(replacement). arrow_s0(f30(x,y),x) # label(replacement). arrow_s0(f30(x,y),y) # label(replacement). -arrow_s0(x,y) | gtrsim_s0(x,y) # label(inclusion). sqsupset_s0(f19(f2(x,y),z),f29(y)) # label(replacement). succeq_s0(f19(f2(x,y),z),f19(x,f11(f12(y),z))) # label(replacement). succeq_s0(f19(x,y),f27(x,y,y)) # label(replacement). succeq_s0(f20(x,y),f19(y,x)) # label(replacement). succeq_s0(f22(f15,x,y),f25(x,y)) # label(replacement). succeq_s0(f25(x,f16(f16(y))),f20(f16(f16(y)),x)) # label(replacement). succeq_s0(f25(x,f16(f16(y))),f22(f3(f16(f16(y)),x),x,f16(y))) # label(replacement). succeq_s0(f27(f16(x),f16(y),z),f27(x,y,z)) # label(replacement). succeq_s0(f27(x,f13,f16(y)),f19(x,f16(y))) # label(replacement). succeq_s0(f29(f16(x)),f22(f4(x,f16(f13)),f7(f12(f13),f13),f16(f7(f13,f12(f13))))) # label(replacement). -sqsupset_s0(x,y) | sqsupsetStar_s0(x,y) # label(inclusion). -sqsupset_s0(x,y) | -sqsupsetStar_s0(y,z) | sqsupsetStar_s0(x,z) # label(compatibility). -sqsupsetStar_s0(x,x) # label(wellfoundedness). end_of_list. ============================== end of clauses for search ============= % There are no natural numbers in the input. ============================== DOMAIN SIZE 2 ========================= ============================== MODEL ================================= interpretation( 2, [number=1, seconds=0], [ function(f13, [ 0 ]), function(f15, [ 0 ]), function(f17, [ 0 ]), function(f12(_), [ 0, 1 ]), function(f16(_), [ 0, 1 ]), function(f23(_), [ 0, 0 ]), function(f26(_), [ 0, 0 ]), function(f29(_), [ 0, 0 ]), function(f6(_), [ 0, 1 ]), function(f9(_), [ 0, 0 ]), function(f11(_,_), [ 0, 1, 0, 1 ]), function(f19(_,_), [ 0, 0, 1, 1 ]), function(f2(_,_), [ 1, 1, 1, 1 ]), function(f20(_,_), [ 0, 1, 0, 1 ]), function(f21(_,_), [ 0, 0, 0, 0 ]), function(f24(_,_), [ 0, 0, 0, 0 ]), function(f25(_,_), [ 0, 0, 1, 1 ]), function(f28(_,_), [ 0, 0, 0, 0 ]), function(f3(_,_), [ 0, 0, 0, 1 ]), function(f30(_,_), [ 0, 1, 1, 1 ]), function(f4(_,_), [ 0, 0, 0, 0 ]), function(f7(_,_), [ 0, 1, 1, 1 ]), function(f8(_,_), [ 0, 0, 0, 0 ]), function(f10(_,_,_), [ 1, 1, 1, 1, 1, 1, 1, 1 ]), function(f22(_,_,_), [ 0, 0, 1, 1, 0, 0, 1, 1 ]), function(f27(_,_,_), [ 0, 0, 0, 0, 1, 1, 1, 1 ]), function(f5(_,_,_), [ 0, 0, 0, 0, 0, 0, 0, 0 ]), relation(arrow_s0(_,_), [ 1, 0, 1, 1 ]), relation(gtrsim_s0(_,_), [ 1, 0, 1, 1 ]), relation(sqsupsetStar_s0(_,_), [ 0, 0, 1, 0 ]), relation(sqsupset_s0(_,_), [ 0, 0, 1, 0 ]), relation(succeq_s0(_,_), [ 1, 0, 1, 1 ]) ]). ============================== end of model ========================== ============================== STATISTICS ============================ For domain size 2. Current CPU time: 0.00 seconds (total CPU time: 0.01 seconds). Ground clauses: seen=622, kept=622. Selections=53, assignments=62, propagations=70, current_models=1. Rewrite_terms=1578, rewrite_bools=995, indexes=205. Rules_from_neg_clauses=49, cross_offs=49. ============================== end of statistics ===================== User_CPU=0.01, System_CPU=0.00, Wall_clock=0. Exiting with 1 model. Process 11952 exit (max_models) Mon Jun 22 09:19:26 2020 The process finished Mon Jun 22 09:19:26 2020 Mace4 cooked interpretation: % number = 1 % seconds = 0 % Interpretation of size 2 f13 = 0. f15 = 0. f17 = 0. f12(0) = 0. f12(1) = 1. f16(0) = 0. f16(1) = 1. f23(0) = 0. f23(1) = 0. f26(0) = 0. f26(1) = 0. f29(0) = 0. f29(1) = 0. f6(0) = 0. f6(1) = 1. f9(0) = 0. f9(1) = 0. f11(0,0) = 0. f11(0,1) = 1. f11(1,0) = 0. f11(1,1) = 1. f19(0,0) = 0. f19(0,1) = 0. f19(1,0) = 1. f19(1,1) = 1. f2(0,0) = 1. f2(0,1) = 1. f2(1,0) = 1. f2(1,1) = 1. f20(0,0) = 0. f20(0,1) = 1. f20(1,0) = 0. f20(1,1) = 1. f21(0,0) = 0. f21(0,1) = 0. f21(1,0) = 0. f21(1,1) = 0. f24(0,0) = 0. f24(0,1) = 0. f24(1,0) = 0. f24(1,1) = 0. f25(0,0) = 0. f25(0,1) = 0. f25(1,0) = 1. f25(1,1) = 1. f28(0,0) = 0. f28(0,1) = 0. f28(1,0) = 0. f28(1,1) = 0. f3(0,0) = 0. f3(0,1) = 0. f3(1,0) = 0. f3(1,1) = 1. f30(0,0) = 0. f30(0,1) = 1. f30(1,0) = 1. f30(1,1) = 1. f4(0,0) = 0. f4(0,1) = 0. f4(1,0) = 0. f4(1,1) = 0. f7(0,0) = 0. f7(0,1) = 1. f7(1,0) = 1. f7(1,1) = 1. f8(0,0) = 0. f8(0,1) = 0. f8(1,0) = 0. f8(1,1) = 0. f10(0,0,0) = 1. f10(0,0,1) = 1. f10(0,1,0) = 1. f10(0,1,1) = 1. f10(1,0,0) = 1. f10(1,0,1) = 1. f10(1,1,0) = 1. f10(1,1,1) = 1. f22(0,0,0) = 0. f22(0,0,1) = 0. f22(0,1,0) = 1. f22(0,1,1) = 1. f22(1,0,0) = 0. f22(1,0,1) = 0. f22(1,1,0) = 1. f22(1,1,1) = 1. f27(0,0,0) = 0. f27(0,0,1) = 0. f27(0,1,0) = 0. f27(0,1,1) = 0. f27(1,0,0) = 1. f27(1,0,1) = 1. f27(1,1,0) = 1. f27(1,1,1) = 1. f5(0,0,0) = 0. f5(0,0,1) = 0. f5(0,1,0) = 0. f5(0,1,1) = 0. f5(1,0,0) = 0. f5(1,0,1) = 0. f5(1,1,0) = 0. f5(1,1,1) = 0. arrow_s0(0,0). - arrow_s0(0,1). arrow_s0(1,0). arrow_s0(1,1). gtrsim_s0(0,0). - gtrsim_s0(0,1). gtrsim_s0(1,0). gtrsim_s0(1,1). - sqsupsetStar_s0(0,0). - sqsupsetStar_s0(0,1). sqsupsetStar_s0(1,0). - sqsupsetStar_s0(1,1). - sqsupset_s0(0,0). - sqsupset_s0(0,1). sqsupset_s0(1,0). - sqsupset_s0(1,1). succeq_s0(0,0). - succeq_s0(0,1). succeq_s0(1,0). succeq_s0(1,1). Problem 1.4: SCC Processor: -> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) DIVIDES(y:S,x:S) -> DIV(x:S,y:S) IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PR(x:S,s(s(y:S))) -> DIVIDES(s(s(y:S)),x:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) ZERO(s(x:S)) -> IF(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->->Cycle: ->->-> Pairs: IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) The problem is decomposed in 2 subproblems. Problem 1.4.1: Subterm Processor: -> Pairs: DIV(div(x:S,y:S),z:S) -> DIV(x:S,times(zero(y:S),z:S)) DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Projection: pi(DIV) = 1 pi(QUOT) = 1 Problem 1.4.1: SCC Processor: -> Pairs: DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) ->->-> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) Problem 1.4.1: Reduction Pair Processor: -> Pairs: DIV(x:S,y:S) -> QUOT(x:S,y:S,y:S) QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) -> Usable rules: Empty ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [0] = 2 [s](X) = 0 [DIV](X1,X2) = 2.X1 + 2.X2 + 2 [QUOT](X1,X2,X3) = 2.X1 + X2 + X3 Problem 1.4.1: SCC Processor: -> Pairs: QUOT(x:S,0,s(z:S)) -> DIV(x:S,s(z:S)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4.2: Subterm Processor: -> Pairs: IF(ffalse,x:S,y:S) -> PR(x:S,y:S) PR(x:S,s(s(y:S))) -> IF(divides(s(s(y:S)),x:S),x:S,s(y:S)) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Projection: pi(IF) = 3 pi(PR) = 2 Problem 1.4.2: SCC Processor: -> Pairs: IF(ffalse,x:S,y:S) -> PR(x:S,y:S) -> Rules: div(div(x:S,y:S),z:S) -> div(x:S,times(zero(y:S),z:S)) div(0,y:S) -> 0 div(x:S,y:S) -> quot(x:S,y:S,y:S) divides(y:S,x:S) -> eq(x:S,times(div(x:S,y:S),y:S)) eq(0,0) -> ttrue eq(0,s(y:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if(ffalse,x:S,y:S) -> pr(x:S,y:S) if(ttrue,x:S,y:S) -> ffalse p(0) -> 0 p(s(x:S)) -> x:S plus(0,y:S) -> y:S plus(s(x:S),y:S) -> s(plus(p(s(x:S)),y:S)) plus(s(x:S),y:S) -> s(plus(x:S,y:S)) plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,p(s(y:S)))) pr(x:S,s(0)) -> ttrue pr(x:S,s(s(y:S))) -> if(divides(s(s(y:S)),x:S),x:S,s(y:S)) prime(s(s(x:S))) -> pr(s(s(x:S)),s(x:S)) quot(zero(y:S),s(y:S),z:S) -> 0 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) quot(x:S,0,s(z:S)) -> s(div(x:S,s(z:S))) times(0,y:S) -> 0 times(s(0),y:S) -> y:S times(s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) zero(div(x:S,x:S)) -> x:S zero(divides(x:S,x:S)) -> x:S zero(quot(x:S,x:S,x:S)) -> x:S zero(times(x:S,x:S)) -> x:S zero(s(x:S)) -> if(eq(x:S,s(0)),plus(zero(0),0),s(plus(0,zero(0)))) ->Strongly Connected Components: There is no strongly connected component The problem is finite.