/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: app(app(eq(),0()),0()) -> true() app(app(eq(),0()),app(s(),x)) -> false() app(app(eq(),app(s(),x)),0()) -> false() app(app(eq(),app(s(),x)),app(s(),y)) -> app(app(eq(),x),y) app(app(or(),true()),y) -> true() app(app(or(),false()),y) -> y app(app(union(),empty()),h) -> h app(app(union(),app(app(app(edge(),x),y),i)),h) -> app(app(app(edge(),x),y),app(app(union(),i),h)) app(app(app(app(reach(),x),y),empty()),h) -> false() app(app(app(app(reach(),x),y),app(app(app(edge(),u),v),i)),h) -> app(app(app(app(app(if_reach_1(),app(app(eq(),x),u)),x),y),app(app(app(edge(),u),v),i)),h) app(app(app(app(app(if_reach_1(),true()),x),y),app(app(app(edge(),u),v),i)),h) -> app(app(app(app(app(if_reach_2(),app(app(eq(),y),v)),x),y),app(app(app(edge(),u),v),i)),h) app(app(app(app(app(if_reach_1(),false()),x),y),app(app(app(edge(),u),v),i)),h) -> app(app(app(app(reach(),x),y),i),app(app(app(edge(),u),v),h)) app(app(app(app(app(if_reach_2(),true()),x),y),app(app(app(edge(),u),v),i)),h) -> true() app(app(app(app(app(if_reach_2(),false()),x),y),app(app(app(edge(),u),v),i)),h) -> app(app(or(),app(app(app(app(reach(),x),y),i),h)),app(app(app(app(reach(),v),y), app(app(union(),i),h)), empty())) app(app(map(),f),nil()) -> nil() app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs)) app(app(filter(),f),nil()) -> nil() app(app(filter(),f),app(app(cons(),x),xs)) -> app(app(app(app(filter2(),app(f,x)),f),x),xs) app(app(app(app(filter2(),true()),f),x),xs) -> app(app(cons(),x),app(app(filter(),f),xs)) app(app(app(app(filter2(),false()),f),x),xs) -> app(app(filter(),f),xs) Proof: Extended Uncurrying Processor: application symbol: app symbol table: filter2 ==> filter20/0 filter21/1 filter22/2 filter23/3 filter24/4 filter ==> filter0/0 filter1/1 filter2/2 cons ==> cons0/0 cons1/1 cons2/2 nil ==> nil0/0 map ==> map0/0 map1/1 map2/2 if_reach_2 ==> if_reach_20/0 if_reach_21/1 if_reach_22/2 if_reach_23/3 if_reach_24/4 if_reach_25/5 if_reach_1 ==> if_reach_10/0 if_reach_11/1 if_reach_12/2 if_reach_13/3 if_reach_14/4 if_reach_15/5 reach ==> reach0/0 reach1/1 reach2/2 reach3/3 reach4/4 edge ==> edge0/0 edge1/1 edge2/2 edge3/3 empty ==> empty0/0 union ==> union0/0 union1/1 union2/2 or ==> or0/0 or1/1 or2/2 false ==> false0/0 s ==> s0/0 s1/1 true ==> true0/0 0 ==> 00/0 eq ==> eq0/0 eq1/1 eq2/2 uncurry-rules: app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) eta-rules: problem: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) DP Processor: DPs: eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> eq{2,#}(y,v) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> union{2,#}(i,h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> or{2,#}(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) map{2,#}(f,cons2(x,xs)) -> app#(f,x) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) app#(eq1(x8),x9) -> eq{2,#}(x8,x9) app#(or1(x16),x17) -> or{2,#}(x16,x17) app#(union1(x19),x20) -> union{2,#}(x19,x20) app#(reach3(x27,x28,x29),x30) -> reach{4,#}(x27,x28,x29,x30) app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) app#(map1(x44),x45) -> map{2,#}(x44,x45) app#(filter1(x51),x52) -> filter{2,#}(x51,x52) app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) TDG Processor: DPs: eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> eq{2,#}(y,v) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> union{2,#}(i,h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> or{2,#}(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) map{2,#}(f,cons2(x,xs)) -> app#(f,x) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) app#(eq1(x8),x9) -> eq{2,#}(x8,x9) app#(or1(x16),x17) -> or{2,#}(x16,x17) app#(union1(x19),x20) -> union{2,#}(x19,x20) app#(reach3(x27,x28,x29),x30) -> reach{4,#}(x27,x28,x29,x30) app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) app#(map1(x44),x45) -> map{2,#}(x44,x45) app#(filter1(x51),x52) -> filter{2,#}(x51,x52) app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) graph: filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) -> filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) -> filter{2,#}(f,cons2(x,xs)) -> app#(f,x) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) -> filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) -> filter{2,#}(f,cons2(x,xs)) -> app#(f,x) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) -> filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) -> filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(filter1(x51),x52) -> filter{2,#}(x51,x52) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(map1(x44),x45) -> map{2,#}(x44,x45) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(reach3(x27,x28,x29),x30) -> reach{4,#}(x27,x28,x29,x30) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(union1(x19),x20) -> union{2,#}(x19,x20) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(or1(x16),x17) -> or{2,#}(x16,x17) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(eq1(x8),x9) -> eq{2,#}(x8,x9) app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) -> filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) -> filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) app#(filter1(x51),x52) -> filter{2,#}(x51,x52) -> filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) app#(filter1(x51),x52) -> filter{2,#}(x51,x52) -> filter{2,#}(f,cons2(x,xs)) -> app#(f,x) app#(map1(x44),x45) -> map{2,#}(x44,x45) -> map{2,#}(f,cons2(x,xs)) -> app#(f,x) app#(map1(x44),x45) -> map{2,#}(x44,x45) -> map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> or{2,#}(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> union{2,#}(i,h) app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) -> if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) -> if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) -> if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> eq{2,#}(y,v) app#(reach3(x27,x28,x29),x30) -> reach{4,#}(x27,x28,x29,x30) -> reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) app#(reach3(x27,x28,x29),x30) -> reach{4,#}(x27,x28,x29,x30) -> reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) app#(union1(x19),x20) -> union{2,#}(x19,x20) -> union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) app#(eq1(x8),x9) -> eq{2,#}(x8,x9) -> eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(filter1(x51),x52) -> filter{2,#}(x51,x52) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(map1(x44),x45) -> map{2,#}(x44,x45) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_2{5,#}(x38,x39,x40,x41,x42) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_1{5,#}(x32,x33,x34,x35,x36) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(reach3(x27,x28,x29),x30) -> reach{4,#}(x27,x28,x29,x30) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(union1(x19),x20) -> union{2,#}(x19,x20) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(or1(x16),x17) -> or{2,#}(x16,x17) map{2,#}(f,cons2(x,xs)) -> app#(f,x) -> app#(eq1(x8),x9) -> eq{2,#}(x8,x9) map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) -> map{2,#}(f,cons2(x,xs)) -> app#(f,x) map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) -> map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) -> reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) -> reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) -> reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) -> reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> union{2,#}(i,h) -> union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) -> reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) -> reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> or{2,#}(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> union{2,#}(i,h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> eq{2,#}(y,v) -> eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> eq{2,#}(y,v) reach{4,#}(x,y,edge3(u,v,i),h) -> eq{2,#}(x,u) -> eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) -> union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) -> eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) SCC Processor: #sccs: 4 #rules: 16 #arcs: 61/676 DPs: filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) app#(map1(x44),x45) -> map{2,#}(x44,x45) map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) map{2,#}(f,cons2(x,xs)) -> app#(f,x) app#(filter1(x51),x52) -> filter{2,#}(x51,x52) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) app#(filter23(x54,x55,x56),x57) -> filter2{4,#}(x54,x55,x56,x57) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Subterm Criterion Processor: simple projection: pi(map{2,#}) = 0 pi(app#) = 0 pi(filter{2,#}) = 0 pi(filter2{4,#}) = 1 problem: DPs: filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) filter{2,#}(f,cons2(x,xs)) -> app#(f,x) map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) map{2,#}(f,cons2(x,xs)) -> app#(f,x) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) SCC Processor: #sccs: 2 #rules: 4 #arcs: 20/36 DPs: map{2,#}(f,cons2(x,xs)) -> map{2,#}(f,xs) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Subterm Criterion Processor: simple projection: pi(map{2,#}) = 1 problem: DPs: TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Qed DPs: filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) filter{2,#}(f,cons2(x,xs)) -> filter2{4,#}(app(f,x),f,x,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Subterm Criterion Processor: simple projection: pi(filter{2,#}) = 1 pi(filter2{4,#}) = 3 problem: DPs: filter2{4,#}(false0(),f,x,xs) -> filter{2,#}(f,xs) filter2{4,#}(true0(),f,x,xs) -> filter{2,#}(f,xs) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) SCC Processor: #sccs: 0 #rules: 0 #arcs: 4/4 DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Usable Rule Processor: DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) Matrix Interpretation Processor: dim=3 usable rules: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) interpretation: [if_reach_2{5,#}](x0, x1, x2, x3, x4) = [0 0 1]x0 + [1 0 0]x2 + [0 0 1]x3 + [1 0 0]x4, [if_reach_1{5,#}](x0, x1, x2, x3, x4) = [1 0 0]x2 + [1 0 0]x3 + [1 0 0]x4, [reach{4,#}](x0, x1, x2, x3) = [1 0 0]x1 + [1 0 0]x2 + [1 0 0]x3, [0 0 1] [0 1 1] [1 0 0] [edge3](x0, x1, x2) = [0 0 0]x0 + [0 0 0]x1 + [0 0 0]x2 [0 0 0] [0 1 0] [1 0 0] , [1] [empty0] = [0] [0], [1 0 0] [1 0 0] [union2](x0, x1) = [0 0 0]x0 + [1 1 0]x1 [1 0 0] [1 0 1] , [0] [false0] = [0] [1], [1] [s1](x0) = x0 + [0] [1], [0] [true0] = [0] [0], [0] [00] = [1] [1], [0 1 0] [0 0 0] [eq2](x0, x1) = [0 0 0]x0 + [1 1 0]x1 [0 0 0] [0 0 1] orientation: reach{4,#}(x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 0 1]u + [0 1 1]v + [1 0 0]y >= [1 0 0]h + [1 0 0]i + [0 0 1]u + [0 1 1]v + [1 0 0]y = if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 0 1]u + [0 1 1]v + [1 0 0]y >= [1 0 0]h + [1 0 0]i + [0 1 1]v + [1 0 0]y = if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 1 0]v + [1 0 0]y + [1] >= [1 0 0]h + [1 0 0]i + [1 0 0]y + [1] = reach{4,#}(v,y,union2(i,h),empty0()) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 1 0]v + [1 0 0]y + [1] >= [1 0 0]h + [1 0 0]i + [1 0 0]y = reach{4,#}(x,y,i,h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 0 1]u + [0 1 1]v + [1 0 0]y >= [1 0 0]h + [1 0 0]i + [0 0 1]u + [0 1 1]v + [1 0 0]y = reach{4,#}(x,y,i,edge3(u,v,h)) [1] [0] eq2(00(),00()) = [1] >= [0] = true0() [1] [0] [0 0 0] [1] [0] eq2(00(),s1(x)) = [1 1 0]x + [1] >= [0] = false0() [0 0 1] [1] [1] [0 1 0] [0] [0] eq2(s1(x),00()) = [0 0 0]x + [1] >= [0] = false0() [0 0 0] [1] [1] [0 1 0] [0 0 0] [0] [0 1 0] [0 0 0] eq2(s1(x),s1(y)) = [0 0 0]x + [1 1 0]y + [1] >= [0 0 0]x + [1 1 0]y = eq2(x,y) [0 0 0] [0 0 1] [1] [0 0 0] [0 0 1] [1 0 0] [1] union2(empty0(),h) = [1 1 0]h + [0] >= h = h [1 0 1] [1] [1 0 0] [1 0 0] [0 0 1] [0 1 1] [1 0 0] [1 0 0] [0 0 1] [0 1 1] union2(edge3(x,y,i),h) = [1 1 0]h + [0 0 0]i + [0 0 0]x + [0 0 0]y >= [0 0 0]h + [0 0 0]i + [0 0 0]x + [0 0 0]y = edge3(x,y,union2(i,h)) [1 0 1] [1 0 0] [0 0 1] [0 1 1] [1 0 0] [1 0 0] [0 0 0] [0 1 0] problem: DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) Restore Modifier: DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Usable Rule Processor: DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) -> if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) Matrix Interpretation Processor: dim=3 usable rules: union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) interpretation: [if_reach_2{5,#}](x0, x1, x2, x3, x4) = [0 1 0]x2 + [0 0 1]x3 + [1 0 0]x4, [if_reach_1{5,#}](x0, x1, x2, x3, x4) = [0 1 0]x2 + [1 0 0]x3 + [1 0 0]x4, [reach{4,#}](x0, x1, x2, x3) = [0 1 0]x1 + [1 0 0]x2 + [1 0 0]x3, [1 0 0] [1] [edge3](x0, x1, x2) = [0 0 0]x2 + [0] [1 0 0] [0], [0] [empty0] = [0] [1], [1 0 0] [1 0 0] [0] [union2](x0, x1) = [0 0 0]x0 + [1 1 1]x1 + [0] [0 0 1] [1 1 1] [1], [0] [false0] = [0] [0], [0] [s1](x0) = [0] [0], [0] [true0] = [0] [0], [0] [00] = [0] [0], [0] [eq2](x0, x1) = [0] [0] orientation: reach{4,#}(x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 1 0]y + [1] >= [1 0 0]h + [1 0 0]i + [0 1 0]y + [1] = if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(true0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 1 0]y + [1] >= [1 0 0]h + [1 0 0]i + [0 1 0]y = if_reach_2{5,#}(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 1 0]y >= [1 0 0]h + [1 0 0]i + [0 1 0]y = reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) = [1 0 0]h + [1 0 0]i + [0 1 0]y + [1] >= [1 0 0]h + [1 0 0]i + [0 1 0]y + [1] = reach{4,#}(x,y,i,edge3(u,v,h)) [0] [0] eq2(00(),00()) = [0] >= [0] = true0() [0] [0] [0] [0] eq2(00(),s1(x)) = [0] >= [0] = false0() [0] [0] [0] [0] eq2(s1(x),00()) = [0] >= [0] = false0() [0] [0] [0] [0] eq2(s1(x),s1(y)) = [0] >= [0] = eq2(x,y) [0] [0] [1 0 0] [0] union2(empty0(),h) = [1 1 1]h + [0] >= h = h [1 1 1] [2] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1] union2(edge3(x,y,i),h) = [1 1 1]h + [0 0 0]i + [0] >= [0 0 0]h + [0 0 0]i + [0] = edge3(x,y,union2(i,h)) [1 1 1] [1 0 0] [1] [1 0 0] [1 0 0] [0] problem: DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) Restore Modifier: DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_2{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(v,y,union2(i,h),empty0()) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) SCC Processor: #sccs: 1 #rules: 2 #arcs: 7/9 DPs: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Size-Change Termination Processor: DPs: TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) The DP: reach{4,#}(x,y,edge3(u,v,i),h) -> if_reach_1{5,#}(eq2(x,u),x,y,edge3(u,v,i),h) has the edges: 0 >= 1 1 >= 2 2 >= 3 3 >= 4 The DP: if_reach_1{5,#}(false0(),x,y,edge3(u,v,i),h) -> reach{4,#}(x,y,i,edge3(u,v,h)) has the edges: 1 >= 0 2 >= 1 3 > 2 Qed DPs: union{2,#}(edge3(x,y,i),h) -> union{2,#}(i,h) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Subterm Criterion Processor: simple projection: pi(union{2,#}) = 0 problem: DPs: TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Qed DPs: eq{2,#}(s1(x),s1(y)) -> eq{2,#}(x,y) TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Subterm Criterion Processor: simple projection: pi(eq{2,#}) = 0 problem: DPs: TRS: eq2(00(),00()) -> true0() eq2(00(),s1(x)) -> false0() eq2(s1(x),00()) -> false0() eq2(s1(x),s1(y)) -> eq2(x,y) or2(true0(),y) -> true0() or2(false0(),y) -> y union2(empty0(),h) -> h union2(edge3(x,y,i),h) -> edge3(x,y,union2(i,h)) reach4(x,y,empty0(),h) -> false0() reach4(x,y,edge3(u,v,i),h) -> if_reach_15(eq2(x,u),x,y,edge3(u,v,i),h) if_reach_15(true0(),x,y,edge3(u,v,i),h) -> if_reach_25(eq2(y,v),x,y,edge3(u,v,i),h) if_reach_15(false0(),x,y,edge3(u,v,i),h) -> reach4(x,y,i,edge3(u,v,h)) if_reach_25(true0(),x,y,edge3(u,v,i),h) -> true0() if_reach_25(false0(),x,y,edge3(u,v,i),h) -> or2(reach4(x,y,i,h),reach4(v,y,union2(i,h),empty0())) map2(f,nil0()) -> nil0() map2(f,cons2(x,xs)) -> cons2(app(f,x),map2(f,xs)) filter2(f,nil0()) -> nil0() filter2(f,cons2(x,xs)) -> filter24(app(f,x),f,x,xs) filter24(true0(),f,x,xs) -> cons2(x,filter2(f,xs)) filter24(false0(),f,x,xs) -> filter2(f,xs) app(eq1(x8),x9) -> eq2(x8,x9) app(eq0(),x8) -> eq1(x8) app(s0(),x13) -> s1(x13) app(or1(x16),x17) -> or2(x16,x17) app(or0(),x16) -> or1(x16) app(union1(x19),x20) -> union2(x19,x20) app(union0(),x19) -> union1(x19) app(edge2(x23,x24),x25) -> edge3(x23,x24,x25) app(edge1(x23),x24) -> edge2(x23,x24) app(edge0(),x23) -> edge1(x23) app(reach3(x27,x28,x29),x30) -> reach4(x27,x28,x29,x30) app(reach2(x27,x28),x29) -> reach3(x27,x28,x29) app(reach1(x27),x28) -> reach2(x27,x28) app(reach0(),x27) -> reach1(x27) app(if_reach_14(x32,x33,x34,x35),x36) -> if_reach_15(x32,x33,x34,x35,x36) app(if_reach_13(x32,x33,x34),x35) -> if_reach_14(x32,x33,x34,x35) app(if_reach_12(x32,x33),x34) -> if_reach_13(x32,x33,x34) app(if_reach_11(x32),x33) -> if_reach_12(x32,x33) app(if_reach_10(),x32) -> if_reach_11(x32) app(if_reach_24(x38,x39,x40,x41),x42) -> if_reach_25(x38,x39,x40,x41,x42) app(if_reach_23(x38,x39,x40),x41) -> if_reach_24(x38,x39,x40,x41) app(if_reach_22(x38,x39),x40) -> if_reach_23(x38,x39,x40) app(if_reach_21(x38),x39) -> if_reach_22(x38,x39) app(if_reach_20(),x38) -> if_reach_21(x38) app(map1(x44),x45) -> map2(x44,x45) app(map0(),x44) -> map1(x44) app(cons1(x48),x49) -> cons2(x48,x49) app(cons0(),x48) -> cons1(x48) app(filter1(x51),x52) -> filter2(x51,x52) app(filter0(),x51) -> filter1(x51) app(filter23(x54,x55,x56),x57) -> filter24(x54,x55,x56,x57) app(filter22(x54,x55),x56) -> filter23(x54,x55,x56) app(filter21(x54),x55) -> filter22(x54,x55) app(filter20(),x54) -> filter21(x54) Qed