YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern reach(g,g,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) PiDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) PiDP (31) PiDPToQDPProof [SOUND, 0 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 25 ms] (34) QDP (35) DependencyGraphProof [EQUIVALENT, 0 ms] (36) TRUE ---------------------------------------- (0) Obligation: Clauses: reach(X, Y, E, L) :- member(.(X, .(Y, [])), E). reach(X, Z, E, L) :- ','(member1(.(X, .(Y, [])), E), ','(member(Y, L), ','(delete(Y, L, V1), reach(Y, Z, E, V1)))). member(H, .(H, L)). member(X, .(H, L)) :- member(X, L). member1(H, .(H, L)). member1(X, .(H, L)) :- member1(X, L). delete(X, .(X, Y), Y). delete(X, .(H, T1), .(H, T2)) :- delete(X, T1, T2). Query: reach(g,g,g,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: reach_in_4: (b,b,b,b) member_in_2: (b,b) member1_in_2: (f,b) delete_in_3: (b,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGGG(X, Y, E, L) -> U1_GGGG(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) REACH_IN_GGGG(X, Y, E, L) -> MEMBER_IN_GG(.(X, .(Y, [])), E) MEMBER_IN_GG(X, .(H, L)) -> U6_GG(X, H, L, member_in_gg(X, L)) MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) REACH_IN_GGGG(X, Z, E, L) -> U2_GGGG(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) REACH_IN_GGGG(X, Z, E, L) -> MEMBER1_IN_AG(.(X, .(Y, [])), E) MEMBER1_IN_AG(X, .(H, L)) -> U7_AG(X, H, L, member1_in_ag(X, L)) MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) U2_GGGG(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_GGGG(X, Z, E, L, Y, member_in_gg(Y, L)) U2_GGGG(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> MEMBER_IN_GG(Y, L) U3_GGGG(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_GGGG(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) U3_GGGG(X, Z, E, L, Y, member_out_gg(Y, L)) -> DELETE_IN_GGA(Y, L, V1) DELETE_IN_GGA(X, .(H, T1), .(H, T2)) -> U8_GGA(X, H, T1, T2, delete_in_gga(X, T1, T2)) DELETE_IN_GGA(X, .(H, T1), .(H, T2)) -> DELETE_IN_GGA(X, T1, T2) U4_GGGG(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_GGGG(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U4_GGGG(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> REACH_IN_GGGG(Y, Z, E, V1) The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) REACH_IN_GGGG(x1, x2, x3, x4) = REACH_IN_GGGG(x1, x2, x3, x4) U1_GGGG(x1, x2, x3, x4, x5) = U1_GGGG(x5) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) U6_GG(x1, x2, x3, x4) = U6_GG(x4) U2_GGGG(x1, x2, x3, x4, x5) = U2_GGGG(x2, x3, x4, x5) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) U7_AG(x1, x2, x3, x4) = U7_AG(x4) U3_GGGG(x1, x2, x3, x4, x5, x6) = U3_GGGG(x2, x3, x4, x5, x6) U4_GGGG(x1, x2, x3, x4, x5, x6) = U4_GGGG(x2, x3, x5, x6) DELETE_IN_GGA(x1, x2, x3) = DELETE_IN_GGA(x1, x2) U8_GGA(x1, x2, x3, x4, x5) = U8_GGA(x2, x5) U5_GGGG(x1, x2, x3, x4, x5) = U5_GGGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGGG(X, Y, E, L) -> U1_GGGG(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) REACH_IN_GGGG(X, Y, E, L) -> MEMBER_IN_GG(.(X, .(Y, [])), E) MEMBER_IN_GG(X, .(H, L)) -> U6_GG(X, H, L, member_in_gg(X, L)) MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) REACH_IN_GGGG(X, Z, E, L) -> U2_GGGG(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) REACH_IN_GGGG(X, Z, E, L) -> MEMBER1_IN_AG(.(X, .(Y, [])), E) MEMBER1_IN_AG(X, .(H, L)) -> U7_AG(X, H, L, member1_in_ag(X, L)) MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) U2_GGGG(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_GGGG(X, Z, E, L, Y, member_in_gg(Y, L)) U2_GGGG(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> MEMBER_IN_GG(Y, L) U3_GGGG(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_GGGG(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) U3_GGGG(X, Z, E, L, Y, member_out_gg(Y, L)) -> DELETE_IN_GGA(Y, L, V1) DELETE_IN_GGA(X, .(H, T1), .(H, T2)) -> U8_GGA(X, H, T1, T2, delete_in_gga(X, T1, T2)) DELETE_IN_GGA(X, .(H, T1), .(H, T2)) -> DELETE_IN_GGA(X, T1, T2) U4_GGGG(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_GGGG(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U4_GGGG(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> REACH_IN_GGGG(Y, Z, E, V1) The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) REACH_IN_GGGG(x1, x2, x3, x4) = REACH_IN_GGGG(x1, x2, x3, x4) U1_GGGG(x1, x2, x3, x4, x5) = U1_GGGG(x5) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) U6_GG(x1, x2, x3, x4) = U6_GG(x4) U2_GGGG(x1, x2, x3, x4, x5) = U2_GGGG(x2, x3, x4, x5) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) U7_AG(x1, x2, x3, x4) = U7_AG(x4) U3_GGGG(x1, x2, x3, x4, x5, x6) = U3_GGGG(x2, x3, x4, x5, x6) U4_GGGG(x1, x2, x3, x4, x5, x6) = U4_GGGG(x2, x3, x5, x6) DELETE_IN_GGA(x1, x2, x3) = DELETE_IN_GGA(x1, x2) U8_GGA(x1, x2, x3, x4, x5) = U8_GGA(x2, x5) U5_GGGG(x1, x2, x3, x4, x5) = U5_GGGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 9 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GGA(X, .(H, T1), .(H, T2)) -> DELETE_IN_GGA(X, T1, T2) The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) DELETE_IN_GGA(x1, x2, x3) = DELETE_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GGA(X, .(H, T1), .(H, T2)) -> DELETE_IN_GGA(X, T1, T2) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) DELETE_IN_GGA(x1, x2, x3) = DELETE_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: DELETE_IN_GGA(X, .(H, T1)) -> DELETE_IN_GGA(X, T1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *DELETE_IN_GGA(X, .(H, T1)) -> DELETE_IN_GGA(X, T1) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBER1_IN_AG(.(H, L)) -> MEMBER1_IN_AG(L) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MEMBER1_IN_AG(.(H, L)) -> MEMBER1_IN_AG(L) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGGG(X, Z, E, L) -> U2_GGGG(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) U2_GGGG(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_GGGG(X, Z, E, L, Y, member_in_gg(Y, L)) U3_GGGG(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_GGGG(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) U4_GGGG(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> REACH_IN_GGGG(Y, Z, E, V1) The TRS R consists of the following rules: reach_in_gggg(X, Y, E, L) -> U1_gggg(X, Y, E, L, member_in_gg(.(X, .(Y, [])), E)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_gggg(X, Y, E, L, member_out_gg(.(X, .(Y, [])), E)) -> reach_out_gggg(X, Y, E, L) reach_in_gggg(X, Z, E, L) -> U2_gggg(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_gggg(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_gggg(X, Z, E, L, Y, member_in_gg(Y, L)) U3_gggg(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_gggg(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) U4_gggg(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> U5_gggg(X, Z, E, L, reach_in_gggg(Y, Z, E, V1)) U5_gggg(X, Z, E, L, reach_out_gggg(Y, Z, E, V1)) -> reach_out_gggg(X, Z, E, L) The argument filtering Pi contains the following mapping: reach_in_gggg(x1, x2, x3, x4) = reach_in_gggg(x1, x2, x3, x4) U1_gggg(x1, x2, x3, x4, x5) = U1_gggg(x5) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] reach_out_gggg(x1, x2, x3, x4) = reach_out_gggg U2_gggg(x1, x2, x3, x4, x5) = U2_gggg(x2, x3, x4, x5) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) U3_gggg(x1, x2, x3, x4, x5, x6) = U3_gggg(x2, x3, x4, x5, x6) U4_gggg(x1, x2, x3, x4, x5, x6) = U4_gggg(x2, x3, x5, x6) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) U5_gggg(x1, x2, x3, x4, x5) = U5_gggg(x5) REACH_IN_GGGG(x1, x2, x3, x4) = REACH_IN_GGGG(x1, x2, x3, x4) U2_GGGG(x1, x2, x3, x4, x5) = U2_GGGG(x2, x3, x4, x5) U3_GGGG(x1, x2, x3, x4, x5, x6) = U3_GGGG(x2, x3, x4, x5, x6) U4_GGGG(x1, x2, x3, x4, x5, x6) = U4_GGGG(x2, x3, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGGG(X, Z, E, L) -> U2_GGGG(X, Z, E, L, member1_in_ag(.(X, .(Y, [])), E)) U2_GGGG(X, Z, E, L, member1_out_ag(.(X, .(Y, [])), E)) -> U3_GGGG(X, Z, E, L, Y, member_in_gg(Y, L)) U3_GGGG(X, Z, E, L, Y, member_out_gg(Y, L)) -> U4_GGGG(X, Z, E, L, Y, delete_in_gga(Y, L, V1)) U4_GGGG(X, Z, E, L, Y, delete_out_gga(Y, L, V1)) -> REACH_IN_GGGG(Y, Z, E, V1) The TRS R consists of the following rules: member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U7_ag(X, H, L, member1_in_ag(X, L)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U6_gg(X, H, L, member_in_gg(X, L)) delete_in_gga(X, .(X, Y), Y) -> delete_out_gga(X, .(X, Y), Y) delete_in_gga(X, .(H, T1), .(H, T2)) -> U8_gga(X, H, T1, T2, delete_in_gga(X, T1, T2)) U7_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U6_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U8_gga(X, H, T1, T2, delete_out_gga(X, T1, T2)) -> delete_out_gga(X, .(H, T1), .(H, T2)) The argument filtering Pi contains the following mapping: member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U6_gg(x1, x2, x3, x4) = U6_gg(x4) [] = [] member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U7_ag(x1, x2, x3, x4) = U7_ag(x4) delete_in_gga(x1, x2, x3) = delete_in_gga(x1, x2) delete_out_gga(x1, x2, x3) = delete_out_gga(x3) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x2, x5) REACH_IN_GGGG(x1, x2, x3, x4) = REACH_IN_GGGG(x1, x2, x3, x4) U2_GGGG(x1, x2, x3, x4, x5) = U2_GGGG(x2, x3, x4, x5) U3_GGGG(x1, x2, x3, x4, x5, x6) = U3_GGGG(x2, x3, x4, x5, x6) U4_GGGG(x1, x2, x3, x4, x5, x6) = U4_GGGG(x2, x3, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGGG(X, Z, E, L) -> U2_GGGG(Z, E, L, member1_in_ag(E)) U2_GGGG(Z, E, L, member1_out_ag(.(X, .(Y, [])))) -> U3_GGGG(Z, E, L, Y, member_in_gg(Y, L)) U3_GGGG(Z, E, L, Y, member_out_gg) -> U4_GGGG(Z, E, Y, delete_in_gga(Y, L)) U4_GGGG(Z, E, Y, delete_out_gga(V1)) -> REACH_IN_GGGG(Y, Z, E, V1) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H) member1_in_ag(.(H, L)) -> U7_ag(member1_in_ag(L)) member_in_gg(H, .(H, L)) -> member_out_gg member_in_gg(X, .(H, L)) -> U6_gg(member_in_gg(X, L)) delete_in_gga(X, .(X, Y)) -> delete_out_gga(Y) delete_in_gga(X, .(H, T1)) -> U8_gga(H, delete_in_gga(X, T1)) U7_ag(member1_out_ag(X)) -> member1_out_ag(X) U6_gg(member_out_gg) -> member_out_gg U8_gga(H, delete_out_gga(T2)) -> delete_out_gga(.(H, T2)) The set Q consists of the following terms: member1_in_ag(x0) member_in_gg(x0, x1) delete_in_gga(x0, x1) U7_ag(x0) U6_gg(x0) U8_gga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U2_GGGG(Z, E, L, member1_out_ag(.(X, .(Y, [])))) -> U3_GGGG(Z, E, L, Y, member_in_gg(Y, L)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U2_GGGG_4(x_1, ..., x_4) ) = 2x_3 + 1 POL( member1_in_ag_1(x_1) ) = 0 POL( ._2(x_1, x_2) ) = 2x_2 + 1 POL( member1_out_ag_1(x_1) ) = 0 POL( U7_ag_1(x_1) ) = max{0, -2} POL( U3_GGGG_5(x_1, ..., x_5) ) = 2x_3 POL( member_in_gg_2(x_1, x_2) ) = 0 POL( member_out_gg ) = 0 POL( U6_gg_1(x_1) ) = max{0, -2} POL( U4_GGGG_4(x_1, ..., x_4) ) = max{0, 2x_4 - 1} POL( delete_in_gga_2(x_1, x_2) ) = x_2 POL( delete_out_gga_1(x_1) ) = 2x_1 + 1 POL( U8_gga_2(x_1, x_2) ) = 2x_2 + 1 POL( REACH_IN_GGGG_4(x_1, ..., x_4) ) = 2x_4 + 1 POL( [] ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: delete_in_gga(X, .(X, Y)) -> delete_out_gga(Y) delete_in_gga(X, .(H, T1)) -> U8_gga(H, delete_in_gga(X, T1)) U8_gga(H, delete_out_gga(T2)) -> delete_out_gga(.(H, T2)) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGGG(X, Z, E, L) -> U2_GGGG(Z, E, L, member1_in_ag(E)) U3_GGGG(Z, E, L, Y, member_out_gg) -> U4_GGGG(Z, E, Y, delete_in_gga(Y, L)) U4_GGGG(Z, E, Y, delete_out_gga(V1)) -> REACH_IN_GGGG(Y, Z, E, V1) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H) member1_in_ag(.(H, L)) -> U7_ag(member1_in_ag(L)) member_in_gg(H, .(H, L)) -> member_out_gg member_in_gg(X, .(H, L)) -> U6_gg(member_in_gg(X, L)) delete_in_gga(X, .(X, Y)) -> delete_out_gga(Y) delete_in_gga(X, .(H, T1)) -> U8_gga(H, delete_in_gga(X, T1)) U7_ag(member1_out_ag(X)) -> member1_out_ag(X) U6_gg(member_out_gg) -> member_out_gg U8_gga(H, delete_out_gga(T2)) -> delete_out_gga(.(H, T2)) The set Q consists of the following terms: member1_in_ag(x0) member_in_gg(x0, x1) delete_in_gga(x0, x1) U7_ag(x0) U6_gg(x0) U8_gga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (36) TRUE