YES Problem 1: (VAR v_NonEmpty:S h:S i:S u:S v:S x:S y:S) (RULES eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ) Problem 1: Innermost Equivalent Processor: -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S -> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination. Problem 1: Dependency Pairs Processor: -> Pairs: EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) IF_REACH_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> EQ(y:S,v:S) IF_REACH_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> OR(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(v:S,y:S,union(i:S,h:S),empty) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,h:S) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> UNION(i:S,h:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> EQ(x:S,u:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) UNION(edge(x:S,y:S,i:S),h:S) -> UNION(i:S,h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S Problem 1: SCC Processor: -> Pairs: EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) IF_REACH_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> EQ(y:S,v:S) IF_REACH_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> OR(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(v:S,y:S,union(i:S,h:S),empty) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,h:S) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> UNION(i:S,h:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> EQ(x:S,u:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) UNION(edge(x:S,y:S,i:S),h:S) -> UNION(i:S,h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: UNION(edge(x:S,y:S,i:S),h:S) -> UNION(i:S,h:S) ->->-> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->->Cycle: ->->-> Pairs: EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) ->->-> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->->Cycle: ->->-> Pairs: IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) IF_REACH_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(v:S,y:S,union(i:S,h:S),empty) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,h:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) ->->-> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: UNION(edge(x:S,y:S,i:S),h:S) -> UNION(i:S,h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Projection: pi(UNION) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: EQ(s(x:S),s(y:S)) -> EQ(x:S,y:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Projection: pi(EQ) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pairs Processor: -> Pairs: IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) IF_REACH_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(v:S,y:S,union(i:S,h:S),empty) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,h:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S -> Usable rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [eq](X1,X2) = 2.X1 + 2.X2 + 2 [if_reach_1](X1,X2,X3,X4,X5) = 0 [if_reach_2](X1,X2,X3,X4,X5) = 0 [or](X1,X2) = 0 [reach](X1,X2,X3,X4) = 0 [union](X1,X2) = X1 + X2 [0] = 2 [edge](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2 [empty] = 1 [fSNonEmpty] = 0 [false] = 2 [s](X) = 2.X + 2 [true] = 0 [EQ](X1,X2) = 0 [IF_REACH_1](X1,X2,X3,X4,X5) = 2.X2 + 2.X3 + 2.X4 + 2.X5 + 2 [IF_REACH_2](X1,X2,X3,X4,X5) = 2.X2 + 2.X3 + 2.X4 + 2.X5 + 1 [OR](X1,X2) = 0 [REACH](X1,X2,X3,X4) = 2.X1 + 2.X2 + 2.X3 + 2.X4 + 2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> Pairs: IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(v:S,y:S,union(i:S,h:S),empty) IF_REACH_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,h:S) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) ->->-> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S Problem 1.3: Subterm Processor: -> Pairs: IF_REACH_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> REACH(x:S,y:S,i:S,edge(u:S,v:S,h:S)) REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Projection: pi(IF_REACH_1) = 4 pi(REACH) = 3 Problem 1.3: SCC Processor: -> Pairs: REACH(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> IF_REACH_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) -> Rules: eq(0,0) -> ttrue eq(0,s(x:S)) -> ffalse eq(s(x:S),0) -> ffalse eq(s(x:S),s(y:S)) -> eq(x:S,y:S) if_reach_1(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> reach(x:S,y:S,i:S,edge(u:S,v:S,h:S)) if_reach_1(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_2(eq(y:S,v:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) if_reach_2(ffalse,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> or(reach(x:S,y:S,i:S,h:S),reach(v:S,y:S,union(i:S,h:S),empty)) if_reach_2(ttrue,x:S,y:S,edge(u:S,v:S,i:S),h:S) -> ttrue or(ffalse,y:S) -> y:S or(ttrue,y:S) -> ttrue reach(x:S,y:S,edge(u:S,v:S,i:S),h:S) -> if_reach_1(eq(x:S,u:S),x:S,y:S,edge(u:S,v:S,i:S),h:S) reach(x:S,y:S,empty,h:S) -> ffalse union(edge(x:S,y:S,i:S),h:S) -> edge(x:S,y:S,union(i:S,h:S)) union(empty,h:S) -> h:S ->Strongly Connected Components: There is no strongly connected component The problem is finite.