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