YES Problem 1: (VAR x y z) (THEORY (AC inter union) (C eq)) (RULES eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x ) Problem 1: Dependency Pairs Processor: -> FAxioms: EQ(x3,x4) = EQ(x4,x3) INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) UNION(union(x3,x4),x5) = UNION(x3,union(x4,x5)) UNION(x3,x4) = UNION(x4,x3) -> Pairs: EQ(s(x),s(y)) -> EQ(x,y) INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,y) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(union(y,z),x),x3) -> UNION(inter(x,y),inter(x,z)) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> EQ(x,y) INTER(inter(singl(x),singl(y)),x3) -> IF(eq(x,y),singl(x),empty) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) INTER(union(y,z),x) -> UNION(inter(x,y),inter(x,z)) INTER(singl(x),singl(y)) -> EQ(x,y) INTER(singl(x),singl(y)) -> IF(eq(x,y),singl(x),empty) UNION(union(empty,x),x3) -> UNION(x,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) UNION(union(x3,x4),x5) -> UNION(x3,x4) UNION(x3,union(x4,x5)) -> UNION(x4,x5) Problem 1: SCC Processor: -> FAxioms: EQ(x3,x4) = EQ(x4,x3) INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) UNION(union(x3,x4),x5) = UNION(x3,union(x4,x5)) UNION(x3,x4) = UNION(x4,x3) -> Pairs: EQ(s(x),s(y)) -> EQ(x,y) INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,y) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(union(y,z),x),x3) -> UNION(inter(x,y),inter(x,z)) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> EQ(x,y) INTER(inter(singl(x),singl(y)),x3) -> IF(eq(x,y),singl(x),empty) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) INTER(union(y,z),x) -> UNION(inter(x,y),inter(x,z)) INTER(singl(x),singl(y)) -> EQ(x,y) INTER(singl(x),singl(y)) -> IF(eq(x,y),singl(x),empty) UNION(union(empty,x),x3) -> UNION(x,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) UNION(union(x3,x4),x5) -> UNION(x3,x4) UNION(x3,union(x4,x5)) -> UNION(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: UNION(union(empty,x),x3) -> UNION(x,x3) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) UNION(union(x3,x4),x5) -> UNION(x3,union(x4,x5)) UNION(x3,x4) -> UNION(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: UNION(union(x3,x4),x5) -> UNION(x3,x4) UNION(x3,union(x4,x5)) -> UNION(x4,x5) ->->Cycle: ->->-> Pairs: EQ(s(x),s(y)) -> EQ(x,y) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) EQ(x3,x4) -> EQ(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: Empty ->->Cycle: ->->-> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,y) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) The problem is decomposed in 3 subproblems. Problem 1.1: Reduction Pairs Processor: -> FAxioms: UNION(union(x3,x4),x5) = UNION(x3,union(x4,x5)) UNION(x3,x4) = UNION(x4,x3) -> Pairs: UNION(union(empty,x),x3) -> UNION(x,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: union(empty,x) -> x -> SRules: UNION(union(x3,x4),x5) -> UNION(x3,x4) UNION(x3,union(x4,x5)) -> UNION(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [eq](X1,X2) = 0 [if](X1,X2,X3) = 0 [inter](X1,X2) = 0 [union](X1,X2) = X1 + X2 [0] = 0 [empty] = 2 [false] = 0 [s](X) = 0 [singl](X) = 0 [true] = 0 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = 0 [UNION](X1,X2) = 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> FAxioms: UNION(union(x3,x4),x5) = UNION(x3,union(x4,x5)) UNION(x3,x4) = UNION(x4,x3) -> Pairs: Empty -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: UNION(union(x3,x4),x5) -> UNION(x3,x4) UNION(x3,union(x4,x5)) -> UNION(x4,x5) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> FAxioms: EQ(x3,x4) = EQ(x4,x3) -> Pairs: EQ(s(x),s(y)) -> EQ(x,y) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: Empty ->Projection: pi(EQ) = [1,2] Problem 1.2: SCC Processor: -> FAxioms: EQ(x3,x4) = EQ(x4,x3) -> Pairs: Empty -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,y) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [eq](X1,X2) = 1 [if](X1,X2,X3) = X1 + X2 + X3 + 1 [inter](X1,X2) = X1.X2 + X1 + X2 [union](X1,X2) = X1 + X2 + 1 [0] = 1 [empty] = 0 [false] = 1 [s](X) = X + 1 [singl](X) = X.X + X + 1 [true] = 1 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = X1.X2 + X1 + X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(union(y,z),x),x3) -> INTER(x,z) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [eq](X1,X2) = 1 [if](X1,X2,X3) = X1.X2 + X1.X3 [inter](X1,X2) = X1.X2 + X1 + X2 [union](X1,X2) = X1 + X2 + 1 [0] = 0 [empty] = 0 [false] = 1 [s](X) = X + 1 [singl](X) = X.X + X [true] = 1 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = X1.X2 + X1 + X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(inter(singl(x),singl(y)),x3) -> INTER(if(eq(x,y),singl(x),empty),x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [eq](X1,X2) = 1 [if](X1,X2,X3) = X1.X2.X3 + X1.X3 + X2.X3 + X1 + X2 + X3 [inter](X1,X2) = X1.X2 + X1 + X2 [union](X1,X2) = X1 + X2 + 1 [0] = 0 [empty] = 0 [false] = 0 [s](X) = X [singl](X) = 1 [true] = 1 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = X1.X2 + X1 + X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(union(y,z),x) -> INTER(x,y) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [eq](X1,X2) = X1.X2 + X1 + X2 + 1 [if](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + X3 + 1 [inter](X1,X2) = X1.X2 + X1 + X2 [union](X1,X2) = X1 + X2 + 1 [0] = 1 [empty] = 0 [false] = 1 [s](X) = X + 1 [singl](X) = X.X + X + 1 [true] = 1 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = X1.X2 + X1 + X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(union(y,z),x) -> INTER(x,z) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) INTER(union(y,z),x) -> INTER(x,z) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [eq](X1,X2) = X1.X2 + X1 + X2 + 1 [if](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + X3 [inter](X1,X2) = X1.X2 + X1 + X2 [union](X1,X2) = X1 + X2 + 1 [0] = 1 [empty] = 0 [false] = 1 [s](X) = X + 1 [singl](X) = X.X + X + 1 [true] = 1 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = X1.X2 + X1 + X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(union(y,z),x),x3) -> INTER(union(inter(x,y),inter(x,z)),x3) INTER(inter(empty,x),x3) -> INTER(empty,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 3 ->Interpretation: [eq](X1,X2) = 2 [if](X1,X2,X3) = 2.X1.X2 + 1/2.X1 + 2/3.X2 + 2.X3 [inter](X1,X2) = 3.X1.X2 + 3.X1 + 3.X2 + 2 [union](X1,X2) = X1 + X2 + 3/2 [0] = 1 [empty] = 0 [false] = 2/3 [s](X) = 1/3.X + 1/3 [singl](X) = 1 [true] = 2 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = 1/3.X1.X2 + 1/3.X1 + 1/3.X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(empty,x),x3) -> INTER(empty,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: INTER(inter(empty,x),x3) -> INTER(empty,x3) -> FAxioms: eq(x3,x4) -> eq(x4,x3) inter(inter(x3,x4),x5) -> inter(x3,inter(x4,x5)) inter(x3,x4) -> inter(x4,x3) union(union(x3,x4),x5) -> union(x3,union(x4,x5)) union(x3,x4) -> union(x4,x3) INTER(inter(x3,x4),x5) -> INTER(x3,inter(x4,x5)) INTER(x3,x4) -> INTER(x4,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) ->->-> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) Problem 1.3: Reduction Pairs Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: INTER(inter(empty,x),x3) -> INTER(empty,x3) -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Usable Equations: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> Usable Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 3 ->Interpretation: [eq](X1,X2) = 1 [if](X1,X2,X3) = 3.X1.X2 + 2.X1.X3 + 3.X2.X3 + 3/2.X3 [inter](X1,X2) = 2.X1.X2 + 3.X1 + 3.X2 + 3 [union](X1,X2) = X1 + X2 + 3 [0] = 2/3 [empty] = 0 [false] = 2/3 [s](X) = 3 [singl](X) = 3 [true] = 1/3 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [INTER](X1,X2) = 1/3.X1.X2 + 1/2.X1 + 1/2.X2 [UNION](X1,X2) = 0 Problem 1.3: SCC Processor: -> FAxioms: INTER(inter(x3,x4),x5) = INTER(x3,inter(x4,x5)) INTER(x3,x4) = INTER(x4,x3) -> Pairs: Empty -> EAxioms: eq(x3,x4) = eq(x4,x3) inter(inter(x3,x4),x5) = inter(x3,inter(x4,x5)) inter(x3,x4) = inter(x4,x3) union(union(x3,x4),x5) = union(x3,union(x4,x5)) union(x3,x4) = union(x4,x3) -> Rules: eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),s(y)) -> eq(x,y) if(false,x,y) -> y if(true,x,y) -> x inter(union(y,z),x) -> union(inter(x,y),inter(x,z)) inter(empty,x) -> empty inter(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) union(empty,x) -> x -> SRules: INTER(inter(x3,x4),x5) -> INTER(x3,x4) INTER(x3,inter(x4,x5)) -> INTER(x4,x5) ->Strongly Connected Components: There is no strongly connected component The problem is finite.