MAYBE 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) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 11 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 [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) TransformationProof [SOUND, 0 ms] (27) QDP (28) TransformationProof [EQUIVALENT, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) PrologToPiTRSProof [SOUND, 0 ms] (33) PiTRS (34) DependencyPairsProof [EQUIVALENT, 0 ms] (35) PiDP (36) DependencyGraphProof [EQUIVALENT, 0 ms] (37) AND (38) PiDP (39) UsableRulesProof [EQUIVALENT, 0 ms] (40) PiDP (41) PiDPToQDPProof [SOUND, 0 ms] (42) QDP (43) QDPSizeChangeProof [EQUIVALENT, 1 ms] (44) YES (45) PiDP (46) UsableRulesProof [EQUIVALENT, 0 ms] (47) PiDP (48) PiDPToQDPProof [EQUIVALENT, 0 ms] (49) QDP (50) QDPSizeChangeProof [EQUIVALENT, 0 ms] (51) YES (52) PiDP (53) UsableRulesProof [EQUIVALENT, 0 ms] (54) PiDP (55) PiDPToQDPProof [SOUND, 0 ms] (56) QDP (57) TransformationProof [SOUND, 0 ms] (58) QDP (59) TransformationProof [EQUIVALENT, 0 ms] (60) QDP (61) TransformationProof [EQUIVALENT, 0 ms] (62) QDP (63) PrologToDTProblemTransformerProof [SOUND, 0 ms] (64) TRIPLES (65) TriplesToPiDPProof [SOUND, 0 ms] (66) PiDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) AND (69) PiDP (70) UsableRulesProof [EQUIVALENT, 0 ms] (71) PiDP (72) PiDPToQDPProof [SOUND, 0 ms] (73) QDP (74) QDPSizeChangeProof [EQUIVALENT, 0 ms] (75) YES (76) PiDP (77) UsableRulesProof [EQUIVALENT, 0 ms] (78) PiDP (79) PiDPToQDPProof [EQUIVALENT, 0 ms] (80) QDP (81) QDPSizeChangeProof [EQUIVALENT, 0 ms] (82) YES (83) PiDP (84) PiDPToQDPProof [SOUND, 0 ms] (85) QDP (86) TransformationProof [SOUND, 0 ms] (87) QDP (88) PrologToTRSTransformerProof [SOUND, 28 ms] (89) QTRS (90) DependencyPairsProof [EQUIVALENT, 0 ms] (91) QDP (92) DependencyGraphProof [EQUIVALENT, 0 ms] (93) AND (94) QDP (95) UsableRulesProof [EQUIVALENT, 1 ms] (96) QDP (97) QDPSizeChangeProof [EQUIVALENT, 0 ms] (98) YES (99) QDP (100) UsableRulesProof [EQUIVALENT, 1 ms] (101) QDP (102) QDPSizeChangeProof [EQUIVALENT, 0 ms] (103) YES (104) QDP (105) NonTerminationLoopProof [COMPLETE, 551 ms] (106) NO (107) PrologToIRSwTTransformerProof [SOUND, 41 ms] (108) AND (109) IRSwT (110) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (111) IRSwT (112) IntTRSCompressionProof [EQUIVALENT, 35 ms] (113) IRSwT (114) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (115) IRSwT (116) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (117) IRSwT (118) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (119) IRSwT (120) TempFilterProof [SOUND, 3 ms] (121) IRSwT (122) IRSwTToQDPProof [SOUND, 0 ms] (123) QDP (124) QDPSizeChangeProof [EQUIVALENT, 0 ms] (125) YES (126) IRSwT (127) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (128) IRSwT (129) IntTRSCompressionProof [EQUIVALENT, 2 ms] (130) IRSwT (131) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (132) IRSwT (133) IRSwTTerminationDigraphProof [EQUIVALENT, 1 ms] (134) IRSwT (135) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (136) IRSwT (137) TempFilterProof [SOUND, 1 ms] (138) IRSwT (139) IRSwTToQDPProof [SOUND, 0 ms] (140) QDP (141) QDPSizeChangeProof [EQUIVALENT, 0 ms] (142) YES (143) IRSwT (144) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (145) IRSwT (146) IntTRSCompressionProof [EQUIVALENT, 8 ms] (147) IRSwT (148) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (149) IRSwT (150) IRSwTTerminationDigraphProof [EQUIVALENT, 14 ms] (151) IRSwT ---------------------------------------- (0) Obligation: Clauses: reach(X, Y, Edges) :- member(.(X, .(Y, [])), Edges). reach(X, Z, Edges) :- ','(member1(.(X, .(Y, [])), Edges), reach(Y, Z, Edges)). member(H, .(H, L)). member(X, .(H, L)) :- member(X, L). member1(H, .(H, L)). member1(X, .(H, L)) :- member1(X, L). Query: reach(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_3: (b,b,b) member_in_2: (b,b) member1_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) 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_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) ---------------------------------------- (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_GGG(X, Y, Edges) -> U1_GGG(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Y, Edges) -> MEMBER_IN_GG(.(X, .(Y, [])), Edges) MEMBER_IN_GG(X, .(H, L)) -> U4_GG(X, H, L, member_in_gg(X, L)) MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Z, Edges) -> MEMBER1_IN_AG(.(X, .(Y, [])), Edges) MEMBER1_IN_AG(X, .(H, L)) -> U5_AG(X, H, L, member1_in_ag(X, L)) MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_GGG(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4) = U1_GGG(x4) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) U4_GG(x1, x2, x3, x4) = U4_GG(x4) U2_GGG(x1, x2, x3, x4) = U2_GGG(x2, x3, x4) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) U5_AG(x1, x2, x3, x4) = U5_AG(x4) U3_GGG(x1, x2, x3, x4) = U3_GGG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGG(X, Y, Edges) -> U1_GGG(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Y, Edges) -> MEMBER_IN_GG(.(X, .(Y, [])), Edges) MEMBER_IN_GG(X, .(H, L)) -> U4_GG(X, H, L, member_in_gg(X, L)) MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Z, Edges) -> MEMBER1_IN_AG(.(X, .(Y, [])), Edges) MEMBER1_IN_AG(X, .(H, L)) -> U5_AG(X, H, L, member1_in_ag(X, L)) MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_GGG(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4) = U1_GGG(x4) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) U4_GG(x1, x2, x3, x4) = U4_GG(x4) U2_GGG(x1, x2, x3, x4) = U2_GGG(x2, x3, x4) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) U5_AG(x1, x2, x3, x4) = U5_AG(x4) U3_GGG(x1, x2, x3, x4) = U3_GGG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) 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_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(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: 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 ---------------------------------------- (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: MEMBER1_IN_AG(.(H, L)) -> MEMBER1_IN_AG(L) 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: *MEMBER1_IN_AG(.(H, L)) -> MEMBER1_IN_AG(L) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) 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_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, 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: 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 ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) 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: 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. ---------------------------------------- (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: *MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg U4_gg(x1, x2, x3, x4) = U4_gg(x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg U2_ggg(x1, x2, x3, x4) = U2_ggg(x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U2_GGG(x1, x2, x3, x4) = U2_GGG(x2, x3, x4) 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: REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) 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)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1) U5_ag(x1, x2, x3, x4) = U5_ag(x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U2_GGG(x1, x2, x3, x4) = U2_GGG(x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) 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: REACH_IN_GGG(X, Z, Edges) -> U2_GGG(Z, Edges, member1_in_ag(Edges)) U2_GGG(Z, Edges, member1_out_ag(.(X, .(Y, [])))) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H) member1_in_ag(.(H, L)) -> U5_ag(member1_in_ag(L)) U5_ag(member1_out_ag(X)) -> member1_out_ag(X) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (SOUND) By narrowing [LPAR04] the rule REACH_IN_GGG(X, Z, Edges) -> U2_GGG(Z, Edges, member1_in_ag(Edges)) at position [2] we obtained the following new rules [LPAR04]: (REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), member1_out_ag(x0)),REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), member1_out_ag(x0))) (REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), U5_ag(member1_in_ag(x1))),REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), U5_ag(member1_in_ag(x1)))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GGG(Z, Edges, member1_out_ag(.(X, .(Y, [])))) -> REACH_IN_GGG(Y, Z, Edges) REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), member1_out_ag(x0)) REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), U5_ag(member1_in_ag(x1))) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H) member1_in_ag(.(H, L)) -> U5_ag(member1_in_ag(L)) U5_ag(member1_out_ag(X)) -> member1_out_ag(X) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U2_GGG(Z, Edges, member1_out_ag(.(X, .(Y, [])))) -> REACH_IN_GGG(Y, Z, Edges) we obtained the following new rules [LPAR04]: (U2_GGG(z1, .(.(x2, .(x3, [])), z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(.(x2, .(x3, [])), z3)),U2_GGG(z1, .(.(x2, .(x3, [])), z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(.(x2, .(x3, [])), z3))) (U2_GGG(z1, .(z2, z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(z2, z3)),U2_GGG(z1, .(z2, z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(z2, z3))) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), member1_out_ag(x0)) REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), U5_ag(member1_in_ag(x1))) U2_GGG(z1, .(.(x2, .(x3, [])), z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(.(x2, .(x3, [])), z3)) U2_GGG(z1, .(z2, z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(z2, z3)) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H) member1_in_ag(.(H, L)) -> U5_ag(member1_in_ag(L)) U5_ag(member1_out_ag(X)) -> member1_out_ag(X) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), member1_out_ag(x0)) we obtained the following new rules [LPAR04]: (REACH_IN_GGG(x0, x1, .(.(y_1, .(y_2, [])), x3)) -> U2_GGG(x1, .(.(y_1, .(y_2, [])), x3), member1_out_ag(.(y_1, .(y_2, [])))),REACH_IN_GGG(x0, x1, .(.(y_1, .(y_2, [])), x3)) -> U2_GGG(x1, .(.(y_1, .(y_2, [])), x3), member1_out_ag(.(y_1, .(y_2, []))))) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y1, .(x0, x1), U5_ag(member1_in_ag(x1))) U2_GGG(z1, .(.(x2, .(x3, [])), z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(.(x2, .(x3, [])), z3)) U2_GGG(z1, .(z2, z3), member1_out_ag(.(x2, .(x3, [])))) -> REACH_IN_GGG(x3, z1, .(z2, z3)) REACH_IN_GGG(x0, x1, .(.(y_1, .(y_2, [])), x3)) -> U2_GGG(x1, .(.(y_1, .(y_2, [])), x3), member1_out_ag(.(y_1, .(y_2, [])))) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H) member1_in_ag(.(H, L)) -> U5_ag(member1_in_ag(L)) U5_ag(member1_out_ag(X)) -> member1_out_ag(X) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) 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_3: (b,b,b) member_in_2: (b,b) member1_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (33) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) ---------------------------------------- (34) 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_GGG(X, Y, Edges) -> U1_GGG(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Y, Edges) -> MEMBER_IN_GG(.(X, .(Y, [])), Edges) MEMBER_IN_GG(X, .(H, L)) -> U4_GG(X, H, L, member_in_gg(X, L)) MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Z, Edges) -> MEMBER1_IN_AG(.(X, .(Y, [])), Edges) MEMBER1_IN_AG(X, .(H, L)) -> U5_AG(X, H, L, member1_in_ag(X, L)) MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_GGG(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4) = U1_GGG(x1, x2, x3, x4) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U2_GGG(x1, x2, x3, x4) = U2_GGG(x1, x2, x3, x4) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) U5_AG(x1, x2, x3, x4) = U5_AG(x2, x3, x4) U3_GGG(x1, x2, x3, x4) = U3_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGG(X, Y, Edges) -> U1_GGG(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Y, Edges) -> MEMBER_IN_GG(.(X, .(Y, [])), Edges) MEMBER_IN_GG(X, .(H, L)) -> U4_GG(X, H, L, member_in_gg(X, L)) MEMBER_IN_GG(X, .(H, L)) -> MEMBER_IN_GG(X, L) REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) REACH_IN_GGG(X, Z, Edges) -> MEMBER1_IN_AG(.(X, .(Y, [])), Edges) MEMBER1_IN_AG(X, .(H, L)) -> U5_AG(X, H, L, member1_in_ag(X, L)) MEMBER1_IN_AG(X, .(H, L)) -> MEMBER1_IN_AG(X, L) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_GGG(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4) = U1_GGG(x1, x2, x3, x4) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U2_GGG(x1, x2, x3, x4) = U2_GGG(x1, x2, x3, x4) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) U5_AG(x1, x2, x3, x4) = U5_AG(x2, x3, x4) U3_GGG(x1, x2, x3, x4) = U3_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (37) Complex Obligation (AND) ---------------------------------------- (38) 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_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (39) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (40) 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 ---------------------------------------- (41) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (42) 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. ---------------------------------------- (43) 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 ---------------------------------------- (44) YES ---------------------------------------- (45) 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_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (46) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (47) 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 ---------------------------------------- (48) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (49) 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. ---------------------------------------- (50) 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 ---------------------------------------- (51) YES ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: reach_in_ggg(X, Y, Edges) -> U1_ggg(X, Y, Edges, member_in_gg(.(X, .(Y, [])), Edges)) member_in_gg(H, .(H, L)) -> member_out_gg(H, .(H, L)) member_in_gg(X, .(H, L)) -> U4_gg(X, H, L, member_in_gg(X, L)) U4_gg(X, H, L, member_out_gg(X, L)) -> member_out_gg(X, .(H, L)) U1_ggg(X, Y, Edges, member_out_gg(.(X, .(Y, [])), Edges)) -> reach_out_ggg(X, Y, Edges) reach_in_ggg(X, Z, Edges) -> U2_ggg(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) member1_in_ag(H, .(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(X, .(H, L)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) U2_ggg(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> U3_ggg(X, Z, Edges, reach_in_ggg(Y, Z, Edges)) U3_ggg(X, Z, Edges, reach_out_ggg(Y, Z, Edges)) -> reach_out_ggg(X, Z, Edges) The argument filtering Pi contains the following mapping: reach_in_ggg(x1, x2, x3) = reach_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4) = U1_ggg(x1, x2, x3, x4) member_in_gg(x1, x2) = member_in_gg(x1, x2) .(x1, x2) = .(x1, x2) member_out_gg(x1, x2) = member_out_gg(x1, x2) U4_gg(x1, x2, x3, x4) = U4_gg(x1, x2, x3, x4) [] = [] reach_out_ggg(x1, x2, x3) = reach_out_ggg(x1, x2, x3) U2_ggg(x1, x2, x3, x4) = U2_ggg(x1, x2, x3, x4) member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) U3_ggg(x1, x2, x3, x4) = U3_ggg(x1, x2, x3, x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U2_GGG(x1, x2, x3, x4) = U2_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (53) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (54) Obligation: Pi DP problem: The TRS P consists of the following rules: REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(.(X, .(Y, [])), Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) 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)) -> U5_ag(X, H, L, member1_in_ag(X, L)) U5_ag(X, H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] member1_in_ag(x1, x2) = member1_in_ag(x2) member1_out_ag(x1, x2) = member1_out_ag(x1, x2) U5_ag(x1, x2, x3, x4) = U5_ag(x2, x3, x4) REACH_IN_GGG(x1, x2, x3) = REACH_IN_GGG(x1, x2, x3) U2_GGG(x1, x2, x3, x4) = U2_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (55) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(Edges)) U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(.(H, L)) -> U5_ag(H, L, member1_in_ag(L)) U5_ag(H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (SOUND) By narrowing [LPAR04] the rule REACH_IN_GGG(X, Z, Edges) -> U2_GGG(X, Z, Edges, member1_in_ag(Edges)) at position [3] we obtained the following new rules [LPAR04]: (REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), member1_out_ag(x0, .(x0, x1))),REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), member1_out_ag(x0, .(x0, x1)))) (REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), U5_ag(x0, x1, member1_in_ag(x1))),REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), U5_ag(x0, x1, member1_in_ag(x1)))) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), member1_out_ag(x0, .(x0, x1))) REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), U5_ag(x0, x1, member1_in_ag(x1))) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(.(H, L)) -> U5_ag(H, L, member1_in_ag(L)) U5_ag(H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (59) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U2_GGG(X, Z, Edges, member1_out_ag(.(X, .(Y, [])), Edges)) -> REACH_IN_GGG(Y, Z, Edges) we obtained the following new rules [LPAR04]: (U2_GGG(z0, z1, .(.(z0, .(x3, [])), z3), member1_out_ag(.(z0, .(x3, [])), .(.(z0, .(x3, [])), z3))) -> REACH_IN_GGG(x3, z1, .(.(z0, .(x3, [])), z3)),U2_GGG(z0, z1, .(.(z0, .(x3, [])), z3), member1_out_ag(.(z0, .(x3, [])), .(.(z0, .(x3, [])), z3))) -> REACH_IN_GGG(x3, z1, .(.(z0, .(x3, [])), z3))) (U2_GGG(z0, z1, .(z2, z3), member1_out_ag(.(z0, .(x3, [])), .(z2, z3))) -> REACH_IN_GGG(x3, z1, .(z2, z3)),U2_GGG(z0, z1, .(z2, z3), member1_out_ag(.(z0, .(x3, [])), .(z2, z3))) -> REACH_IN_GGG(x3, z1, .(z2, z3))) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), member1_out_ag(x0, .(x0, x1))) REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), U5_ag(x0, x1, member1_in_ag(x1))) U2_GGG(z0, z1, .(.(z0, .(x3, [])), z3), member1_out_ag(.(z0, .(x3, [])), .(.(z0, .(x3, [])), z3))) -> REACH_IN_GGG(x3, z1, .(.(z0, .(x3, [])), z3)) U2_GGG(z0, z1, .(z2, z3), member1_out_ag(.(z0, .(x3, [])), .(z2, z3))) -> REACH_IN_GGG(x3, z1, .(z2, z3)) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(.(H, L)) -> U5_ag(H, L, member1_in_ag(L)) U5_ag(H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), member1_out_ag(x0, .(x0, x1))) we obtained the following new rules [LPAR04]: (REACH_IN_GGG(x0, x1, .(.(y_2, .(y_3, [])), x3)) -> U2_GGG(x0, x1, .(.(y_2, .(y_3, [])), x3), member1_out_ag(.(y_2, .(y_3, [])), .(.(y_2, .(y_3, [])), x3))),REACH_IN_GGG(x0, x1, .(.(y_2, .(y_3, [])), x3)) -> U2_GGG(x0, x1, .(.(y_2, .(y_3, [])), x3), member1_out_ag(.(y_2, .(y_3, [])), .(.(y_2, .(y_3, [])), x3)))) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: REACH_IN_GGG(y0, y1, .(x0, x1)) -> U2_GGG(y0, y1, .(x0, x1), U5_ag(x0, x1, member1_in_ag(x1))) U2_GGG(z0, z1, .(.(z0, .(x3, [])), z3), member1_out_ag(.(z0, .(x3, [])), .(.(z0, .(x3, [])), z3))) -> REACH_IN_GGG(x3, z1, .(.(z0, .(x3, [])), z3)) U2_GGG(z0, z1, .(z2, z3), member1_out_ag(.(z0, .(x3, [])), .(z2, z3))) -> REACH_IN_GGG(x3, z1, .(z2, z3)) REACH_IN_GGG(x0, x1, .(.(y_2, .(y_3, [])), x3)) -> U2_GGG(x0, x1, .(.(y_2, .(y_3, [])), x3), member1_out_ag(.(y_2, .(y_3, [])), .(.(y_2, .(y_3, [])), x3))) The TRS R consists of the following rules: member1_in_ag(.(H, L)) -> member1_out_ag(H, .(H, L)) member1_in_ag(.(H, L)) -> U5_ag(H, L, member1_in_ag(L)) U5_ag(H, L, member1_out_ag(X, L)) -> member1_out_ag(X, .(H, L)) The set Q consists of the following terms: member1_in_ag(x0) U5_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (63) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(reach X Y Edges)", "(member (. X (. Y ([]))) Edges)" ], [ "(reach X Z Edges)", "(',' (member1 (. X (. Y ([]))) Edges) (reach Y Z Edges))" ], [ "(member H (. H L))", null ], [ "(member X (. H L))", "(member X L)" ], [ "(member1 H (. H L))", null ], [ "(member1 X (. H L))", "(member1 X L)" ] ] }, "graph": { "nodes": { "type": "Nodes", "172": { "goal": [{ "clause": 1, "scope": 1, "term": "(reach T7 T8 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "293": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T133 (. X114 ([]))) T135)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T133", "T135" ], "free": ["X114"], "exprvars": [] } }, "294": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [ { "clause": 2, "scope": 3, "term": "(member (. T41 (. T42 ([]))) T44)" }, { "clause": 3, "scope": 3, "term": "(member (. T41 (. T42 ([]))) T44)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "112": { "goal": [{ "clause": 2, "scope": 3, "term": "(member (. T41 (. T42 ([]))) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "113": { "goal": [{ "clause": 3, "scope": 3, "term": "(member (. T41 (. T42 ([]))) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "114": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member1 (. T96 (. X75 ([]))) T98) (reach X75 T97 T98))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97", "T98" ], "free": ["X75"], "exprvars": [] } }, "115": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "116": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "118": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T74 (. T75 ([]))) T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T75", "T77" ], "free": [], "exprvars": [] } }, "119": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T41 (. T42 ([]))) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "53": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [ { "clause": 2, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }, { "clause": 3, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(reach T7 T8 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "33": { "goal": [{ "clause": 2, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "34": { "goal": [ { "clause": 3, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(reach T7 T8 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": 3, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "280": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T96 (. X75 ([]))) T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "281": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T105 T97 T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T97", "T98", "T105" ], "free": [], "exprvars": [] } }, "282": { "goal": [ { "clause": 4, "scope": 4, "term": "(member1 (. T96 (. X75 ([]))) T98)" }, { "clause": 5, "scope": 4, "term": "(member1 (. T96 (. X75 ([]))) T98)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "283": { "goal": [{ "clause": 4, "scope": 4, "term": "(member1 (. T96 (. X75 ([]))) T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "284": { "goal": [{ "clause": 5, "scope": 4, "term": "(member1 (. T96 (. X75 ([]))) T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "285": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "286": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "287": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "8": { "goal": [ { "clause": -1, "scope": -1, "term": "(member (. T7 (. T8 ([]))) T9)" }, { "clause": 1, "scope": 1, "term": "(reach T7 T8 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "41": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(reach T7 T8 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 8, "label": "ONLY EVAL with clause\nreach(X4, X5, X6) :- member(.(X4, .(X5, [])), X6).\nand substitutionT1 -> T7,\nX4 -> T7,\nT2 -> T8,\nX5 -> T8,\nT3 -> T9,\nX6 -> T9" }, { "from": 8, "to": 11, "label": "CASE" }, { "from": 11, "to": 33, "label": "PARALLEL" }, { "from": 11, "to": 34, "label": "PARALLEL" }, { "from": 33, "to": 35, "label": "EVAL with clause\nmember(X15, .(X15, X16)).\nand substitutionT7 -> T22,\nT8 -> T23,\nX15 -> .(T22, .(T23, [])),\nX16 -> T24,\nT9 -> .(.(T22, .(T23, [])), T24)" }, { "from": 33, "to": 36, "label": "EVAL-BACKTRACK" }, { "from": 34, "to": 39, "label": "PARALLEL" }, { "from": 34, "to": 41, "label": "PARALLEL" }, { "from": 35, "to": 37, "label": "SUCCESS" }, { "from": 39, "to": 50, "label": "EVAL with clause\nmember(X29, .(X30, X31)) :- member(X29, X31).\nand substitutionT7 -> T41,\nT8 -> T42,\nX29 -> .(T41, .(T42, [])),\nX30 -> T43,\nX31 -> T44,\nT9 -> .(T43, T44)" }, { "from": 39, "to": 53, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 172, "label": "FAILURE" }, { "from": 50, "to": 111, "label": "CASE" }, { "from": 111, "to": 112, "label": "PARALLEL" }, { "from": 111, "to": 113, "label": "PARALLEL" }, { "from": 112, "to": 114, "label": "EVAL with clause\nmember(X44, .(X44, X45)).\nand substitutionT41 -> T63,\nT42 -> T64,\nX44 -> .(T63, .(T64, [])),\nX45 -> T65,\nT44 -> .(.(T63, .(T64, [])), T65)" }, { "from": 112, "to": 115, "label": "EVAL-BACKTRACK" }, { "from": 113, "to": 118, "label": "EVAL with clause\nmember(X52, .(X53, X54)) :- member(X52, X54).\nand substitutionT41 -> T74,\nT42 -> T75,\nX52 -> .(T74, .(T75, [])),\nX53 -> T76,\nX54 -> T77,\nT44 -> .(T76, T77)" }, { "from": 113, "to": 119, "label": "EVAL-BACKTRACK" }, { "from": 114, "to": 116, "label": "SUCCESS" }, { "from": 118, "to": 50, "label": "INSTANCE with matching:\nT41 -> T74\nT42 -> T75\nT44 -> T77" }, { "from": 172, "to": 279, "label": "ONLY EVAL with clause\nreach(X72, X73, X74) :- ','(member1(.(X72, .(X75, [])), X74), reach(X75, X73, X74)).\nand substitutionT7 -> T96,\nX72 -> T96,\nT8 -> T97,\nX73 -> T97,\nT9 -> T98,\nX74 -> T98" }, { "from": 279, "to": 280, "label": "SPLIT 1" }, { "from": 279, "to": 281, "label": "SPLIT 2\nnew knowledge:\nT96 is ground\nT105 is ground\nT98 is ground\nreplacements:X75 -> T105" }, { "from": 280, "to": 282, "label": "CASE" }, { "from": 281, "to": 1, "label": "INSTANCE with matching:\nT1 -> T105\nT2 -> T97\nT3 -> T98" }, { "from": 282, "to": 283, "label": "PARALLEL" }, { "from": 282, "to": 284, "label": "PARALLEL" }, { "from": 283, "to": 285, "label": "EVAL with clause\nmember1(X100, .(X100, X101)).\nand substitutionT96 -> T124,\nX75 -> T125,\nX100 -> .(T124, .(T125, [])),\nX102 -> T125,\nX101 -> T126,\nT98 -> .(.(T124, .(T125, [])), T126)" }, { "from": 283, "to": 286, "label": "EVAL-BACKTRACK" }, { "from": 284, "to": 293, "label": "EVAL with clause\nmember1(X111, .(X112, X113)) :- member1(X111, X113).\nand substitutionT96 -> T133,\nX75 -> X114,\nX111 -> .(T133, .(X114, [])),\nX112 -> T134,\nX113 -> T135,\nT98 -> .(T134, T135)" }, { "from": 284, "to": 294, "label": "EVAL-BACKTRACK" }, { "from": 285, "to": 287, "label": "SUCCESS" }, { "from": 293, "to": 280, "label": "INSTANCE with matching:\nT96 -> T133\nX75 -> X114\nT98 -> T135" } ], "type": "Graph" } } ---------------------------------------- (64) Obligation: Triples: memberA(X1, X2, .(X3, X4)) :- memberA(X1, X2, X4). member1C(X1, X2, .(X3, X4)) :- member1C(X1, X2, X4). reachB(X1, X2, .(X3, X4)) :- memberA(X1, X2, X4). reachB(X1, X2, X3) :- member1C(X1, X4, X3). reachB(X1, X2, X3) :- ','(member1cC(X1, X4, X3), reachB(X4, X2, X3)). Clauses: membercA(X1, X2, .(.(X1, .(X2, [])), X3)). membercA(X1, X2, .(X3, X4)) :- membercA(X1, X2, X4). reachcB(X1, X2, .(.(X1, .(X2, [])), X3)). reachcB(X1, X2, .(X3, X4)) :- membercA(X1, X2, X4). reachcB(X1, X2, X3) :- ','(member1cC(X1, X4, X3), reachcB(X4, X2, X3)). member1cC(X1, X2, .(.(X1, .(X2, [])), X3)). member1cC(X1, X2, .(X3, X4)) :- member1cC(X1, X2, X4). Afs: reachB(x1, x2, x3) = reachB(x1, x2, x3) ---------------------------------------- (65) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: reachB_in_3: (b,b,b) memberA_in_3: (b,b,b) member1C_in_3: (b,f,b) member1cC_in_3: (b,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: REACHB_IN_GGG(X1, X2, .(X3, X4)) -> U3_GGG(X1, X2, X3, X4, memberA_in_ggg(X1, X2, X4)) REACHB_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> U1_GGG(X1, X2, X3, X4, memberA_in_ggg(X1, X2, X4)) MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) REACHB_IN_GGG(X1, X2, X3) -> U4_GGG(X1, X2, X3, member1C_in_gag(X1, X4, X3)) REACHB_IN_GGG(X1, X2, X3) -> MEMBER1C_IN_GAG(X1, X4, X3) MEMBER1C_IN_GAG(X1, X2, .(X3, X4)) -> U2_GAG(X1, X2, X3, X4, member1C_in_gag(X1, X2, X4)) MEMBER1C_IN_GAG(X1, X2, .(X3, X4)) -> MEMBER1C_IN_GAG(X1, X2, X4) REACHB_IN_GGG(X1, X2, X3) -> U5_GGG(X1, X2, X3, member1cC_in_gag(X1, X4, X3)) U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> U6_GGG(X1, X2, X3, reachB_in_ggg(X4, X2, X3)) U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> REACHB_IN_GGG(X4, X2, X3) The TRS R consists of the following rules: member1cC_in_gag(X1, X2, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, X2, .(X3, X4)) -> U12_gag(X1, X2, X3, X4, member1cC_in_gag(X1, X2, X4)) U12_gag(X1, X2, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The argument filtering Pi contains the following mapping: reachB_in_ggg(x1, x2, x3) = reachB_in_ggg(x1, x2, x3) .(x1, x2) = .(x1, x2) memberA_in_ggg(x1, x2, x3) = memberA_in_ggg(x1, x2, x3) member1C_in_gag(x1, x2, x3) = member1C_in_gag(x1, x3) member1cC_in_gag(x1, x2, x3) = member1cC_in_gag(x1, x3) [] = [] member1cC_out_gag(x1, x2, x3) = member1cC_out_gag(x1, x2, x3) U12_gag(x1, x2, x3, x4, x5) = U12_gag(x1, x3, x4, x5) REACHB_IN_GGG(x1, x2, x3) = REACHB_IN_GGG(x1, x2, x3) U3_GGG(x1, x2, x3, x4, x5) = U3_GGG(x1, x2, x3, x4, x5) MEMBERA_IN_GGG(x1, x2, x3) = MEMBERA_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4, x5) = U1_GGG(x1, x2, x3, x4, x5) U4_GGG(x1, x2, x3, x4) = U4_GGG(x1, x2, x3, x4) MEMBER1C_IN_GAG(x1, x2, x3) = MEMBER1C_IN_GAG(x1, x3) U2_GAG(x1, x2, x3, x4, x5) = U2_GAG(x1, x3, x4, x5) U5_GGG(x1, x2, x3, x4) = U5_GGG(x1, x2, x3, x4) U6_GGG(x1, x2, x3, x4) = U6_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (66) Obligation: Pi DP problem: The TRS P consists of the following rules: REACHB_IN_GGG(X1, X2, .(X3, X4)) -> U3_GGG(X1, X2, X3, X4, memberA_in_ggg(X1, X2, X4)) REACHB_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> U1_GGG(X1, X2, X3, X4, memberA_in_ggg(X1, X2, X4)) MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) REACHB_IN_GGG(X1, X2, X3) -> U4_GGG(X1, X2, X3, member1C_in_gag(X1, X4, X3)) REACHB_IN_GGG(X1, X2, X3) -> MEMBER1C_IN_GAG(X1, X4, X3) MEMBER1C_IN_GAG(X1, X2, .(X3, X4)) -> U2_GAG(X1, X2, X3, X4, member1C_in_gag(X1, X2, X4)) MEMBER1C_IN_GAG(X1, X2, .(X3, X4)) -> MEMBER1C_IN_GAG(X1, X2, X4) REACHB_IN_GGG(X1, X2, X3) -> U5_GGG(X1, X2, X3, member1cC_in_gag(X1, X4, X3)) U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> U6_GGG(X1, X2, X3, reachB_in_ggg(X4, X2, X3)) U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> REACHB_IN_GGG(X4, X2, X3) The TRS R consists of the following rules: member1cC_in_gag(X1, X2, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, X2, .(X3, X4)) -> U12_gag(X1, X2, X3, X4, member1cC_in_gag(X1, X2, X4)) U12_gag(X1, X2, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The argument filtering Pi contains the following mapping: reachB_in_ggg(x1, x2, x3) = reachB_in_ggg(x1, x2, x3) .(x1, x2) = .(x1, x2) memberA_in_ggg(x1, x2, x3) = memberA_in_ggg(x1, x2, x3) member1C_in_gag(x1, x2, x3) = member1C_in_gag(x1, x3) member1cC_in_gag(x1, x2, x3) = member1cC_in_gag(x1, x3) [] = [] member1cC_out_gag(x1, x2, x3) = member1cC_out_gag(x1, x2, x3) U12_gag(x1, x2, x3, x4, x5) = U12_gag(x1, x3, x4, x5) REACHB_IN_GGG(x1, x2, x3) = REACHB_IN_GGG(x1, x2, x3) U3_GGG(x1, x2, x3, x4, x5) = U3_GGG(x1, x2, x3, x4, x5) MEMBERA_IN_GGG(x1, x2, x3) = MEMBERA_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4, x5) = U1_GGG(x1, x2, x3, x4, x5) U4_GGG(x1, x2, x3, x4) = U4_GGG(x1, x2, x3, x4) MEMBER1C_IN_GAG(x1, x2, x3) = MEMBER1C_IN_GAG(x1, x3) U2_GAG(x1, x2, x3, x4, x5) = U2_GAG(x1, x3, x4, x5) U5_GGG(x1, x2, x3, x4) = U5_GGG(x1, x2, x3, x4) U6_GGG(x1, x2, x3, x4) = U6_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 7 less nodes. ---------------------------------------- (68) Complex Obligation (AND) ---------------------------------------- (69) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER1C_IN_GAG(X1, X2, .(X3, X4)) -> MEMBER1C_IN_GAG(X1, X2, X4) The TRS R consists of the following rules: member1cC_in_gag(X1, X2, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, X2, .(X3, X4)) -> U12_gag(X1, X2, X3, X4, member1cC_in_gag(X1, X2, X4)) U12_gag(X1, X2, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) member1cC_in_gag(x1, x2, x3) = member1cC_in_gag(x1, x3) [] = [] member1cC_out_gag(x1, x2, x3) = member1cC_out_gag(x1, x2, x3) U12_gag(x1, x2, x3, x4, x5) = U12_gag(x1, x3, x4, x5) MEMBER1C_IN_GAG(x1, x2, x3) = MEMBER1C_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (70) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (71) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER1C_IN_GAG(X1, X2, .(X3, X4)) -> MEMBER1C_IN_GAG(X1, X2, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) MEMBER1C_IN_GAG(x1, x2, x3) = MEMBER1C_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (72) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBER1C_IN_GAG(X1, .(X3, X4)) -> MEMBER1C_IN_GAG(X1, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (74) 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: *MEMBER1C_IN_GAG(X1, .(X3, X4)) -> MEMBER1C_IN_GAG(X1, X4) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (75) YES ---------------------------------------- (76) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) The TRS R consists of the following rules: member1cC_in_gag(X1, X2, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, X2, .(X3, X4)) -> U12_gag(X1, X2, X3, X4, member1cC_in_gag(X1, X2, X4)) U12_gag(X1, X2, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) member1cC_in_gag(x1, x2, x3) = member1cC_in_gag(x1, x3) [] = [] member1cC_out_gag(x1, x2, x3) = member1cC_out_gag(x1, x2, x3) U12_gag(x1, x2, x3, x4, x5) = U12_gag(x1, x3, x4, x5) MEMBERA_IN_GGG(x1, x2, x3) = MEMBERA_IN_GGG(x1, x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (77) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (78) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (79) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (81) 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: *MEMBERA_IN_GGG(X1, X2, .(X3, X4)) -> MEMBERA_IN_GGG(X1, X2, X4) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (82) YES ---------------------------------------- (83) Obligation: Pi DP problem: The TRS P consists of the following rules: REACHB_IN_GGG(X1, X2, X3) -> U5_GGG(X1, X2, X3, member1cC_in_gag(X1, X4, X3)) U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> REACHB_IN_GGG(X4, X2, X3) The TRS R consists of the following rules: member1cC_in_gag(X1, X2, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, X2, .(X3, X4)) -> U12_gag(X1, X2, X3, X4, member1cC_in_gag(X1, X2, X4)) U12_gag(X1, X2, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) member1cC_in_gag(x1, x2, x3) = member1cC_in_gag(x1, x3) [] = [] member1cC_out_gag(x1, x2, x3) = member1cC_out_gag(x1, x2, x3) U12_gag(x1, x2, x3, x4, x5) = U12_gag(x1, x3, x4, x5) REACHB_IN_GGG(x1, x2, x3) = REACHB_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4) = U5_GGG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (84) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: REACHB_IN_GGG(X1, X2, X3) -> U5_GGG(X1, X2, X3, member1cC_in_gag(X1, X3)) U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> REACHB_IN_GGG(X4, X2, X3) The TRS R consists of the following rules: member1cC_in_gag(X1, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, .(X3, X4)) -> U12_gag(X1, X3, X4, member1cC_in_gag(X1, X4)) U12_gag(X1, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The set Q consists of the following terms: member1cC_in_gag(x0, x1) U12_gag(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (86) TransformationProof (SOUND) By narrowing [LPAR04] the rule REACHB_IN_GGG(X1, X2, X3) -> U5_GGG(X1, X2, X3, member1cC_in_gag(X1, X3)) at position [3] we obtained the following new rules [LPAR04]: (REACHB_IN_GGG(x0, y1, .(.(x0, .(x1, [])), x2)) -> U5_GGG(x0, y1, .(.(x0, .(x1, [])), x2), member1cC_out_gag(x0, x1, .(.(x0, .(x1, [])), x2))),REACHB_IN_GGG(x0, y1, .(.(x0, .(x1, [])), x2)) -> U5_GGG(x0, y1, .(.(x0, .(x1, [])), x2), member1cC_out_gag(x0, x1, .(.(x0, .(x1, [])), x2)))) (REACHB_IN_GGG(x0, y1, .(x1, x2)) -> U5_GGG(x0, y1, .(x1, x2), U12_gag(x0, x1, x2, member1cC_in_gag(x0, x2))),REACHB_IN_GGG(x0, y1, .(x1, x2)) -> U5_GGG(x0, y1, .(x1, x2), U12_gag(x0, x1, x2, member1cC_in_gag(x0, x2)))) ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> REACHB_IN_GGG(X4, X2, X3) REACHB_IN_GGG(x0, y1, .(.(x0, .(x1, [])), x2)) -> U5_GGG(x0, y1, .(.(x0, .(x1, [])), x2), member1cC_out_gag(x0, x1, .(.(x0, .(x1, [])), x2))) REACHB_IN_GGG(x0, y1, .(x1, x2)) -> U5_GGG(x0, y1, .(x1, x2), U12_gag(x0, x1, x2, member1cC_in_gag(x0, x2))) The TRS R consists of the following rules: member1cC_in_gag(X1, .(.(X1, .(X2, [])), X3)) -> member1cC_out_gag(X1, X2, .(.(X1, .(X2, [])), X3)) member1cC_in_gag(X1, .(X3, X4)) -> U12_gag(X1, X3, X4, member1cC_in_gag(X1, X4)) U12_gag(X1, X3, X4, member1cC_out_gag(X1, X2, X4)) -> member1cC_out_gag(X1, X2, .(X3, X4)) The set Q consists of the following terms: member1cC_in_gag(x0, x1) U12_gag(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (88) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 2, "program": { "directives": [], "clauses": [ [ "(reach X Y Edges)", "(member (. X (. Y ([]))) Edges)" ], [ "(reach X Z Edges)", "(',' (member1 (. X (. Y ([]))) Edges) (reach Y Z Edges))" ], [ "(member H (. H L))", null ], [ "(member X (. H L))", "(member X L)" ], [ "(member1 H (. H L))", null ], [ "(member1 X (. H L))", "(member1 X L)" ] ] }, "graph": { "nodes": { "290": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T119 (. X106 ([]))) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": ["X106"], "exprvars": [] } }, "270": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T91 T83 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T91" ], "free": [], "exprvars": [] } }, "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [ { "clause": 4, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }, { "clause": 5, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "272": { "goal": [{ "clause": 4, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "274": { "goal": [{ "clause": 5, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "74": { "goal": [{ "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "75": { "goal": [{ "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "264": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "221": { "goal": [ { "clause": 2, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }, { "clause": 3, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "265": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": 2, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "266": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T60 (. T61 ([]))) T63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61", "T63" ], "free": [], "exprvars": [] } }, "288": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "223": { "goal": [{ "clause": 3, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "267": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "289": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member1 (. T82 (. X67 ([]))) T84) (reach X67 T83 T84))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T83", "T84" ], "free": ["X67"], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 74, "label": "PARALLEL" }, { "from": 5, "to": 75, "label": "PARALLEL" }, { "from": 74, "to": 220, "label": "ONLY EVAL with clause\nreach(X21, X22, X23) :- member(.(X21, .(X22, [])), X23).\nand substitutionT1 -> T28,\nX21 -> T28,\nT2 -> T29,\nX22 -> T29,\nT3 -> T30,\nX23 -> T30" }, { "from": 75, "to": 268, "label": "ONLY EVAL with clause\nreach(X64, X65, X66) :- ','(member1(.(X64, .(X67, [])), X66), reach(X67, X65, X66)).\nand substitutionT1 -> T82,\nX64 -> T82,\nT2 -> T83,\nX65 -> T83,\nT3 -> T84,\nX66 -> T84" }, { "from": 220, "to": 221, "label": "CASE" }, { "from": 221, "to": 222, "label": "PARALLEL" }, { "from": 221, "to": 223, "label": "PARALLEL" }, { "from": 222, "to": 263, "label": "EVAL with clause\nmember(X36, .(X36, X37)).\nand substitutionT28 -> T49,\nT29 -> T50,\nX36 -> .(T49, .(T50, [])),\nX37 -> T51,\nT30 -> .(.(T49, .(T50, [])), T51)" }, { "from": 222, "to": 264, "label": "EVAL-BACKTRACK" }, { "from": 223, "to": 266, "label": "EVAL with clause\nmember(X44, .(X45, X46)) :- member(X44, X46).\nand substitutionT28 -> T60,\nT29 -> T61,\nX44 -> .(T60, .(T61, [])),\nX45 -> T62,\nX46 -> T63,\nT30 -> .(T62, T63)" }, { "from": 223, "to": 267, "label": "EVAL-BACKTRACK" }, { "from": 263, "to": 265, "label": "SUCCESS" }, { "from": 266, "to": 220, "label": "INSTANCE with matching:\nT28 -> T60\nT29 -> T61\nT30 -> T63" }, { "from": 268, "to": 269, "label": "SPLIT 1" }, { "from": 268, "to": 270, "label": "SPLIT 2\nnew knowledge:\nT82 is ground\nT91 is ground\nT84 is ground\nreplacements:X67 -> T91" }, { "from": 269, "to": 271, "label": "CASE" }, { "from": 270, "to": 2, "label": "INSTANCE with matching:\nT1 -> T91\nT2 -> T83\nT3 -> T84" }, { "from": 271, "to": 272, "label": "PARALLEL" }, { "from": 271, "to": 274, "label": "PARALLEL" }, { "from": 272, "to": 288, "label": "EVAL with clause\nmember1(X92, .(X92, X93)).\nand substitutionT82 -> T110,\nX67 -> T111,\nX92 -> .(T110, .(T111, [])),\nX94 -> T111,\nX93 -> T112,\nT84 -> .(.(T110, .(T111, [])), T112)" }, { "from": 272, "to": 289, "label": "EVAL-BACKTRACK" }, { "from": 274, "to": 291, "label": "EVAL with clause\nmember1(X103, .(X104, X105)) :- member1(X103, X105).\nand substitutionT82 -> T119,\nX67 -> X106,\nX103 -> .(T119, .(X106, [])),\nX104 -> T120,\nX105 -> T121,\nT84 -> .(T120, T121)" }, { "from": 274, "to": 292, "label": "EVAL-BACKTRACK" }, { "from": 288, "to": 290, "label": "SUCCESS" }, { "from": 291, "to": 269, "label": "INSTANCE with matching:\nT82 -> T119\nX67 -> X106\nT84 -> T121" } ], "type": "Graph" } } ---------------------------------------- (89) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in(T28, T29, T30) -> U1(f220_in(T28, T29, T30), T28, T29, T30) U1(f220_out1, T28, T29, T30) -> f2_out1 f2_in(T82, T83, T84) -> U2(f268_in(T82, T84, T83), T82, T83, T84) U2(f268_out1(X67), T82, T83, T84) -> f2_out1 f220_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f220_out1 f220_in(T60, T61, .(T62, T63)) -> U3(f220_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f220_out1, T60, T61, .(T62, T63)) -> f220_out1 f269_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_out1(T111) f269_in(T119, .(T120, T121)) -> U4(f269_in(T119, T121), T119, .(T120, T121)) U4(f269_out1(X106), T119, .(T120, T121)) -> f269_out1(X106) f268_in(T82, T84, T83) -> U5(f269_in(T82, T84), T82, T84, T83) U5(f269_out1(T91), T82, T84, T83) -> U6(f2_in(T91, T83, T84), T82, T84, T83, T91) U6(f2_out1, T82, T84, T83, T91) -> f268_out1(T91) Q is empty. ---------------------------------------- (90) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T28, T29, T30) -> U1^1(f220_in(T28, T29, T30), T28, T29, T30) F2_IN(T28, T29, T30) -> F220_IN(T28, T29, T30) F2_IN(T82, T83, T84) -> U2^1(f268_in(T82, T84, T83), T82, T83, T84) F2_IN(T82, T83, T84) -> F268_IN(T82, T84, T83) F220_IN(T60, T61, .(T62, T63)) -> U3^1(f220_in(T60, T61, T63), T60, T61, .(T62, T63)) F220_IN(T60, T61, .(T62, T63)) -> F220_IN(T60, T61, T63) F269_IN(T119, .(T120, T121)) -> U4^1(f269_in(T119, T121), T119, .(T120, T121)) F269_IN(T119, .(T120, T121)) -> F269_IN(T119, T121) F268_IN(T82, T84, T83) -> U5^1(f269_in(T82, T84), T82, T84, T83) F268_IN(T82, T84, T83) -> F269_IN(T82, T84) U5^1(f269_out1(T91), T82, T84, T83) -> U6^1(f2_in(T91, T83, T84), T82, T84, T83, T91) U5^1(f269_out1(T91), T82, T84, T83) -> F2_IN(T91, T83, T84) The TRS R consists of the following rules: f2_in(T28, T29, T30) -> U1(f220_in(T28, T29, T30), T28, T29, T30) U1(f220_out1, T28, T29, T30) -> f2_out1 f2_in(T82, T83, T84) -> U2(f268_in(T82, T84, T83), T82, T83, T84) U2(f268_out1(X67), T82, T83, T84) -> f2_out1 f220_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f220_out1 f220_in(T60, T61, .(T62, T63)) -> U3(f220_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f220_out1, T60, T61, .(T62, T63)) -> f220_out1 f269_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_out1(T111) f269_in(T119, .(T120, T121)) -> U4(f269_in(T119, T121), T119, .(T120, T121)) U4(f269_out1(X106), T119, .(T120, T121)) -> f269_out1(X106) f268_in(T82, T84, T83) -> U5(f269_in(T82, T84), T82, T84, T83) U5(f269_out1(T91), T82, T84, T83) -> U6(f2_in(T91, T83, T84), T82, T84, T83, T91) U6(f2_out1, T82, T84, T83, T91) -> f268_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (92) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes. ---------------------------------------- (93) Complex Obligation (AND) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: F269_IN(T119, .(T120, T121)) -> F269_IN(T119, T121) The TRS R consists of the following rules: f2_in(T28, T29, T30) -> U1(f220_in(T28, T29, T30), T28, T29, T30) U1(f220_out1, T28, T29, T30) -> f2_out1 f2_in(T82, T83, T84) -> U2(f268_in(T82, T84, T83), T82, T83, T84) U2(f268_out1(X67), T82, T83, T84) -> f2_out1 f220_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f220_out1 f220_in(T60, T61, .(T62, T63)) -> U3(f220_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f220_out1, T60, T61, .(T62, T63)) -> f220_out1 f269_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_out1(T111) f269_in(T119, .(T120, T121)) -> U4(f269_in(T119, T121), T119, .(T120, T121)) U4(f269_out1(X106), T119, .(T120, T121)) -> f269_out1(X106) f268_in(T82, T84, T83) -> U5(f269_in(T82, T84), T82, T84, T83) U5(f269_out1(T91), T82, T84, T83) -> U6(f2_in(T91, T83, T84), T82, T84, T83, T91) U6(f2_out1, T82, T84, T83, T91) -> f268_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: F269_IN(T119, .(T120, T121)) -> F269_IN(T119, T121) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) 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: *F269_IN(T119, .(T120, T121)) -> F269_IN(T119, T121) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (98) YES ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: F220_IN(T60, T61, .(T62, T63)) -> F220_IN(T60, T61, T63) The TRS R consists of the following rules: f2_in(T28, T29, T30) -> U1(f220_in(T28, T29, T30), T28, T29, T30) U1(f220_out1, T28, T29, T30) -> f2_out1 f2_in(T82, T83, T84) -> U2(f268_in(T82, T84, T83), T82, T83, T84) U2(f268_out1(X67), T82, T83, T84) -> f2_out1 f220_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f220_out1 f220_in(T60, T61, .(T62, T63)) -> U3(f220_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f220_out1, T60, T61, .(T62, T63)) -> f220_out1 f269_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_out1(T111) f269_in(T119, .(T120, T121)) -> U4(f269_in(T119, T121), T119, .(T120, T121)) U4(f269_out1(X106), T119, .(T120, T121)) -> f269_out1(X106) f268_in(T82, T84, T83) -> U5(f269_in(T82, T84), T82, T84, T83) U5(f269_out1(T91), T82, T84, T83) -> U6(f2_in(T91, T83, T84), T82, T84, T83, T91) U6(f2_out1, T82, T84, T83, T91) -> f268_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: F220_IN(T60, T61, .(T62, T63)) -> F220_IN(T60, T61, T63) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) 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: *F220_IN(T60, T61, .(T62, T63)) -> F220_IN(T60, T61, T63) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (103) YES ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T82, T83, T84) -> F268_IN(T82, T84, T83) F268_IN(T82, T84, T83) -> U5^1(f269_in(T82, T84), T82, T84, T83) U5^1(f269_out1(T91), T82, T84, T83) -> F2_IN(T91, T83, T84) The TRS R consists of the following rules: f2_in(T28, T29, T30) -> U1(f220_in(T28, T29, T30), T28, T29, T30) U1(f220_out1, T28, T29, T30) -> f2_out1 f2_in(T82, T83, T84) -> U2(f268_in(T82, T84, T83), T82, T83, T84) U2(f268_out1(X67), T82, T83, T84) -> f2_out1 f220_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f220_out1 f220_in(T60, T61, .(T62, T63)) -> U3(f220_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f220_out1, T60, T61, .(T62, T63)) -> f220_out1 f269_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_out1(T111) f269_in(T119, .(T120, T121)) -> U4(f269_in(T119, T121), T119, .(T120, T121)) U4(f269_out1(X106), T119, .(T120, T121)) -> f269_out1(X106) f268_in(T82, T84, T83) -> U5(f269_in(T82, T84), T82, T84, T83) U5(f269_out1(T91), T82, T84, T83) -> U6(f2_in(T91, T83, T84), T82, T84, T83, T91) U6(f2_out1, T82, T84, T83, T91) -> f268_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (105) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = F268_IN(T82, .(.(T82, .(T111, [])), T112), T83) evaluates to t =F268_IN(T111, .(.(T82, .(T111, [])), T112), T83) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [T111 / T82] -------------------------------------------------------------------------------- Rewriting sequence F268_IN(T82, .(.(T82, .(T82, [])), T112), T83) -> U5^1(f269_in(T82, .(.(T82, .(T82, [])), T112)), T82, .(.(T82, .(T82, [])), T112), T83) with rule F268_IN(T82', T84, T83') -> U5^1(f269_in(T82', T84), T82', T84, T83') at position [] and matcher [T82' / T82, T84 / .(.(T82, .(T82, [])), T112), T83' / T83] U5^1(f269_in(T82, .(.(T82, .(T82, [])), T112)), T82, .(.(T82, .(T82, [])), T112), T83) -> U5^1(f269_out1(T82), T82, .(.(T82, .(T82, [])), T112), T83) with rule f269_in(T110, .(.(T110, .(T111, [])), T112')) -> f269_out1(T111) at position [0] and matcher [T110 / T82, T111 / T82, T112' / T112] U5^1(f269_out1(T82), T82, .(.(T82, .(T82, [])), T112), T83) -> F2_IN(T82, T83, .(.(T82, .(T82, [])), T112)) with rule U5^1(f269_out1(T91), T82', T84', T83') -> F2_IN(T91, T83', T84') at position [] and matcher [T91 / T82, T82' / T82, T84' / .(.(T82, .(T82, [])), T112), T83' / T83] F2_IN(T82, T83, .(.(T82, .(T82, [])), T112)) -> F268_IN(T82, .(.(T82, .(T82, [])), T112), T83) with rule F2_IN(T82, T83, T84) -> F268_IN(T82, T84, T83) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (106) NO ---------------------------------------- (107) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(reach X Y Edges)", "(member (. X (. Y ([]))) Edges)" ], [ "(reach X Z Edges)", "(',' (member1 (. X (. Y ([]))) Edges) (reach Y Z Edges))" ], [ "(member H (. H L))", null ], [ "(member X (. H L))", "(member X L)" ], [ "(member1 H (. H L))", null ], [ "(member1 X (. H L))", "(member1 X L)" ] ] }, "graph": { "nodes": { "type": "Nodes", "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "252": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T91 T83 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T91" ], "free": [], "exprvars": [] } }, "253": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "254": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "255": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T119 (. X106 ([]))) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": ["X106"], "exprvars": [] } }, "256": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "237": { "goal": [ { "clause": 4, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }, { "clause": 5, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "117": { "goal": [ { "clause": 2, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }, { "clause": 3, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "120": { "goal": [{ "clause": 2, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": 3, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "124": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "125": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T60 (. T61 ([]))) T63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61", "T63" ], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member1 (. T82 (. X67 ([]))) T84) (reach X67 T83 T84))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T83", "T84" ], "free": ["X67"], "exprvars": [] } }, "126": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "247": { "goal": [{ "clause": 4, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "248": { "goal": [{ "clause": 5, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "40": { "goal": [{ "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 38, "label": "PARALLEL" }, { "from": 6, "to": 40, "label": "PARALLEL" }, { "from": 38, "to": 42, "label": "ONLY EVAL with clause\nreach(X21, X22, X23) :- member(.(X21, .(X22, [])), X23).\nand substitutionT1 -> T28,\nX21 -> T28,\nT2 -> T29,\nX22 -> T29,\nT3 -> T30,\nX23 -> T30" }, { "from": 40, "to": 224, "label": "ONLY EVAL with clause\nreach(X64, X65, X66) :- ','(member1(.(X64, .(X67, [])), X66), reach(X67, X65, X66)).\nand substitutionT1 -> T82,\nX64 -> T82,\nT2 -> T83,\nX65 -> T83,\nT3 -> T84,\nX66 -> T84" }, { "from": 42, "to": 117, "label": "CASE" }, { "from": 117, "to": 120, "label": "PARALLEL" }, { "from": 117, "to": 121, "label": "PARALLEL" }, { "from": 120, "to": 122, "label": "EVAL with clause\nmember(X36, .(X36, X37)).\nand substitutionT28 -> T49,\nT29 -> T50,\nX36 -> .(T49, .(T50, [])),\nX37 -> T51,\nT30 -> .(.(T49, .(T50, [])), T51)" }, { "from": 120, "to": 123, "label": "EVAL-BACKTRACK" }, { "from": 121, "to": 125, "label": "EVAL with clause\nmember(X44, .(X45, X46)) :- member(X44, X46).\nand substitutionT28 -> T60,\nT29 -> T61,\nX44 -> .(T60, .(T61, [])),\nX45 -> T62,\nX46 -> T63,\nT30 -> .(T62, T63)" }, { "from": 121, "to": 126, "label": "EVAL-BACKTRACK" }, { "from": 122, "to": 124, "label": "SUCCESS" }, { "from": 125, "to": 42, "label": "INSTANCE with matching:\nT28 -> T60\nT29 -> T61\nT30 -> T63" }, { "from": 224, "to": 230, "label": "SPLIT 1" }, { "from": 224, "to": 231, "label": "SPLIT 2\nnew knowledge:\nT82 is ground\nT91 is ground\nT84 is ground\nreplacements:X67 -> T91" }, { "from": 230, "to": 237, "label": "CASE" }, { "from": 231, "to": 3, "label": "INSTANCE with matching:\nT1 -> T91\nT2 -> T83\nT3 -> T84" }, { "from": 237, "to": 247, "label": "PARALLEL" }, { "from": 237, "to": 248, "label": "PARALLEL" }, { "from": 247, "to": 252, "label": "EVAL with clause\nmember1(X92, .(X92, X93)).\nand substitutionT82 -> T110,\nX67 -> T111,\nX92 -> .(T110, .(T111, [])),\nX94 -> T111,\nX93 -> T112,\nT84 -> .(.(T110, .(T111, [])), T112)" }, { "from": 247, "to": 253, "label": "EVAL-BACKTRACK" }, { "from": 248, "to": 255, "label": "EVAL with clause\nmember1(X103, .(X104, X105)) :- member1(X103, X105).\nand substitutionT82 -> T119,\nX67 -> X106,\nX103 -> .(T119, .(X106, [])),\nX104 -> T120,\nX105 -> T121,\nT84 -> .(T120, T121)" }, { "from": 248, "to": 256, "label": "EVAL-BACKTRACK" }, { "from": 252, "to": 254, "label": "SUCCESS" }, { "from": 255, "to": 230, "label": "INSTANCE with matching:\nT82 -> T119\nX67 -> X106\nT84 -> T121" } ], "type": "Graph" } } ---------------------------------------- (108) Complex Obligation (AND) ---------------------------------------- (109) Obligation: Rules: f256_out -> f248_out(T82, T84) :|: TRUE f248_in(T119, .(T120, T121)) -> f255_in(T119, T121) :|: TRUE f255_out(x, x1) -> f248_out(x, .(x2, x1)) :|: TRUE f248_in(x3, x4) -> f256_in :|: TRUE f230_in(x5, x6) -> f237_in(x5, x6) :|: TRUE f237_out(x7, x8) -> f230_out(x7, x8) :|: TRUE f255_in(x9, x10) -> f230_in(x9, x10) :|: TRUE f230_out(x11, x12) -> f255_out(x11, x12) :|: TRUE f237_in(x13, x14) -> f248_in(x13, x14) :|: TRUE f247_out(x15, x16) -> f237_out(x15, x16) :|: TRUE f248_out(x17, x18) -> f237_out(x17, x18) :|: TRUE f237_in(x19, x20) -> f247_in(x19, x20) :|: TRUE f6_out(T1, T2, T3) -> f3_out(T1, T2, T3) :|: TRUE f3_in(x21, x22, x23) -> f6_in(x21, x22, x23) :|: TRUE f6_in(x24, x25, x26) -> f38_in(x24, x25, x26) :|: TRUE f40_out(x27, x28, x29) -> f6_out(x27, x28, x29) :|: TRUE f38_out(x30, x31, x32) -> f6_out(x30, x31, x32) :|: TRUE f6_in(x33, x34, x35) -> f40_in(x33, x34, x35) :|: TRUE f40_in(x36, x37, x38) -> f224_in(x36, x38, x37) :|: TRUE f224_out(x39, x40, x41) -> f40_out(x39, x41, x40) :|: TRUE f224_in(x42, x43, x44) -> f230_in(x42, x43) :|: TRUE f230_out(x45, x46) -> f231_in(x47, x48, x46) :|: TRUE f231_out(x49, x50, x51) -> f224_out(x52, x51, x50) :|: TRUE Start term: f3_in(T1, T2, T3) ---------------------------------------- (110) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f248_in(T119, .(T120, T121)) -> f255_in(T119, T121) :|: TRUE f230_in(x5, x6) -> f237_in(x5, x6) :|: TRUE f255_in(x9, x10) -> f230_in(x9, x10) :|: TRUE f237_in(x13, x14) -> f248_in(x13, x14) :|: TRUE ---------------------------------------- (111) Obligation: Rules: f248_in(T119, .(T120, T121)) -> f255_in(T119, T121) :|: TRUE f230_in(x5, x6) -> f237_in(x5, x6) :|: TRUE f255_in(x9, x10) -> f230_in(x9, x10) :|: TRUE f237_in(x13, x14) -> f248_in(x13, x14) :|: TRUE ---------------------------------------- (112) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (113) Obligation: Rules: f248_in(T119:0, .(T120:0, T121:0)) -> f248_in(T119:0, T121:0) :|: TRUE ---------------------------------------- (114) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (115) Obligation: Rules: f248_in(T119:0, .(T120:0, T121:0)) -> f248_in(T119:0, T121:0) :|: TRUE ---------------------------------------- (116) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f248_in(T119:0, .(T120:0, T121:0)) -> f248_in(T119:0, T121:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (117) Obligation: Termination digraph: Nodes: (1) f248_in(T119:0, .(T120:0, T121:0)) -> f248_in(T119:0, T121:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (118) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f248_in(x1, x2) -> f248_in(x2) .(x1, x2) -> .(x2) ---------------------------------------- (119) Obligation: Rules: f248_in(.(T121:0)) -> f248_in(T121:0) :|: TRUE ---------------------------------------- (120) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f248_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (121) Obligation: Rules: f248_in(.(T121:0)) -> f248_in(T121:0) ---------------------------------------- (122) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (123) Obligation: Q DP problem: The TRS P consists of the following rules: f248_in(.(T121:0)) -> f248_in(T121:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (124) 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: *f248_in(.(T121:0)) -> f248_in(T121:0) The graph contains the following edges 1 > 1 ---------------------------------------- (125) YES ---------------------------------------- (126) Obligation: Rules: f125_in(T60, T61, T63) -> f42_in(T60, T61, T63) :|: TRUE f42_out(x, x1, x2) -> f125_out(x, x1, x2) :|: TRUE f42_in(T28, T29, T30) -> f117_in(T28, T29, T30) :|: TRUE f117_out(x3, x4, x5) -> f42_out(x3, x4, x5) :|: TRUE f117_in(x6, x7, x8) -> f120_in(x6, x7, x8) :|: TRUE f120_out(x9, x10, x11) -> f117_out(x9, x10, x11) :|: TRUE f117_in(x12, x13, x14) -> f121_in(x12, x13, x14) :|: TRUE f121_out(x15, x16, x17) -> f117_out(x15, x16, x17) :|: TRUE f125_out(x18, x19, x20) -> f121_out(x18, x19, .(x21, x20)) :|: TRUE f121_in(x22, x23, .(x24, x25)) -> f125_in(x22, x23, x25) :|: TRUE f121_in(x26, x27, x28) -> f126_in :|: TRUE f126_out -> f121_out(x29, x30, x31) :|: TRUE f6_out(T1, T2, T3) -> f3_out(T1, T2, T3) :|: TRUE f3_in(x32, x33, x34) -> f6_in(x32, x33, x34) :|: TRUE f6_in(x35, x36, x37) -> f38_in(x35, x36, x37) :|: TRUE f40_out(x38, x39, x40) -> f6_out(x38, x39, x40) :|: TRUE f38_out(x41, x42, x43) -> f6_out(x41, x42, x43) :|: TRUE f6_in(x44, x45, x46) -> f40_in(x44, x45, x46) :|: TRUE f38_in(x47, x48, x49) -> f42_in(x47, x48, x49) :|: TRUE f42_out(x50, x51, x52) -> f38_out(x50, x51, x52) :|: TRUE Start term: f3_in(T1, T2, T3) ---------------------------------------- (127) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f125_in(T60, T61, T63) -> f42_in(T60, T61, T63) :|: TRUE f42_in(T28, T29, T30) -> f117_in(T28, T29, T30) :|: TRUE f117_in(x12, x13, x14) -> f121_in(x12, x13, x14) :|: TRUE f121_in(x22, x23, .(x24, x25)) -> f125_in(x22, x23, x25) :|: TRUE ---------------------------------------- (128) Obligation: Rules: f125_in(T60, T61, T63) -> f42_in(T60, T61, T63) :|: TRUE f42_in(T28, T29, T30) -> f117_in(T28, T29, T30) :|: TRUE f117_in(x12, x13, x14) -> f121_in(x12, x13, x14) :|: TRUE f121_in(x22, x23, .(x24, x25)) -> f125_in(x22, x23, x25) :|: TRUE ---------------------------------------- (129) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (130) Obligation: Rules: f125_in(T60:0, T61:0, .(x24:0, x25:0)) -> f125_in(T60:0, T61:0, x25:0) :|: TRUE ---------------------------------------- (131) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (132) Obligation: Rules: f125_in(T60:0, T61:0, .(x24:0, x25:0)) -> f125_in(T60:0, T61:0, x25:0) :|: TRUE ---------------------------------------- (133) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f125_in(T60:0, T61:0, .(x24:0, x25:0)) -> f125_in(T60:0, T61:0, x25:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (134) Obligation: Termination digraph: Nodes: (1) f125_in(T60:0, T61:0, .(x24:0, x25:0)) -> f125_in(T60:0, T61:0, x25:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (135) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f125_in(x1, x2, x3) -> f125_in(x3) .(x1, x2) -> .(x2) ---------------------------------------- (136) Obligation: Rules: f125_in(.(x25:0)) -> f125_in(x25:0) :|: TRUE ---------------------------------------- (137) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f125_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (138) Obligation: Rules: f125_in(.(x25:0)) -> f125_in(x25:0) ---------------------------------------- (139) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (140) Obligation: Q DP problem: The TRS P consists of the following rules: f125_in(.(x25:0)) -> f125_in(x25:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (141) 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: *f125_in(.(x25:0)) -> f125_in(x25:0) The graph contains the following edges 1 > 1 ---------------------------------------- (142) YES ---------------------------------------- (143) Obligation: Rules: f255_in(T119, T121) -> f230_in(T119, T121) :|: TRUE f230_out(x, x1) -> f255_out(x, x1) :|: TRUE f224_in(T82, T84, T83) -> f230_in(T82, T84) :|: TRUE f230_out(x2, x3) -> f231_in(x4, x5, x3) :|: TRUE f231_out(x6, x7, x8) -> f224_out(x9, x8, x7) :|: TRUE f40_in(x10, x11, x12) -> f224_in(x10, x12, x11) :|: TRUE f224_out(x13, x14, x15) -> f40_out(x13, x15, x14) :|: TRUE f6_out(T1, T2, T3) -> f3_out(T1, T2, T3) :|: TRUE f3_in(x16, x17, x18) -> f6_in(x16, x17, x18) :|: TRUE f3_out(x19, x20, x21) -> f231_out(x19, x20, x21) :|: TRUE f231_in(x22, x23, x24) -> f3_in(x22, x23, x24) :|: TRUE f230_in(x25, x26) -> f237_in(x25, x26) :|: TRUE f237_out(x27, x28) -> f230_out(x27, x28) :|: TRUE f256_out -> f248_out(x29, x30) :|: TRUE f248_in(x31, .(x32, x33)) -> f255_in(x31, x33) :|: TRUE f255_out(x34, x35) -> f248_out(x34, .(x36, x35)) :|: TRUE f248_in(x37, x38) -> f256_in :|: TRUE f247_in(T110, .(.(T110, .(T111, [])), T112)) -> f252_in :|: TRUE f247_in(x39, x40) -> f253_in :|: TRUE f253_out -> f247_out(x41, x42) :|: TRUE f252_out -> f247_out(x43, .(.(x43, .(x44, [])), x45)) :|: TRUE f237_in(x46, x47) -> f248_in(x46, x47) :|: TRUE f247_out(x48, x49) -> f237_out(x48, x49) :|: TRUE f248_out(x50, x51) -> f237_out(x50, x51) :|: TRUE f237_in(x52, x53) -> f247_in(x52, x53) :|: TRUE f252_in -> f252_out :|: TRUE f6_in(x54, x55, x56) -> f38_in(x54, x55, x56) :|: TRUE f40_out(x57, x58, x59) -> f6_out(x57, x58, x59) :|: TRUE f38_out(x60, x61, x62) -> f6_out(x60, x61, x62) :|: TRUE f6_in(x63, x64, x65) -> f40_in(x63, x64, x65) :|: TRUE Start term: f3_in(T1, T2, T3) ---------------------------------------- (144) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f255_in(T119, T121) -> f230_in(T119, T121) :|: TRUE f230_out(x, x1) -> f255_out(x, x1) :|: TRUE f224_in(T82, T84, T83) -> f230_in(T82, T84) :|: TRUE f230_out(x2, x3) -> f231_in(x4, x5, x3) :|: TRUE f40_in(x10, x11, x12) -> f224_in(x10, x12, x11) :|: TRUE f3_in(x16, x17, x18) -> f6_in(x16, x17, x18) :|: TRUE f231_in(x22, x23, x24) -> f3_in(x22, x23, x24) :|: TRUE f230_in(x25, x26) -> f237_in(x25, x26) :|: TRUE f237_out(x27, x28) -> f230_out(x27, x28) :|: TRUE f248_in(x31, .(x32, x33)) -> f255_in(x31, x33) :|: TRUE f255_out(x34, x35) -> f248_out(x34, .(x36, x35)) :|: TRUE f247_in(T110, .(.(T110, .(T111, [])), T112)) -> f252_in :|: TRUE f252_out -> f247_out(x43, .(.(x43, .(x44, [])), x45)) :|: TRUE f237_in(x46, x47) -> f248_in(x46, x47) :|: TRUE f247_out(x48, x49) -> f237_out(x48, x49) :|: TRUE f248_out(x50, x51) -> f237_out(x50, x51) :|: TRUE f237_in(x52, x53) -> f247_in(x52, x53) :|: TRUE f252_in -> f252_out :|: TRUE f6_in(x63, x64, x65) -> f40_in(x63, x64, x65) :|: TRUE ---------------------------------------- (145) Obligation: Rules: f255_in(T119, T121) -> f230_in(T119, T121) :|: TRUE f230_out(x, x1) -> f255_out(x, x1) :|: TRUE f224_in(T82, T84, T83) -> f230_in(T82, T84) :|: TRUE f230_out(x2, x3) -> f231_in(x4, x5, x3) :|: TRUE f40_in(x10, x11, x12) -> f224_in(x10, x12, x11) :|: TRUE f3_in(x16, x17, x18) -> f6_in(x16, x17, x18) :|: TRUE f231_in(x22, x23, x24) -> f3_in(x22, x23, x24) :|: TRUE f230_in(x25, x26) -> f237_in(x25, x26) :|: TRUE f237_out(x27, x28) -> f230_out(x27, x28) :|: TRUE f248_in(x31, .(x32, x33)) -> f255_in(x31, x33) :|: TRUE f255_out(x34, x35) -> f248_out(x34, .(x36, x35)) :|: TRUE f247_in(T110, .(.(T110, .(T111, [])), T112)) -> f252_in :|: TRUE f252_out -> f247_out(x43, .(.(x43, .(x44, [])), x45)) :|: TRUE f237_in(x46, x47) -> f248_in(x46, x47) :|: TRUE f247_out(x48, x49) -> f237_out(x48, x49) :|: TRUE f248_out(x50, x51) -> f237_out(x50, x51) :|: TRUE f237_in(x52, x53) -> f247_in(x52, x53) :|: TRUE f252_in -> f252_out :|: TRUE f6_in(x63, x64, x65) -> f40_in(x63, x64, x65) :|: TRUE ---------------------------------------- (146) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (147) Obligation: Rules: f237_out(x27:0, x28:0) -> f237_out(x27:0, .(x36:0, x28:0)) :|: TRUE f237_out(x, x1) -> f237_in(x2, x1) :|: TRUE f237_in(x52:0, .(.(x52:0, .(T111:0, [])), T112:0)) -> f237_out(x43:0, .(.(x43:0, .(x44:0, [])), x45:0)) :|: TRUE f237_in(x46:0, .(x32:0, x33:0)) -> f237_in(x46:0, x33:0) :|: TRUE ---------------------------------------- (148) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (149) Obligation: Rules: f237_out(x27:0, x28:0) -> f237_out(x27:0, .(x36:0, x28:0)) :|: TRUE f237_out(x, x1) -> f237_in(x2, x1) :|: TRUE f237_in(x52:0, .(.(x52:0, .(T111:0, [])), T112:0)) -> f237_out(x43:0, .(.(x43:0, .(x44:0, [])), x45:0)) :|: TRUE f237_in(x46:0, .(x32:0, x33:0)) -> f237_in(x46:0, x33:0) :|: TRUE ---------------------------------------- (150) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f237_out(x27:0, x28:0) -> f237_out(x27:0, .(x36:0, x28:0)) :|: TRUE (2) f237_out(x, x1) -> f237_in(x2, x1) :|: TRUE (3) f237_in(x52:0, .(.(x52:0, .(T111:0, [])), T112:0)) -> f237_out(x43:0, .(.(x43:0, .(x44:0, [])), x45:0)) :|: TRUE (4) f237_in(x46:0, .(x32:0, x33:0)) -> f237_in(x46:0, x33:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (3), (4) (3) -> (1), (2) (4) -> (3), (4) This digraph is fully evaluated! ---------------------------------------- (151) Obligation: Termination digraph: Nodes: (1) f237_out(x27:0, x28:0) -> f237_out(x27:0, .(x36:0, x28:0)) :|: TRUE (2) f237_in(x52:0, .(.(x52:0, .(T111:0, [])), T112:0)) -> f237_out(x43:0, .(.(x43:0, .(x44:0, [])), x45:0)) :|: TRUE (3) f237_in(x46:0, .(x32:0, x33:0)) -> f237_in(x46:0, x33:0) :|: TRUE (4) f237_out(x, x1) -> f237_in(x2, x1) :|: TRUE Arcs: (1) -> (1), (4) (2) -> (1), (4) (3) -> (2), (3) (4) -> (2), (3) This digraph is fully evaluated!