/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [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, 0 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) PrologToTRSTransformerProof [SOUND, 0 ms] (64) QTRS (65) DependencyPairsProof [EQUIVALENT, 0 ms] (66) QDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) AND (69) QDP (70) UsableRulesProof [EQUIVALENT, 0 ms] (71) QDP (72) QDPSizeChangeProof [EQUIVALENT, 0 ms] (73) YES (74) QDP (75) UsableRulesProof [EQUIVALENT, 0 ms] (76) QDP (77) QDPSizeChangeProof [EQUIVALENT, 0 ms] (78) YES (79) QDP (80) NonTerminationLoopProof [COMPLETE, 707 ms] (81) NO (82) PrologToDTProblemTransformerProof [SOUND, 0 ms] (83) TRIPLES (84) TriplesToPiDPProof [SOUND, 0 ms] (85) PiDP (86) DependencyGraphProof [EQUIVALENT, 0 ms] (87) AND (88) PiDP (89) UsableRulesProof [EQUIVALENT, 0 ms] (90) PiDP (91) PiDPToQDPProof [SOUND, 0 ms] (92) QDP (93) QDPSizeChangeProof [EQUIVALENT, 0 ms] (94) YES (95) PiDP (96) UsableRulesProof [EQUIVALENT, 0 ms] (97) PiDP (98) PiDPToQDPProof [EQUIVALENT, 0 ms] (99) QDP (100) QDPSizeChangeProof [EQUIVALENT, 0 ms] (101) YES (102) PiDP (103) PiDPToQDPProof [SOUND, 0 ms] (104) QDP (105) TransformationProof [SOUND, 0 ms] (106) QDP (107) TransformationProof [EQUIVALENT, 0 ms] (108) QDP (109) PrologToIRSwTTransformerProof [SOUND, 47 ms] (110) AND (111) IRSwT (112) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (113) IRSwT (114) IntTRSCompressionProof [EQUIVALENT, 24 ms] (115) IRSwT (116) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (117) IRSwT (118) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (119) IRSwT (120) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (121) IRSwT (122) TempFilterProof [SOUND, 1 ms] (123) IRSwT (124) IRSwTToQDPProof [SOUND, 0 ms] (125) QDP (126) QDPSizeChangeProof [EQUIVALENT, 0 ms] (127) YES (128) IRSwT (129) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (130) IRSwT (131) IntTRSCompressionProof [EQUIVALENT, 2 ms] (132) IRSwT (133) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (134) IRSwT (135) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (136) IRSwT (137) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (138) IRSwT (139) TempFilterProof [SOUND, 1 ms] (140) IRSwT (141) IRSwTToQDPProof [SOUND, 1 ms] (142) QDP (143) QDPSizeChangeProof [EQUIVALENT, 0 ms] (144) YES (145) IRSwT (146) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (147) IRSwT (148) IntTRSCompressionProof [EQUIVALENT, 13 ms] (149) IRSwT (150) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (151) IRSwT (152) IRSwTTerminationDigraphProof [EQUIVALENT, 14 ms] (153) IRSwT (154) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (155) 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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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, 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 ---------------------------------------- (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(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. ---------------------------------------- (26) 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)))) ---------------------------------------- (27) 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. ---------------------------------------- (28) 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))) ---------------------------------------- (29) 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. ---------------------------------------- (30) 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)))) ---------------------------------------- (31) 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. ---------------------------------------- (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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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) 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 ---------------------------------------- (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(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. ---------------------------------------- (57) 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)))) ---------------------------------------- (58) 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. ---------------------------------------- (59) 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))) ---------------------------------------- (60) 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. ---------------------------------------- (61) 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, []))))) ---------------------------------------- (62) 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. ---------------------------------------- (63) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "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": { "27": { "goal": [{ "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "29": { "goal": [{ "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "290": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "293": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T119 (. X106 ([]))) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": ["X106"], "exprvars": [] } }, "195": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "294": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "196": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "179": { "goal": [{ "clause": 2, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "99": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "181": { "goal": [{ "clause": 3, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "284": { "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": [] } }, "285": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T91 T83 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T91" ], "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": [ { "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": [] } }, "288": { "goal": [{ "clause": 4, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "3": { "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": [] } }, "289": { "goal": [{ "clause": 5, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "147": { "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": [] } }, "205": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T60 (. T61 ([]))) T63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61", "T63" ], "free": [], "exprvars": [] } }, "206": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 27, "label": "PARALLEL" }, { "from": 3, "to": 29, "label": "PARALLEL" }, { "from": 27, "to": 99, "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": 29, "to": 284, "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": 99, "to": 147, "label": "CASE" }, { "from": 147, "to": 179, "label": "PARALLEL" }, { "from": 147, "to": 181, "label": "PARALLEL" }, { "from": 179, "to": 195, "label": "EVAL with clause\nmember(X36, .(X36, X37)).\nand substitutionT28 -> T49,\nT29 -> T50,\nX36 -> .(T49, .(T50, [])),\nX37 -> T51,\nT30 -> .(.(T49, .(T50, [])), T51)" }, { "from": 179, "to": 196, "label": "EVAL-BACKTRACK" }, { "from": 181, "to": 205, "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": 181, "to": 206, "label": "EVAL-BACKTRACK" }, { "from": 195, "to": 199, "label": "SUCCESS" }, { "from": 205, "to": 99, "label": "INSTANCE with matching:\nT28 -> T60\nT29 -> T61\nT30 -> T63" }, { "from": 284, "to": 285, "label": "SPLIT 1" }, { "from": 284, "to": 286, "label": "SPLIT 2\nnew knowledge:\nT82 is ground\nT91 is ground\nT84 is ground\nreplacements:X67 -> T91" }, { "from": 285, "to": 287, "label": "CASE" }, { "from": 286, "to": 1, "label": "INSTANCE with matching:\nT1 -> T91\nT2 -> T83\nT3 -> T84" }, { "from": 287, "to": 288, "label": "PARALLEL" }, { "from": 287, "to": 289, "label": "PARALLEL" }, { "from": 288, "to": 290, "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": 288, "to": 291, "label": "EVAL-BACKTRACK" }, { "from": 289, "to": 293, "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": 289, "to": 294, "label": "EVAL-BACKTRACK" }, { "from": 290, "to": 292, "label": "SUCCESS" }, { "from": 293, "to": 285, "label": "INSTANCE with matching:\nT82 -> T119\nX67 -> X106\nT84 -> T121" } ], "type": "Graph" } } ---------------------------------------- (64) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T28, T29, T30) -> U1(f99_in(T28, T29, T30), T28, T29, T30) U1(f99_out1, T28, T29, T30) -> f1_out1 f1_in(T82, T83, T84) -> U2(f284_in(T82, T84, T83), T82, T83, T84) U2(f284_out1(X67), T82, T83, T84) -> f1_out1 f99_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f99_out1 f99_in(T60, T61, .(T62, T63)) -> U3(f99_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f99_out1, T60, T61, .(T62, T63)) -> f99_out1 f285_in(T110, .(.(T110, .(T111, [])), T112)) -> f285_out1(T111) f285_in(T119, .(T120, T121)) -> U4(f285_in(T119, T121), T119, .(T120, T121)) U4(f285_out1(X106), T119, .(T120, T121)) -> f285_out1(X106) f284_in(T82, T84, T83) -> U5(f285_in(T82, T84), T82, T84, T83) U5(f285_out1(T91), T82, T84, T83) -> U6(f1_in(T91, T83, T84), T82, T84, T83, T91) U6(f1_out1, T82, T84, T83, T91) -> f284_out1(T91) Q is empty. ---------------------------------------- (65) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T28, T29, T30) -> U1^1(f99_in(T28, T29, T30), T28, T29, T30) F1_IN(T28, T29, T30) -> F99_IN(T28, T29, T30) F1_IN(T82, T83, T84) -> U2^1(f284_in(T82, T84, T83), T82, T83, T84) F1_IN(T82, T83, T84) -> F284_IN(T82, T84, T83) F99_IN(T60, T61, .(T62, T63)) -> U3^1(f99_in(T60, T61, T63), T60, T61, .(T62, T63)) F99_IN(T60, T61, .(T62, T63)) -> F99_IN(T60, T61, T63) F285_IN(T119, .(T120, T121)) -> U4^1(f285_in(T119, T121), T119, .(T120, T121)) F285_IN(T119, .(T120, T121)) -> F285_IN(T119, T121) F284_IN(T82, T84, T83) -> U5^1(f285_in(T82, T84), T82, T84, T83) F284_IN(T82, T84, T83) -> F285_IN(T82, T84) U5^1(f285_out1(T91), T82, T84, T83) -> U6^1(f1_in(T91, T83, T84), T82, T84, T83, T91) U5^1(f285_out1(T91), T82, T84, T83) -> F1_IN(T91, T83, T84) The TRS R consists of the following rules: f1_in(T28, T29, T30) -> U1(f99_in(T28, T29, T30), T28, T29, T30) U1(f99_out1, T28, T29, T30) -> f1_out1 f1_in(T82, T83, T84) -> U2(f284_in(T82, T84, T83), T82, T83, T84) U2(f284_out1(X67), T82, T83, T84) -> f1_out1 f99_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f99_out1 f99_in(T60, T61, .(T62, T63)) -> U3(f99_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f99_out1, T60, T61, .(T62, T63)) -> f99_out1 f285_in(T110, .(.(T110, .(T111, [])), T112)) -> f285_out1(T111) f285_in(T119, .(T120, T121)) -> U4(f285_in(T119, T121), T119, .(T120, T121)) U4(f285_out1(X106), T119, .(T120, T121)) -> f285_out1(X106) f284_in(T82, T84, T83) -> U5(f285_in(T82, T84), T82, T84, T83) U5(f285_out1(T91), T82, T84, T83) -> U6(f1_in(T91, T83, T84), T82, T84, T83, T91) U6(f1_out1, T82, T84, T83, T91) -> f284_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes. ---------------------------------------- (68) Complex Obligation (AND) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: F285_IN(T119, .(T120, T121)) -> F285_IN(T119, T121) The TRS R consists of the following rules: f1_in(T28, T29, T30) -> U1(f99_in(T28, T29, T30), T28, T29, T30) U1(f99_out1, T28, T29, T30) -> f1_out1 f1_in(T82, T83, T84) -> U2(f284_in(T82, T84, T83), T82, T83, T84) U2(f284_out1(X67), T82, T83, T84) -> f1_out1 f99_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f99_out1 f99_in(T60, T61, .(T62, T63)) -> U3(f99_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f99_out1, T60, T61, .(T62, T63)) -> f99_out1 f285_in(T110, .(.(T110, .(T111, [])), T112)) -> f285_out1(T111) f285_in(T119, .(T120, T121)) -> U4(f285_in(T119, T121), T119, .(T120, T121)) U4(f285_out1(X106), T119, .(T120, T121)) -> f285_out1(X106) f284_in(T82, T84, T83) -> U5(f285_in(T82, T84), T82, T84, T83) U5(f285_out1(T91), T82, T84, T83) -> U6(f1_in(T91, T83, T84), T82, T84, T83, T91) U6(f1_out1, T82, T84, T83, T91) -> f284_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) 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. ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: F285_IN(T119, .(T120, T121)) -> F285_IN(T119, T121) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) 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: *F285_IN(T119, .(T120, T121)) -> F285_IN(T119, T121) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (73) YES ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: F99_IN(T60, T61, .(T62, T63)) -> F99_IN(T60, T61, T63) The TRS R consists of the following rules: f1_in(T28, T29, T30) -> U1(f99_in(T28, T29, T30), T28, T29, T30) U1(f99_out1, T28, T29, T30) -> f1_out1 f1_in(T82, T83, T84) -> U2(f284_in(T82, T84, T83), T82, T83, T84) U2(f284_out1(X67), T82, T83, T84) -> f1_out1 f99_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f99_out1 f99_in(T60, T61, .(T62, T63)) -> U3(f99_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f99_out1, T60, T61, .(T62, T63)) -> f99_out1 f285_in(T110, .(.(T110, .(T111, [])), T112)) -> f285_out1(T111) f285_in(T119, .(T120, T121)) -> U4(f285_in(T119, T121), T119, .(T120, T121)) U4(f285_out1(X106), T119, .(T120, T121)) -> f285_out1(X106) f284_in(T82, T84, T83) -> U5(f285_in(T82, T84), T82, T84, T83) U5(f285_out1(T91), T82, T84, T83) -> U6(f1_in(T91, T83, T84), T82, T84, T83, T91) U6(f1_out1, T82, T84, T83, T91) -> f284_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) 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. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F99_IN(T60, T61, .(T62, T63)) -> F99_IN(T60, T61, T63) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) 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: *F99_IN(T60, T61, .(T62, T63)) -> F99_IN(T60, T61, T63) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (78) YES ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T82, T83, T84) -> F284_IN(T82, T84, T83) F284_IN(T82, T84, T83) -> U5^1(f285_in(T82, T84), T82, T84, T83) U5^1(f285_out1(T91), T82, T84, T83) -> F1_IN(T91, T83, T84) The TRS R consists of the following rules: f1_in(T28, T29, T30) -> U1(f99_in(T28, T29, T30), T28, T29, T30) U1(f99_out1, T28, T29, T30) -> f1_out1 f1_in(T82, T83, T84) -> U2(f284_in(T82, T84, T83), T82, T83, T84) U2(f284_out1(X67), T82, T83, T84) -> f1_out1 f99_in(T49, T50, .(.(T49, .(T50, [])), T51)) -> f99_out1 f99_in(T60, T61, .(T62, T63)) -> U3(f99_in(T60, T61, T63), T60, T61, .(T62, T63)) U3(f99_out1, T60, T61, .(T62, T63)) -> f99_out1 f285_in(T110, .(.(T110, .(T111, [])), T112)) -> f285_out1(T111) f285_in(T119, .(T120, T121)) -> U4(f285_in(T119, T121), T119, .(T120, T121)) U4(f285_out1(X106), T119, .(T120, T121)) -> f285_out1(X106) f284_in(T82, T84, T83) -> U5(f285_in(T82, T84), T82, T84, T83) U5(f285_out1(T91), T82, T84, T83) -> U6(f1_in(T91, T83, T84), T82, T84, T83, T91) U6(f1_out1, T82, T84, T83, T91) -> f284_out1(T91) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) 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 = F284_IN(T82, .(.(T82, .(T111, [])), T112), T83) evaluates to t =F284_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 F284_IN(T82, .(.(T82, .(T82, [])), T112), T83) -> U5^1(f285_in(T82, .(.(T82, .(T82, [])), T112)), T82, .(.(T82, .(T82, [])), T112), T83) with rule F284_IN(T82', T84, T83') -> U5^1(f285_in(T82', T84), T82', T84, T83') at position [] and matcher [T82' / T82, T84 / .(.(T82, .(T82, [])), T112), T83' / T83] U5^1(f285_in(T82, .(.(T82, .(T82, [])), T112)), T82, .(.(T82, .(T82, [])), T112), T83) -> U5^1(f285_out1(T82), T82, .(.(T82, .(T82, [])), T112), T83) with rule f285_in(T110, .(.(T110, .(T111, [])), T112')) -> f285_out1(T111) at position [0] and matcher [T110 / T82, T111 / T82, T112' / T112] U5^1(f285_out1(T82), T82, .(.(T82, .(T82, [])), T112), T83) -> F1_IN(T82, T83, .(.(T82, .(T82, [])), T112)) with rule U5^1(f285_out1(T91), T82', T84', T83') -> F1_IN(T91, T83', T84') at position [] and matcher [T91 / T82, T82' / T82, T84' / .(.(T82, .(T82, [])), T112), T83' / T83] F1_IN(T82, T83, .(.(T82, .(T82, [])), T112)) -> F284_IN(T82, .(.(T82, .(T82, [])), T112), T83) with rule F1_IN(T82, T83, T84) -> F284_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. ---------------------------------------- (81) NO ---------------------------------------- (82) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 17, "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": { "193": { "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": [] } }, "type": "Nodes", "194": { "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": [] } }, "272": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T96 (. X75 ([]))) T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "273": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T105 T97 T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T97", "T98", "T105" ], "free": [], "exprvars": [] } }, "197": { "goal": [{ "clause": 2, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "198": { "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": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T74 (. T75 ([]))) T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T75", "T77" ], "free": [], "exprvars": [] } }, "210": { "goal": [{ "clause": 2, "scope": 3, "term": "(member (. T41 (. T42 ([]))) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "276": { "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": [] } }, "211": { "goal": [{ "clause": 3, "scope": 3, "term": "(member (. T41 (. T42 ([]))) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "277": { "goal": [{ "clause": 4, "scope": 4, "term": "(member1 (. T96 (. X75 ([]))) T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "278": { "goal": [{ "clause": 5, "scope": 4, "term": "(member1 (. T96 (. X75 ([]))) T98)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T98" ], "free": ["X75"], "exprvars": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "217": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "18": { "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": [] } }, "280": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "281": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T133 (. X114 ([]))) T135)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T133", "T135" ], "free": ["X114"], "exprvars": [] } }, "283": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [{ "clause": 1, "scope": 1, "term": "(reach T7 T8 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "200": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "202": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "268": { "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": [] } }, "203": { "goal": [{ "clause": 3, "scope": 2, "term": "(member (. T7 (. T8 ([]))) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [], "exprvars": [] } }, "204": { "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": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T41 (. T42 ([]))) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T44" ], "free": [], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "209": { "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": [] } } }, "edges": [ { "from": 17, "to": 18, "label": "CASE" }, { "from": 18, "to": 193, "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": 193, "to": 194, "label": "CASE" }, { "from": 194, "to": 197, "label": "PARALLEL" }, { "from": 194, "to": 198, "label": "PARALLEL" }, { "from": 197, "to": 200, "label": "EVAL with clause\nmember(X15, .(X15, X16)).\nand substitutionT7 -> T22,\nT8 -> T23,\nX15 -> .(T22, .(T23, [])),\nX16 -> T24,\nT9 -> .(.(T22, .(T23, [])), T24)" }, { "from": 197, "to": 201, "label": "EVAL-BACKTRACK" }, { "from": 198, "to": 203, "label": "PARALLEL" }, { "from": 198, "to": 204, "label": "PARALLEL" }, { "from": 200, "to": 202, "label": "SUCCESS" }, { "from": 203, "to": 207, "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": 203, "to": 208, "label": "EVAL-BACKTRACK" }, { "from": 204, "to": 264, "label": "FAILURE" }, { "from": 207, "to": 209, "label": "CASE" }, { "from": 209, "to": 210, "label": "PARALLEL" }, { "from": 209, "to": 211, "label": "PARALLEL" }, { "from": 210, "to": 215, "label": "EVAL with clause\nmember(X44, .(X44, X45)).\nand substitutionT41 -> T63,\nT42 -> T64,\nX44 -> .(T63, .(T64, [])),\nX45 -> T65,\nT44 -> .(.(T63, .(T64, [])), T65)" }, { "from": 210, "to": 216, "label": "EVAL-BACKTRACK" }, { "from": 211, "to": 231, "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": 211, "to": 233, "label": "EVAL-BACKTRACK" }, { "from": 215, "to": 217, "label": "SUCCESS" }, { "from": 231, "to": 207, "label": "INSTANCE with matching:\nT41 -> T74\nT42 -> T75\nT44 -> T77" }, { "from": 264, "to": 268, "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": 268, "to": 272, "label": "SPLIT 1" }, { "from": 268, "to": 273, "label": "SPLIT 2\nnew knowledge:\nT96 is ground\nT105 is ground\nT98 is ground\nreplacements:X75 -> T105" }, { "from": 272, "to": 276, "label": "CASE" }, { "from": 273, "to": 17, "label": "INSTANCE with matching:\nT1 -> T105\nT2 -> T97\nT3 -> T98" }, { "from": 276, "to": 277, "label": "PARALLEL" }, { "from": 276, "to": 278, "label": "PARALLEL" }, { "from": 277, "to": 279, "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": 277, "to": 280, "label": "EVAL-BACKTRACK" }, { "from": 278, "to": 282, "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": 278, "to": 283, "label": "EVAL-BACKTRACK" }, { "from": 279, "to": 281, "label": "SUCCESS" }, { "from": 282, "to": 272, "label": "INSTANCE with matching:\nT96 -> T133\nX75 -> X114\nT98 -> T135" } ], "type": "Graph" } } ---------------------------------------- (83) 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) ---------------------------------------- (84) 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 ---------------------------------------- (85) 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 ---------------------------------------- (86) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 7 less nodes. ---------------------------------------- (87) Complex Obligation (AND) ---------------------------------------- (88) 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 ---------------------------------------- (89) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (90) 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 ---------------------------------------- (91) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (92) 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. ---------------------------------------- (93) 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 ---------------------------------------- (94) YES ---------------------------------------- (95) 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 ---------------------------------------- (96) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (97) 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 ---------------------------------------- (98) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (99) 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. ---------------------------------------- (100) 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 ---------------------------------------- (101) YES ---------------------------------------- (102) 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 ---------------------------------------- (103) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (104) 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. ---------------------------------------- (105) 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)))) ---------------------------------------- (106) 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. ---------------------------------------- (107) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U5_GGG(X1, X2, X3, member1cC_out_gag(X1, X4, X3)) -> REACHB_IN_GGG(X4, X2, X3) we obtained the following new rules [LPAR04]: (U5_GGG(z0, z1, .(.(z0, .(z2, [])), z3), member1cC_out_gag(z0, z2, .(.(z0, .(z2, [])), z3))) -> REACHB_IN_GGG(z2, z1, .(.(z0, .(z2, [])), z3)),U5_GGG(z0, z1, .(.(z0, .(z2, [])), z3), member1cC_out_gag(z0, z2, .(.(z0, .(z2, [])), z3))) -> REACHB_IN_GGG(z2, z1, .(.(z0, .(z2, [])), z3))) (U5_GGG(z0, z1, .(z2, z3), member1cC_out_gag(z0, x3, .(z2, z3))) -> REACHB_IN_GGG(x3, z1, .(z2, z3)),U5_GGG(z0, z1, .(z2, z3), member1cC_out_gag(z0, x3, .(z2, z3))) -> REACHB_IN_GGG(x3, z1, .(z2, z3))) ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: 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))) U5_GGG(z0, z1, .(.(z0, .(z2, [])), z3), member1cC_out_gag(z0, z2, .(.(z0, .(z2, [])), z3))) -> REACHB_IN_GGG(z2, z1, .(.(z0, .(z2, [])), z3)) U5_GGG(z0, z1, .(z2, z3), member1cC_out_gag(z0, x3, .(z2, z3))) -> REACHB_IN_GGG(x3, z1, .(z2, z3)) 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. ---------------------------------------- (109) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 15, "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": { "270": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "250": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "252": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "274": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T119 (. X106 ([]))) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": ["X106"], "exprvars": [] } }, "275": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "212": { "goal": [{ "clause": 0, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "234": { "goal": [{ "clause": 2, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "213": { "goal": [{ "clause": 1, "scope": 1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "257": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T60 (. T61 ([]))) T63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61", "T63" ], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": 3, "scope": 2, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "16": { "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": [] } }, "260": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "261": { "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": [] } }, "262": { "goal": [{ "clause": -1, "scope": -1, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(reach T91 T83 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T91" ], "free": [], "exprvars": [] } }, "265": { "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": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(member (. T28 (. T29 ([]))) T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [], "exprvars": [] } }, "266": { "goal": [{ "clause": 4, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "267": { "goal": [{ "clause": 5, "scope": 3, "term": "(member1 (. T82 (. X67 ([]))) T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T82", "T84" ], "free": ["X67"], "exprvars": [] } }, "224": { "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": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "248": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 15, "to": 16, "label": "CASE" }, { "from": 16, "to": 212, "label": "PARALLEL" }, { "from": 16, "to": 213, "label": "PARALLEL" }, { "from": 212, "to": 222, "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": 213, "to": 261, "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": 222, "to": 224, "label": "CASE" }, { "from": 224, "to": 234, "label": "PARALLEL" }, { "from": 224, "to": 236, "label": "PARALLEL" }, { "from": 234, "to": 248, "label": "EVAL with clause\nmember(X36, .(X36, X37)).\nand substitutionT28 -> T49,\nT29 -> T50,\nX36 -> .(T49, .(T50, [])),\nX37 -> T51,\nT30 -> .(.(T49, .(T50, [])), T51)" }, { "from": 234, "to": 250, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 257, "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": 236, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 248, "to": 252, "label": "SUCCESS" }, { "from": 257, "to": 222, "label": "INSTANCE with matching:\nT28 -> T60\nT29 -> T61\nT30 -> T63" }, { "from": 261, "to": 262, "label": "SPLIT 1" }, { "from": 261, "to": 263, "label": "SPLIT 2\nnew knowledge:\nT82 is ground\nT91 is ground\nT84 is ground\nreplacements:X67 -> T91" }, { "from": 262, "to": 265, "label": "CASE" }, { "from": 263, "to": 15, "label": "INSTANCE with matching:\nT1 -> T91\nT2 -> T83\nT3 -> T84" }, { "from": 265, "to": 266, "label": "PARALLEL" }, { "from": 265, "to": 267, "label": "PARALLEL" }, { "from": 266, "to": 269, "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": 266, "to": 270, "label": "EVAL-BACKTRACK" }, { "from": 267, "to": 274, "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": 267, "to": 275, "label": "EVAL-BACKTRACK" }, { "from": 269, "to": 271, "label": "SUCCESS" }, { "from": 274, "to": 262, "label": "INSTANCE with matching:\nT82 -> T119\nX67 -> X106\nT84 -> T121" } ], "type": "Graph" } } ---------------------------------------- (110) Complex Obligation (AND) ---------------------------------------- (111) Obligation: Rules: f274_in(T119, T121) -> f262_in(T119, T121) :|: TRUE f262_out(x, x1) -> f274_out(x, x1) :|: TRUE f266_out(T82, T84) -> f265_out(T82, T84) :|: TRUE f265_in(x2, x3) -> f267_in(x2, x3) :|: TRUE f265_in(x4, x5) -> f266_in(x4, x5) :|: TRUE f267_out(x6, x7) -> f265_out(x6, x7) :|: TRUE f275_out -> f267_out(x8, x9) :|: TRUE f267_in(x10, .(x11, x12)) -> f274_in(x10, x12) :|: TRUE f267_in(x13, x14) -> f275_in :|: TRUE f274_out(x15, x16) -> f267_out(x15, .(x17, x16)) :|: TRUE f262_in(x18, x19) -> f265_in(x18, x19) :|: TRUE f265_out(x20, x21) -> f262_out(x20, x21) :|: TRUE f15_in(T1, T2, T3) -> f16_in(T1, T2, T3) :|: TRUE f16_out(x22, x23, x24) -> f15_out(x22, x23, x24) :|: TRUE f212_out(x25, x26, x27) -> f16_out(x25, x26, x27) :|: TRUE f16_in(x28, x29, x30) -> f212_in(x28, x29, x30) :|: TRUE f16_in(x31, x32, x33) -> f213_in(x31, x32, x33) :|: TRUE f213_out(x34, x35, x36) -> f16_out(x34, x35, x36) :|: TRUE f213_in(x37, x38, x39) -> f261_in(x37, x39, x38) :|: TRUE f261_out(x40, x41, x42) -> f213_out(x40, x42, x41) :|: TRUE f261_in(x43, x44, x45) -> f262_in(x43, x44) :|: TRUE f263_out(x46, x47, x48) -> f261_out(x49, x48, x47) :|: TRUE f262_out(x50, x51) -> f263_in(x52, x53, x51) :|: TRUE Start term: f15_in(T1, T2, T3) ---------------------------------------- (112) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f274_in(T119, T121) -> f262_in(T119, T121) :|: TRUE f265_in(x2, x3) -> f267_in(x2, x3) :|: TRUE f267_in(x10, .(x11, x12)) -> f274_in(x10, x12) :|: TRUE f262_in(x18, x19) -> f265_in(x18, x19) :|: TRUE ---------------------------------------- (113) Obligation: Rules: f274_in(T119, T121) -> f262_in(T119, T121) :|: TRUE f265_in(x2, x3) -> f267_in(x2, x3) :|: TRUE f267_in(x10, .(x11, x12)) -> f274_in(x10, x12) :|: TRUE f262_in(x18, x19) -> f265_in(x18, x19) :|: TRUE ---------------------------------------- (114) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (115) Obligation: Rules: f265_in(x2:0, .(x11:0, x12:0)) -> f265_in(x2:0, x12:0) :|: TRUE ---------------------------------------- (116) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (117) Obligation: Rules: f265_in(x2:0, .(x11:0, x12:0)) -> f265_in(x2:0, x12:0) :|: TRUE ---------------------------------------- (118) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f265_in(x2:0, .(x11:0, x12:0)) -> f265_in(x2:0, x12:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (119) Obligation: Termination digraph: Nodes: (1) f265_in(x2:0, .(x11:0, x12:0)) -> f265_in(x2:0, x12:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (120) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f265_in(x1, x2) -> f265_in(x2) .(x1, x2) -> .(x2) ---------------------------------------- (121) Obligation: Rules: f265_in(.(x12:0)) -> f265_in(x12:0) :|: TRUE ---------------------------------------- (122) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f265_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (123) Obligation: Rules: f265_in(.(x12:0)) -> f265_in(x12:0) ---------------------------------------- (124) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (125) Obligation: Q DP problem: The TRS P consists of the following rules: f265_in(.(x12:0)) -> f265_in(x12:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (126) 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: *f265_in(.(x12:0)) -> f265_in(x12:0) The graph contains the following edges 1 > 1 ---------------------------------------- (127) YES ---------------------------------------- (128) Obligation: Rules: f236_in(T60, T61, .(T62, T63)) -> f257_in(T60, T61, T63) :|: TRUE f260_out -> f236_out(T28, T29, T30) :|: TRUE f236_in(x, x1, x2) -> f260_in :|: TRUE f257_out(x3, x4, x5) -> f236_out(x3, x4, .(x6, x5)) :|: TRUE f222_in(x7, x8, x9) -> f224_in(x7, x8, x9) :|: TRUE f224_out(x10, x11, x12) -> f222_out(x10, x11, x12) :|: TRUE f222_out(x13, x14, x15) -> f257_out(x13, x14, x15) :|: TRUE f257_in(x16, x17, x18) -> f222_in(x16, x17, x18) :|: TRUE f234_out(x19, x20, x21) -> f224_out(x19, x20, x21) :|: TRUE f224_in(x22, x23, x24) -> f236_in(x22, x23, x24) :|: TRUE f236_out(x25, x26, x27) -> f224_out(x25, x26, x27) :|: TRUE f224_in(x28, x29, x30) -> f234_in(x28, x29, x30) :|: TRUE f15_in(T1, T2, T3) -> f16_in(T1, T2, T3) :|: TRUE f16_out(x31, x32, x33) -> f15_out(x31, x32, x33) :|: TRUE f212_out(x34, x35, x36) -> f16_out(x34, x35, x36) :|: TRUE f16_in(x37, x38, x39) -> f212_in(x37, x38, x39) :|: TRUE f16_in(x40, x41, x42) -> f213_in(x40, x41, x42) :|: TRUE f213_out(x43, x44, x45) -> f16_out(x43, x44, x45) :|: TRUE f222_out(x46, x47, x48) -> f212_out(x46, x47, x48) :|: TRUE f212_in(x49, x50, x51) -> f222_in(x49, x50, x51) :|: TRUE Start term: f15_in(T1, T2, T3) ---------------------------------------- (129) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f236_in(T60, T61, .(T62, T63)) -> f257_in(T60, T61, T63) :|: TRUE f222_in(x7, x8, x9) -> f224_in(x7, x8, x9) :|: TRUE f257_in(x16, x17, x18) -> f222_in(x16, x17, x18) :|: TRUE f224_in(x22, x23, x24) -> f236_in(x22, x23, x24) :|: TRUE ---------------------------------------- (130) Obligation: Rules: f236_in(T60, T61, .(T62, T63)) -> f257_in(T60, T61, T63) :|: TRUE f222_in(x7, x8, x9) -> f224_in(x7, x8, x9) :|: TRUE f257_in(x16, x17, x18) -> f222_in(x16, x17, x18) :|: TRUE f224_in(x22, x23, x24) -> f236_in(x22, x23, x24) :|: TRUE ---------------------------------------- (131) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (132) Obligation: Rules: f236_in(T60:0, T61:0, .(T62:0, T63:0)) -> f236_in(T60:0, T61:0, T63:0) :|: TRUE ---------------------------------------- (133) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (134) Obligation: Rules: f236_in(T60:0, T61:0, .(T62:0, T63:0)) -> f236_in(T60:0, T61:0, T63:0) :|: TRUE ---------------------------------------- (135) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f236_in(T60:0, T61:0, .(T62:0, T63:0)) -> f236_in(T60:0, T61:0, T63:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (136) Obligation: Termination digraph: Nodes: (1) f236_in(T60:0, T61:0, .(T62:0, T63:0)) -> f236_in(T60:0, T61:0, T63:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (137) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f236_in(x1, x2, x3) -> f236_in(x3) .(x1, x2) -> .(x2) ---------------------------------------- (138) Obligation: Rules: f236_in(.(T63:0)) -> f236_in(T63:0) :|: TRUE ---------------------------------------- (139) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f236_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (140) Obligation: Rules: f236_in(.(T63:0)) -> f236_in(T63:0) ---------------------------------------- (141) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (142) Obligation: Q DP problem: The TRS P consists of the following rules: f236_in(.(T63:0)) -> f236_in(T63:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (143) 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: *f236_in(.(T63:0)) -> f236_in(T63:0) The graph contains the following edges 1 > 1 ---------------------------------------- (144) YES ---------------------------------------- (145) Obligation: Rules: f269_in -> f269_out :|: TRUE f263_in(T91, T83, T84) -> f15_in(T91, T83, T84) :|: TRUE f15_out(x, x1, x2) -> f263_out(x, x1, x2) :|: TRUE f275_out -> f267_out(x3, x4) :|: TRUE f267_in(T119, .(T120, T121)) -> f274_in(T119, T121) :|: TRUE f267_in(x5, x6) -> f275_in :|: TRUE f274_out(x7, x8) -> f267_out(x7, .(x9, x8)) :|: TRUE f262_in(x10, x11) -> f265_in(x10, x11) :|: TRUE f265_out(x12, x13) -> f262_out(x12, x13) :|: TRUE f15_in(T1, T2, T3) -> f16_in(T1, T2, T3) :|: TRUE f16_out(x14, x15, x16) -> f15_out(x14, x15, x16) :|: TRUE f213_in(x17, x18, x19) -> f261_in(x17, x19, x18) :|: TRUE f261_out(x20, x21, x22) -> f213_out(x20, x22, x21) :|: TRUE f212_out(x23, x24, x25) -> f16_out(x23, x24, x25) :|: TRUE f16_in(x26, x27, x28) -> f212_in(x26, x27, x28) :|: TRUE f16_in(x29, x30, x31) -> f213_in(x29, x30, x31) :|: TRUE f213_out(x32, x33, x34) -> f16_out(x32, x33, x34) :|: TRUE f261_in(x35, x36, x37) -> f262_in(x35, x36) :|: TRUE f263_out(x38, x39, x40) -> f261_out(x41, x40, x39) :|: TRUE f262_out(x42, x43) -> f263_in(x44, x45, x43) :|: TRUE f274_in(x46, x47) -> f262_in(x46, x47) :|: TRUE f262_out(x48, x49) -> f274_out(x48, x49) :|: TRUE f266_out(x50, x51) -> f265_out(x50, x51) :|: TRUE f265_in(x52, x53) -> f267_in(x52, x53) :|: TRUE f265_in(x54, x55) -> f266_in(x54, x55) :|: TRUE f267_out(x56, x57) -> f265_out(x56, x57) :|: TRUE f266_in(x58, x59) -> f270_in :|: TRUE f270_out -> f266_out(x60, x61) :|: TRUE f266_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_in :|: TRUE f269_out -> f266_out(x62, .(.(x62, .(x63, [])), x64)) :|: TRUE Start term: f15_in(T1, T2, T3) ---------------------------------------- (146) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f269_in -> f269_out :|: TRUE f263_in(T91, T83, T84) -> f15_in(T91, T83, T84) :|: TRUE f267_in(T119, .(T120, T121)) -> f274_in(T119, T121) :|: TRUE f274_out(x7, x8) -> f267_out(x7, .(x9, x8)) :|: TRUE f262_in(x10, x11) -> f265_in(x10, x11) :|: TRUE f265_out(x12, x13) -> f262_out(x12, x13) :|: TRUE f15_in(T1, T2, T3) -> f16_in(T1, T2, T3) :|: TRUE f213_in(x17, x18, x19) -> f261_in(x17, x19, x18) :|: TRUE f16_in(x29, x30, x31) -> f213_in(x29, x30, x31) :|: TRUE f261_in(x35, x36, x37) -> f262_in(x35, x36) :|: TRUE f262_out(x42, x43) -> f263_in(x44, x45, x43) :|: TRUE f274_in(x46, x47) -> f262_in(x46, x47) :|: TRUE f262_out(x48, x49) -> f274_out(x48, x49) :|: TRUE f266_out(x50, x51) -> f265_out(x50, x51) :|: TRUE f265_in(x52, x53) -> f267_in(x52, x53) :|: TRUE f265_in(x54, x55) -> f266_in(x54, x55) :|: TRUE f267_out(x56, x57) -> f265_out(x56, x57) :|: TRUE f266_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_in :|: TRUE f269_out -> f266_out(x62, .(.(x62, .(x63, [])), x64)) :|: TRUE ---------------------------------------- (147) Obligation: Rules: f269_in -> f269_out :|: TRUE f263_in(T91, T83, T84) -> f15_in(T91, T83, T84) :|: TRUE f267_in(T119, .(T120, T121)) -> f274_in(T119, T121) :|: TRUE f274_out(x7, x8) -> f267_out(x7, .(x9, x8)) :|: TRUE f262_in(x10, x11) -> f265_in(x10, x11) :|: TRUE f265_out(x12, x13) -> f262_out(x12, x13) :|: TRUE f15_in(T1, T2, T3) -> f16_in(T1, T2, T3) :|: TRUE f213_in(x17, x18, x19) -> f261_in(x17, x19, x18) :|: TRUE f16_in(x29, x30, x31) -> f213_in(x29, x30, x31) :|: TRUE f261_in(x35, x36, x37) -> f262_in(x35, x36) :|: TRUE f262_out(x42, x43) -> f263_in(x44, x45, x43) :|: TRUE f274_in(x46, x47) -> f262_in(x46, x47) :|: TRUE f262_out(x48, x49) -> f274_out(x48, x49) :|: TRUE f266_out(x50, x51) -> f265_out(x50, x51) :|: TRUE f265_in(x52, x53) -> f267_in(x52, x53) :|: TRUE f265_in(x54, x55) -> f266_in(x54, x55) :|: TRUE f267_out(x56, x57) -> f265_out(x56, x57) :|: TRUE f266_in(T110, .(.(T110, .(T111, [])), T112)) -> f269_in :|: TRUE f269_out -> f266_out(x62, .(.(x62, .(x63, [])), x64)) :|: TRUE ---------------------------------------- (148) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (149) Obligation: Rules: f262_in(x10:0, .(T120:0, T121:0)) -> f262_in(x10:0, T121:0) :|: TRUE f265_out(x12:0, x13:0) -> f265_out(x12:0, .(x9:0, x13:0)) :|: TRUE f262_in(x, .(.(x, .(x1, [])), x2)) -> f265_out(x3, .(.(x3, .(x4, [])), x5)) :|: TRUE f265_out(x6, x7) -> f262_in(x8, x7) :|: TRUE ---------------------------------------- (150) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (151) Obligation: Rules: f262_in(x10:0, .(T120:0, T121:0)) -> f262_in(x10:0, T121:0) :|: TRUE f265_out(x12:0, x13:0) -> f265_out(x12:0, .(x9:0, x13:0)) :|: TRUE f262_in(x, .(.(x, .(x1, [])), x2)) -> f265_out(x3, .(.(x3, .(x4, [])), x5)) :|: TRUE f265_out(x6, x7) -> f262_in(x8, x7) :|: TRUE ---------------------------------------- (152) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f262_in(x10:0, .(T120:0, T121:0)) -> f262_in(x10:0, T121:0) :|: TRUE (2) f265_out(x12:0, x13:0) -> f265_out(x12:0, .(x9:0, x13:0)) :|: TRUE (3) f262_in(x, .(.(x, .(x1, [])), x2)) -> f265_out(x3, .(.(x3, .(x4, [])), x5)) :|: TRUE (4) f265_out(x6, x7) -> f262_in(x8, x7) :|: TRUE Arcs: (1) -> (1), (3) (2) -> (2), (4) (3) -> (2), (4) (4) -> (1), (3) This digraph is fully evaluated! ---------------------------------------- (153) Obligation: Termination digraph: Nodes: (1) f262_in(x10:0, .(T120:0, T121:0)) -> f262_in(x10:0, T121:0) :|: TRUE (2) f265_out(x6, x7) -> f262_in(x8, x7) :|: TRUE (3) f265_out(x12:0, x13:0) -> f265_out(x12:0, .(x9:0, x13:0)) :|: TRUE (4) f262_in(x, .(.(x, .(x1, [])), x2)) -> f265_out(x3, .(.(x3, .(x4, [])), x5)) :|: TRUE Arcs: (1) -> (1), (4) (2) -> (1), (4) (3) -> (2), (3) (4) -> (2), (3) This digraph is fully evaluated! ---------------------------------------- (154) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f265_out(x1, x2) -> f265_out(x2) ---------------------------------------- (155) Obligation: Rules: f262_in(x10:0, .(T120:0, T121:0)) -> f262_in(x10:0, T121:0) :|: TRUE f265_out(x7) -> f262_in(x8, x7) :|: TRUE f265_out(x13:0) -> f265_out(.(x9:0, x13:0)) :|: TRUE f262_in(x, .(.(x, .(x1, [])), x2)) -> f265_out(.(.(x3, .(x4, [])), x5)) :|: TRUE