/export/starexec/sandbox/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Proof: DP Processor: DPs: eq#(s(x),s(y)) -> eq#(x,y) union#(edge(x,y,i),h) -> union#(i,h) reach#(x,y,edge(u,v,i),h) -> eq#(x,u) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> eq#(y,v) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> union#(i,h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> or#(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) TDG Processor: DPs: eq#(s(x),s(y)) -> eq#(x,y) union#(edge(x,y,i),h) -> union#(i,h) reach#(x,y,edge(u,v,i),h) -> eq#(x,u) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> eq#(y,v) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> union#(i,h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> or#(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) graph: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) -> reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) -> reach#(x,y,edge(u,v,i),h) -> eq#(x,u) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) -> reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) -> reach#(x,y,edge(u,v,i),h) -> eq#(x,u) if_reach_2#(false(),x,y,edge(u,v,i),h) -> union#(i,h) -> union#(edge(x,y,i),h) -> union#(i,h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) -> reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) -> reach#(x,y,edge(u,v,i),h) -> eq#(x,u) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) -> if_reach_2#(false(),x,y,edge(u,v,i),h) -> or#(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) -> if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) -> if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) -> if_reach_2#(false(),x,y,edge(u,v,i),h) -> union#(i,h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> eq#(y,v) -> eq#(s(x),s(y)) -> eq#(x,y) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) -> if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) -> if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) -> if_reach_1#(true(),x,y,edge(u,v,i),h) -> eq#(y,v) reach#(x,y,edge(u,v,i),h) -> eq#(x,u) -> eq#(s(x),s(y)) -> eq#(x,y) union#(edge(x,y,i),h) -> union#(i,h) -> union#(edge(x,y,i),h) -> union#(i,h) eq#(s(x),s(y)) -> eq#(x,y) -> eq#(s(x),s(y)) -> eq#(x,y) SCC Processor: #sccs: 3 #rules: 7 #arcs: 18/121 DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Usable Rule Processor: DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) Matrix Interpretation Processor: dim=3 usable rules: union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) interpretation: [if_reach_2#](x0, x1, x2, x3, x4) = [0 1 0]x2 + [0 1 0]x3 + [0 1 0]x4, [if_reach_1#](x0, x1, x2, x3, x4) = [0 1 0]x2 + [0 0 1]x3 + [0 1 0]x4 + [1], [reach#](x0, x1, x2, x3) = [0 1 0]x1 + [0 1 0]x2 + [0 1 0]x3, [0 0 0] [0 0 0] [0] [edge](x0, x1, x2) = [0 1 0]x0 + [0 1 0]x2 + [1] [0 1 0] [0 1 0] [0], [0 1 0] [1 0 0] [0] [union](x0, x1) = [0 1 0]x0 + [0 1 0]x1 + [1] [0 0 1] [0 1 1] [1], [0] [empty] = [0] [0], [0] [false] = [0] [0], [0 0 0] [s](x0) = [0 0 1]x0 [0 0 0] , [0] [true] = [0] [0], [0 0 0] [eq](x0, x1) = [0 1 0]x1 [0 0 0] , [0] [0] = [1] [0] orientation: if_reach_2#(false(),x,y,edge(u,v,i),h) = [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] >= [0 1 0]h + [0 1 0]i + [0 1 0]y + [1] = reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) = [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] >= [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] = if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) = [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] >= [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] = if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_2#(false(),x,y,edge(u,v,i),h) = [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] >= [0 1 0]h + [0 1 0]i + [0 1 0]y = reach#(x,y,i,h) if_reach_1#(false(),x,y,edge(u,v,i),h) = [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] >= [0 1 0]h + [0 1 0]i + [0 1 0]u + [0 1 0]y + [1] = reach#(x,y,i,edge(u,v,h)) [1 0 0] [0] union(empty(),h) = [0 1 0]h + [1] >= h = h [0 1 1] [1] [1 0 0] [0 1 0] [0 1 0] [1] [0 0 0] [0 0 0] [0 0 0] [0] union(edge(x,y,i),h) = [0 1 0]h + [0 1 0]i + [0 1 0]x + [2] >= [0 1 0]h + [0 1 0]i + [0 1 0]x + [2] = edge(x,y,union(i,h)) [0 1 1] [0 1 0] [0 1 0] [1] [0 1 0] [0 1 0] [0 1 0] [1] [0] [0] eq(0(),0()) = [1] >= [0] = true() [0] [0] [0 0 0] [0] eq(0(),s(x)) = [0 0 1]x >= [0] = false() [0 0 0] [0] [0] [0] eq(s(x),0()) = [1] >= [0] = false() [0] [0] [0 0 0] [0 0 0] eq(s(x),s(y)) = [0 0 1]y >= [0 1 0]y = eq(x,y) [0 0 0] [0 0 0] problem: DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) Restore Modifier: DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Usable Rule Processor: DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) -> if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) Matrix Interpretation Processor: dim=3 usable rules: union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) interpretation: [if_reach_2#](x0, x1, x2, x3, x4) = [0 1 0]x0 + [1 0 0]x3 + [0 0 1]x4, [if_reach_1#](x0, x1, x2, x3, x4) = [0 1 0]x3 + [0 0 1]x4 + [1], [reach#](x0, x1, x2, x3) = [0 0 1]x2 + [0 0 1]x3, [1 0 0] [0 0 1] [0] [edge](x0, x1, x2) = [1 0 1]x1 + [0 0 1]x2 + [0] [1 0 1] [0 0 1] [1], [0 1 1] [1 1 1] [0] [union](x0, x1) = [0 1 0]x0 + [0 1 1]x1 + [1] [0 0 1] [0 0 1] [0], [0] [empty] = [0] [0], [0] [false] = [0] [0], [0 0 0] [0] [s](x0) = [0 1 0]x0 + [1] [0 1 1] [0], [0] [true] = [0] [0], [0 0 0] [0 0 0] [eq](x0, x1) = [0 0 0]x0 + [0 0 1]x1 [0 1 0] [0 0 0] , [0] [0] = [1] [0] orientation: if_reach_2#(false(),x,y,edge(u,v,i),h) = [0 0 1]h + [0 0 1]i + [1 0 0]v >= [0 0 1]h + [0 0 1]i = reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) = [0 0 1]h + [0 0 1]i + [1 0 1]v + [1] >= [0 0 1]h + [0 0 1]i + [1 0 1]v + [1] = if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(true(),x,y,edge(u,v,i),h) = [0 0 1]h + [0 0 1]i + [1 0 1]v + [1] >= [0 0 1]h + [0 0 1]i + [1 0 1]v = if_reach_2#(eq(y,v),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) = [0 0 1]h + [0 0 1]i + [1 0 1]v + [1] >= [0 0 1]h + [0 0 1]i + [1 0 1]v + [1] = reach#(x,y,i,edge(u,v,h)) [1 1 1] [0] union(empty(),h) = [0 1 1]h + [1] >= h = h [0 0 1] [0] [1 1 1] [0 0 2] [2 0 2] [1] [0 0 1] [0 0 1] [1 0 0] [0] union(edge(x,y,i),h) = [0 1 1]h + [0 0 1]i + [1 0 1]y + [1] >= [0 0 1]h + [0 0 1]i + [1 0 1]y + [0] = edge(x,y,union(i,h)) [0 0 1] [0 0 1] [1 0 1] [1] [0 0 1] [0 0 1] [1 0 1] [1] [0] [0] eq(0(),0()) = [0] >= [0] = true() [1] [0] [0 0 0] [0] [0] eq(0(),s(x)) = [0 1 1]x + [0] >= [0] = false() [0 0 0] [1] [0] [0 0 0] [0] [0] eq(s(x),0()) = [0 0 0]x + [0] >= [0] = false() [0 1 0] [1] [0] [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] eq(s(x),s(y)) = [0 0 0]x + [0 1 1]y + [0] >= [0 0 0]x + [0 0 1]y = eq(x,y) [0 1 0] [0 0 0] [1] [0 1 0] [0 0 0] problem: DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) Restore Modifier: DPs: if_reach_2#(false(),x,y,edge(u,v,i),h) -> reach#(v,y,union(i,h),empty()) reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) SCC Processor: #sccs: 1 #rules: 2 #arcs: 7/9 DPs: reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Size-Change Termination Processor: DPs: TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) The DP: reach#(x,y,edge(u,v,i),h) -> if_reach_1#(eq(x,u),x,y,edge(u,v,i),h) has the edges: 0 >= 1 1 >= 2 2 >= 3 3 >= 4 The DP: if_reach_1#(false(),x,y,edge(u,v,i),h) -> reach#(x,y,i,edge(u,v,h)) has the edges: 1 >= 0 2 >= 1 3 > 2 Qed DPs: union#(edge(x,y,i),h) -> union#(i,h) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Subterm Criterion Processor: simple projection: pi(union#) = 0 problem: DPs: TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Qed DPs: eq#(s(x),s(y)) -> eq#(x,y) TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Subterm Criterion Processor: simple projection: pi(eq#) = 0 problem: DPs: TRS: eq(0(),0()) -> true() eq(0(),s(x)) -> false() eq(s(x),0()) -> false() eq(s(x),s(y)) -> eq(x,y) or(true(),y) -> true() or(false(),y) -> y union(empty(),h) -> h union(edge(x,y,i),h) -> edge(x,y,union(i,h)) reach(x,y,empty(),h) -> false() reach(x,y,edge(u,v,i),h) -> if_reach_1(eq(x,u),x,y,edge(u,v,i),h) if_reach_1(true(),x,y,edge(u,v,i),h) -> if_reach_2(eq(y,v),x,y,edge(u,v,i),h) if_reach_2(true(),x,y,edge(u,v,i),h) -> true() if_reach_2(false(),x,y,edge(u,v,i),h) -> or(reach(x,y,i,h),reach(v,y,union(i,h),empty())) if_reach_1(false(),x,y,edge(u,v,i),h) -> reach(x,y,i,edge(u,v,h)) Qed