/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern color_map(a,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 [SOUND, 0 ms] (18) QDP (19) TransformationProof [SOUND, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) NonTerminationLoopProof [COMPLETE, 0 ms] (24) NO (25) PiDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) PiDP (28) PiDPToQDPProof [SOUND, 0 ms] (29) QDP (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] (31) YES (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) PrologToPiTRSProof [SOUND, 0 ms] (38) PiTRS (39) DependencyPairsProof [EQUIVALENT, 0 ms] (40) PiDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) AND (43) PiDP (44) UsableRulesProof [EQUIVALENT, 0 ms] (45) PiDP (46) PiDPToQDPProof [SOUND, 0 ms] (47) QDP (48) QDPSizeChangeProof [EQUIVALENT, 0 ms] (49) YES (50) PiDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) PiDP (53) PiDPToQDPProof [SOUND, 0 ms] (54) QDP (55) TransformationProof [SOUND, 0 ms] (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) PiDP (60) UsableRulesProof [EQUIVALENT, 0 ms] (61) PiDP (62) PiDP (63) UsableRulesProof [EQUIVALENT, 0 ms] (64) PiDP (65) PrologToTRSTransformerProof [SOUND, 40 ms] (66) QTRS (67) DependencyPairsProof [EQUIVALENT, 0 ms] (68) QDP (69) DependencyGraphProof [EQUIVALENT, 0 ms] (70) AND (71) QDP (72) UsableRulesProof [EQUIVALENT, 0 ms] (73) QDP (74) QDPSizeChangeProof [EQUIVALENT, 0 ms] (75) YES (76) QDP (77) NonTerminationLoopProof [COMPLETE, 0 ms] (78) NO (79) QDP (80) UsableRulesProof [EQUIVALENT, 0 ms] (81) QDP (82) QDPSizeChangeProof [EQUIVALENT, 0 ms] (83) YES (84) QDP (85) NonTerminationLoopProof [COMPLETE, 0 ms] (86) NO (87) PrologToDTProblemTransformerProof [SOUND, 34 ms] (88) TRIPLES (89) TriplesToPiDPProof [SOUND, 0 ms] (90) PiDP (91) DependencyGraphProof [EQUIVALENT, 0 ms] (92) AND (93) PiDP (94) UsableRulesProof [EQUIVALENT, 0 ms] (95) PiDP (96) PiDPToQDPProof [SOUND, 0 ms] (97) QDP (98) QDPSizeChangeProof [EQUIVALENT, 0 ms] (99) YES (100) PiDP (101) UsableRulesProof [EQUIVALENT, 0 ms] (102) PiDP (103) PiDPToQDPProof [SOUND, 0 ms] (104) QDP (105) TransformationProof [SOUND, 0 ms] (106) QDP (107) TransformationProof [EQUIVALENT, 0 ms] (108) QDP (109) PiDP (110) UsableRulesProof [EQUIVALENT, 0 ms] (111) PiDP (112) PiDP (113) PrologToIRSwTTransformerProof [SOUND, 35 ms] (114) AND (115) IRSwT (116) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (117) TRUE (118) IRSwT (119) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (120) TRUE (121) IRSwT (122) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (123) IRSwT (124) IntTRSCompressionProof [EQUIVALENT, 6 ms] (125) IRSwT (126) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (127) IRSwT (128) IRSwTTerminationDigraphProof [EQUIVALENT, 1 ms] (129) IRSwT (130) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 17 ms] (131) IRSwT (132) TempFilterProof [SOUND, 3 ms] (133) IRSwT (134) IRSwTToQDPProof [SOUND, 0 ms] (135) QDP (136) QDPSizeChangeProof [EQUIVALENT, 0 ms] (137) YES (138) IRSwT (139) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (140) IRSwT (141) IntTRSCompressionProof [EQUIVALENT, 27 ms] (142) IRSwT (143) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (144) IRSwT (145) IRSwTTerminationDigraphProof [EQUIVALENT, 71 ms] (146) IRSwT (147) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (148) IRSwT (149) IRSwTToIntTRSProof [SOUND, 27 ms] (150) IRSwT ---------------------------------------- (0) Obligation: Clauses: color_map(.(Region, Regions), Colors) :- ','(color_region(Region, Colors), color_map(Regions, Colors)). color_map([], Colors). color_region(region(Color, Neighbors), Colors) :- ','(select(Color, Colors, Colors1), members(Neighbors, Colors1)). select(X, .(X, Xs), Xs). select(X, .(Y, Ys), .(Y, Zs)) :- select(X, Ys, Zs). members(.(X, Xs), Ys) :- ','(member(X, Ys), members(Xs, Ys)). members([], Ys). member(X, .(X, X1)). member(X, .(X2, T)) :- member(X, T). test_color(Name, Pairs) :- ','(colors(Name, Colors), ','(color_map(Map, Colors), ','(map(Name, Symbols, Map), symbols(Symbols, Map, Pairs)))). symbols([], [], []). symbols(.(S, Ss), .(region(C, N), Rs), .(pair(S, C), Ps)) :- symbols(Ss, Rs, Ps). map(test, .(a, .(b, .(c, .(d, .(e, .(f, [])))))), .(region(A, .(B, .(C, .(D, [])))), .(region(B, .(A, .(C, .(E, [])))), .(region(C, .(A, .(B, .(D, .(E, .(F, [])))))), .(region(D, .(A, .(C, .(F, [])))), .(region(E, .(B, .(C, .(F, [])))), .(region(F, .(C, .(D, .(E, [])))), []))))))). map(west_europe, .(portugal, .(spain, .(france, .(belgium, .(holland, .(west_germany, .(luxembourg, .(italy, .(switzerland, .(austria, [])))))))))), .(region(P, .(E, [])), .(region(E, .(F, .(P, []))), .(region(F, .(E, .(I, .(S, .(B, .(WG, .(L, []))))))), .(region(B, .(F, .(H, .(L, .(WG, []))))), .(region(H, .(B, .(WG, []))), .(region(WG, .(F, .(A, .(S, .(H, .(B, .(L, []))))))), .(region(L, .(F, .(B, .(WG, [])))), .(region(I, .(F, .(A, .(S, [])))), .(region(S, .(F, .(I, .(A, .(WG, []))))), .(region(A, .(I, .(S, .(WG, [])))), []))))))))))). colors(X, .(red, .(yellow, .(blue, .(white, []))))). Query: color_map(a,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: color_map_in_2: (f,b) color_region_in_2: (f,b) select_in_3: (f,b,f) members_in_2: (f,b) member_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) ---------------------------------------- (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: COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> COLOR_REGION_IN_AG(Region, Colors) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> U3_AG(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> SELECT_IN_AGA(Color, Colors, Colors1) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> U5_AGA(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> MEMBERS_IN_AG(Neighbors, Colors1) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) MEMBERS_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) MEMBER_IN_AG(X, .(X2, T)) -> U8_AG(X, X2, T, member_in_ag(X, T)) MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_AG(X, Xs, Ys, members_in_ag(Xs, Ys)) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_AG(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) COLOR_REGION_IN_AG(x1, x2) = COLOR_REGION_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x4) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x2, x5) U4_AG(x1, x2, x3, x4) = U4_AG(x1, x4) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) U8_AG(x1, x2, x3, x4) = U8_AG(x4) U7_AG(x1, x2, x3, x4) = U7_AG(x1, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> COLOR_REGION_IN_AG(Region, Colors) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> U3_AG(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> SELECT_IN_AGA(Color, Colors, Colors1) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> U5_AGA(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> MEMBERS_IN_AG(Neighbors, Colors1) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) MEMBERS_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) MEMBER_IN_AG(X, .(X2, T)) -> U8_AG(X, X2, T, member_in_ag(X, T)) MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_AG(X, Xs, Ys, members_in_ag(Xs, Ys)) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_AG(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) COLOR_REGION_IN_AG(x1, x2) = COLOR_REGION_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x4) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x2, x5) U4_AG(x1, x2, x3, x4) = U4_AG(x1, x4) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) U8_AG(x1, x2, x3, x4) = U8_AG(x4) U7_AG(x1, x2, x3, x4) = U7_AG(x1, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) MEMBER_IN_AG(x1, x2) = MEMBER_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: MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) MEMBER_IN_AG(x1, x2) = MEMBER_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: MEMBER_IN_AG(.(X2, T)) -> MEMBER_IN_AG(T) 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: *MEMBER_IN_AG(.(X2, T)) -> MEMBER_IN_AG(T) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) 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: U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) The TRS R consists of the following rules: member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U6_AG(Ys, member_out_ag(X)) -> MEMBERS_IN_AG(Ys) MEMBERS_IN_AG(Ys) -> U6_AG(Ys, member_in_ag(Ys)) The TRS R consists of the following rules: member_in_ag(.(X, X1)) -> member_out_ag(X) member_in_ag(.(X2, T)) -> U8_ag(member_in_ag(T)) U8_ag(member_out_ag(X)) -> member_out_ag(X) The set Q consists of the following terms: member_in_ag(x0) U8_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) TransformationProof (SOUND) By narrowing [LPAR04] the rule MEMBERS_IN_AG(Ys) -> U6_AG(Ys, member_in_ag(Ys)) at position [1] we obtained the following new rules [LPAR04]: (MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0)),MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0))) (MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(member_in_ag(x1))),MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(member_in_ag(x1)))) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U6_AG(Ys, member_out_ag(X)) -> MEMBERS_IN_AG(Ys) MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0)) MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(member_in_ag(x1))) The TRS R consists of the following rules: member_in_ag(.(X, X1)) -> member_out_ag(X) member_in_ag(.(X2, T)) -> U8_ag(member_in_ag(T)) U8_ag(member_out_ag(X)) -> member_out_ag(X) The set Q consists of the following terms: member_in_ag(x0) U8_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U6_AG(Ys, member_out_ag(X)) -> MEMBERS_IN_AG(Ys) we obtained the following new rules [LPAR04]: (U6_AG(.(z0, z1), member_out_ag(z0)) -> MEMBERS_IN_AG(.(z0, z1)),U6_AG(.(z0, z1), member_out_ag(z0)) -> MEMBERS_IN_AG(.(z0, z1))) (U6_AG(.(z0, z1), member_out_ag(x1)) -> MEMBERS_IN_AG(.(z0, z1)),U6_AG(.(z0, z1), member_out_ag(x1)) -> MEMBERS_IN_AG(.(z0, z1))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0)) MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(member_in_ag(x1))) U6_AG(.(z0, z1), member_out_ag(z0)) -> MEMBERS_IN_AG(.(z0, z1)) U6_AG(.(z0, z1), member_out_ag(x1)) -> MEMBERS_IN_AG(.(z0, z1)) The TRS R consists of the following rules: member_in_ag(.(X, X1)) -> member_out_ag(X) member_in_ag(.(X2, T)) -> U8_ag(member_in_ag(T)) U8_ag(member_out_ag(X)) -> member_out_ag(X) The set Q consists of the following terms: member_in_ag(x0) U8_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) 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 = U6_AG(.(z0, z1), member_out_ag(z0)) evaluates to t =U6_AG(.(z0, z1), member_out_ag(z0)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U6_AG(.(z0, z1), member_out_ag(z0)) -> MEMBERS_IN_AG(.(z0, z1)) with rule U6_AG(.(z0', z1'), member_out_ag(z0')) -> MEMBERS_IN_AG(.(z0', z1')) at position [] and matcher [z0' / z0, z1' / z1] MEMBERS_IN_AG(.(z0, z1)) -> U6_AG(.(z0, z1), member_out_ag(z0)) with rule MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0)) 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. ---------------------------------------- (24) NO ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (27) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (28) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: SELECT_IN_AGA(.(Y, Ys)) -> SELECT_IN_AGA(Ys) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) 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: *SELECT_IN_AGA(.(Y, Ys)) -> SELECT_IN_AGA(Ys) The graph contains the following edges 1 > 1 ---------------------------------------- (31) YES ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) The TRS R consists of the following rules: color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The argument filtering Pi contains the following mapping: color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1) U8_ag(x1, x2, x3, x4) = U8_ag(x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x4) members_out_ag(x1, x2) = members_out_ag(x1) color_region_out_ag(x1, x2) = color_region_out_ag(x1) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(Colors, color_region_out_ag(Region)) -> COLOR_MAP_IN_AG(Colors) COLOR_MAP_IN_AG(Colors) -> U1_AG(Colors, color_region_in_ag(Colors)) The TRS R consists of the following rules: color_region_in_ag(Colors) -> U3_ag(select_in_aga(Colors)) U3_ag(select_out_aga(Color, Colors1)) -> U4_ag(Color, members_in_ag(Colors1)) select_in_aga(.(X, Xs)) -> select_out_aga(X, Xs) select_in_aga(.(Y, Ys)) -> U5_aga(Y, select_in_aga(Ys)) U4_ag(Color, members_out_ag(Neighbors)) -> color_region_out_ag(region(Color, Neighbors)) U5_aga(Y, select_out_aga(X, Zs)) -> select_out_aga(X, .(Y, Zs)) members_in_ag(Ys) -> U6_ag(Ys, member_in_ag(Ys)) members_in_ag(Ys) -> members_out_ag([]) U6_ag(Ys, member_out_ag(X)) -> U7_ag(X, members_in_ag(Ys)) member_in_ag(.(X, X1)) -> member_out_ag(X) member_in_ag(.(X2, T)) -> U8_ag(member_in_ag(T)) U7_ag(X, members_out_ag(Xs)) -> members_out_ag(.(X, Xs)) U8_ag(member_out_ag(X)) -> member_out_ag(X) The set Q consists of the following terms: color_region_in_ag(x0) U3_ag(x0) select_in_aga(x0) U4_ag(x0, x1) U5_aga(x0, x1) members_in_ag(x0) U6_ag(x0, x1) member_in_ag(x0) U7_ag(x0, x1) U8_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: color_map_in_2: (f,b) color_region_in_2: (f,b) select_in_3: (f,b,f) members_in_2: (f,b) member_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (38) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) ---------------------------------------- (39) 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: COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> COLOR_REGION_IN_AG(Region, Colors) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> U3_AG(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> SELECT_IN_AGA(Color, Colors, Colors1) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> U5_AGA(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> MEMBERS_IN_AG(Neighbors, Colors1) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) MEMBERS_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) MEMBER_IN_AG(X, .(X2, T)) -> U8_AG(X, X2, T, member_in_ag(X, T)) MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_AG(X, Xs, Ys, members_in_ag(Xs, Ys)) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_AG(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) COLOR_REGION_IN_AG(x1, x2) = COLOR_REGION_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x2, x3, x5) U4_AG(x1, x2, x3, x4) = U4_AG(x1, x3, x4) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) U8_AG(x1, x2, x3, x4) = U8_AG(x2, x3, x4) U7_AG(x1, x2, x3, x4) = U7_AG(x1, x3, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (40) Obligation: Pi DP problem: The TRS P consists of the following rules: COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> COLOR_REGION_IN_AG(Region, Colors) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> U3_AG(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Color, Neighbors), Colors) -> SELECT_IN_AGA(Color, Colors, Colors1) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> U5_AGA(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> MEMBERS_IN_AG(Neighbors, Colors1) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) MEMBERS_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) MEMBER_IN_AG(X, .(X2, T)) -> U8_AG(X, X2, T, member_in_ag(X, T)) MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_AG(X, Xs, Ys, members_in_ag(Xs, Ys)) U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_AG(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) COLOR_REGION_IN_AG(x1, x2) = COLOR_REGION_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x2, x3, x5) U4_AG(x1, x2, x3, x4) = U4_AG(x1, x3, x4) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) U8_AG(x1, x2, x3, x4) = U8_AG(x2, x3, x4) U7_AG(x1, x2, x3, x4) = U7_AG(x1, x3, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (41) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes. ---------------------------------------- (42) Complex Obligation (AND) ---------------------------------------- (43) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (44) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (45) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBER_IN_AG(X, .(X2, T)) -> MEMBER_IN_AG(X, T) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (46) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBER_IN_AG(.(X2, T)) -> MEMBER_IN_AG(T) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (48) 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_AG(.(X2, T)) -> MEMBER_IN_AG(T) The graph contains the following edges 1 > 1 ---------------------------------------- (49) YES ---------------------------------------- (50) Obligation: Pi DP problem: The TRS P consists of the following rules: U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (51) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: U6_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Xs, Ys) MEMBERS_IN_AG(.(X, Xs), Ys) -> U6_AG(X, Xs, Ys, member_in_ag(X, Ys)) The TRS R consists of the following rules: member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) MEMBERS_IN_AG(x1, x2) = MEMBERS_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (53) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: U6_AG(Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Ys) MEMBERS_IN_AG(Ys) -> U6_AG(Ys, member_in_ag(Ys)) The TRS R consists of the following rules: member_in_ag(.(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(.(X2, T)) -> U8_ag(X2, T, member_in_ag(T)) U8_ag(X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The set Q consists of the following terms: member_in_ag(x0) U8_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (55) TransformationProof (SOUND) By narrowing [LPAR04] the rule MEMBERS_IN_AG(Ys) -> U6_AG(Ys, member_in_ag(Ys)) at position [1] we obtained the following new rules [LPAR04]: (MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0, .(x0, x1))),MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0, .(x0, x1)))) (MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(x0, x1, member_in_ag(x1))),MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(x0, x1, member_in_ag(x1)))) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: U6_AG(Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Ys) MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0, .(x0, x1))) MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(x0, x1, member_in_ag(x1))) The TRS R consists of the following rules: member_in_ag(.(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(.(X2, T)) -> U8_ag(X2, T, member_in_ag(T)) U8_ag(X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The set Q consists of the following terms: member_in_ag(x0) U8_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U6_AG(Ys, member_out_ag(X, Ys)) -> MEMBERS_IN_AG(Ys) we obtained the following new rules [LPAR04]: (U6_AG(.(z0, z1), member_out_ag(z0, .(z0, z1))) -> MEMBERS_IN_AG(.(z0, z1)),U6_AG(.(z0, z1), member_out_ag(z0, .(z0, z1))) -> MEMBERS_IN_AG(.(z0, z1))) (U6_AG(.(z0, z1), member_out_ag(x1, .(z0, z1))) -> MEMBERS_IN_AG(.(z0, z1)),U6_AG(.(z0, z1), member_out_ag(x1, .(z0, z1))) -> MEMBERS_IN_AG(.(z0, z1))) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), member_out_ag(x0, .(x0, x1))) MEMBERS_IN_AG(.(x0, x1)) -> U6_AG(.(x0, x1), U8_ag(x0, x1, member_in_ag(x1))) U6_AG(.(z0, z1), member_out_ag(z0, .(z0, z1))) -> MEMBERS_IN_AG(.(z0, z1)) U6_AG(.(z0, z1), member_out_ag(x1, .(z0, z1))) -> MEMBERS_IN_AG(.(z0, z1)) The TRS R consists of the following rules: member_in_ag(.(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(.(X2, T)) -> U8_ag(X2, T, member_in_ag(T)) U8_ag(X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The set Q consists of the following terms: member_in_ag(x0) U8_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (59) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (60) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (61) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECT_IN_AGA(X, .(Y, Ys), .(Y, Zs)) -> SELECT_IN_AGA(X, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) SELECT_IN_AGA(x1, x2, x3) = SELECT_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (62) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) The TRS R consists of the following rules: color_map_in_ag(.(Region, Regions), Colors) -> U1_ag(Region, Regions, Colors, color_region_in_ag(Region, Colors)) color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U1_ag(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> U2_ag(Region, Regions, Colors, color_map_in_ag(Regions, Colors)) color_map_in_ag([], Colors) -> color_map_out_ag([], Colors) U2_ag(Region, Regions, Colors, color_map_out_ag(Regions, Colors)) -> color_map_out_ag(.(Region, Regions), Colors) The argument filtering Pi contains the following mapping: color_map_in_ag(x1, x2) = color_map_in_ag(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1, x2) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (63) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (64) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Region, Regions, Colors, color_region_out_ag(Region, Colors)) -> COLOR_MAP_IN_AG(Regions, Colors) COLOR_MAP_IN_AG(.(Region, Regions), Colors) -> U1_AG(Region, Regions, Colors, color_region_in_ag(Region, Colors)) The TRS R consists of the following rules: color_region_in_ag(region(Color, Neighbors), Colors) -> U3_ag(Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) U3_ag(Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) select_in_aga(X, .(X, Xs), Xs) -> select_out_aga(X, .(X, Xs), Xs) select_in_aga(X, .(Y, Ys), .(Y, Zs)) -> U5_aga(X, Y, Ys, Zs, select_in_aga(X, Ys, Zs)) U4_ag(Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Color, Neighbors), Colors) U5_aga(X, Y, Ys, Zs, select_out_aga(X, Ys, Zs)) -> select_out_aga(X, .(Y, Ys), .(Y, Zs)) members_in_ag(.(X, Xs), Ys) -> U6_ag(X, Xs, Ys, member_in_ag(X, Ys)) members_in_ag([], Ys) -> members_out_ag([], Ys) U6_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U7_ag(X, Xs, Ys, members_in_ag(Xs, Ys)) member_in_ag(X, .(X, X1)) -> member_out_ag(X, .(X, X1)) member_in_ag(X, .(X2, T)) -> U8_ag(X, X2, T, member_in_ag(X, T)) U7_ag(X, Xs, Ys, members_out_ag(Xs, Ys)) -> members_out_ag(.(X, Xs), Ys) U8_ag(X, X2, T, member_out_ag(X, T)) -> member_out_ag(X, .(X2, T)) The argument filtering Pi contains the following mapping: color_region_in_ag(x1, x2) = color_region_in_ag(x2) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) select_in_aga(x1, x2, x3) = select_in_aga(x2) .(x1, x2) = .(x1, x2) select_out_aga(x1, x2, x3) = select_out_aga(x1, x2, x3) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x3, x5) U4_ag(x1, x2, x3, x4) = U4_ag(x1, x3, x4) members_in_ag(x1, x2) = members_in_ag(x2) U6_ag(x1, x2, x3, x4) = U6_ag(x3, x4) member_in_ag(x1, x2) = member_in_ag(x2) member_out_ag(x1, x2) = member_out_ag(x1, x2) U8_ag(x1, x2, x3, x4) = U8_ag(x2, x3, x4) U7_ag(x1, x2, x3, x4) = U7_ag(x1, x3, x4) members_out_ag(x1, x2) = members_out_ag(x1, x2) color_region_out_ag(x1, x2) = color_region_out_ag(x1, x2) region(x1, x2) = region(x1, x2) COLOR_MAP_IN_AG(x1, x2) = COLOR_MAP_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (65) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(color_map (. Region Regions) Colors)", "(',' (color_region Region Colors) (color_map Regions Colors))" ], [ "(color_map ([]) Colors)", null ], [ "(color_region (region Color Neighbors) Colors)", "(',' (select Color Colors Colors1) (members Neighbors Colors1))" ], [ "(select X (. X Xs) Xs)", null ], [ "(select X (. Y Ys) (. Y Zs))", "(select X Ys Zs)" ], [ "(members (. X Xs) Ys)", "(',' (member X Ys) (members Xs Ys))" ], [ "(members ([]) Ys)", null ], [ "(member X (. X X1))", null ], [ "(member X (. X2 T))", "(member X T)" ], [ "(test_color Name Pairs)", "(',' (colors Name Colors) (',' (color_map Map Colors) (',' (map Name Symbols Map) (symbols Symbols Map Pairs))))" ], [ "(symbols ([]) ([]) ([]))", null ], [ "(symbols (. S Ss) (. (region C N) Rs) (. (pair S C) Ps))", "(symbols Ss Rs Ps)" ], [ "(map (test) (. (a) (. (b) (. (c) (. (d) (. (e) (. (f) ([]))))))) (. (region A (. B (. C (. D ([]))))) (. (region B (. A (. C (. E ([]))))) (. (region C (. A (. B (. D (. E (. F ([]))))))) (. (region D (. A (. C (. F ([]))))) (. (region E (. B (. C (. F ([]))))) (. (region F (. C (. D (. E ([]))))) ([]))))))))", null ], [ "(map (west_europe) (. (portugal) (. (spain) (. (france) (. (belgium) (. (holland) (. (west_germany) (. (luxembourg) (. (italy) (. (switzerland) (. (austria) ([]))))))))))) (. (region P (. E ([]))) (. (region E (. F (. P ([])))) (. (region F (. E (. I (. S (. B (. WG (. L ([])))))))) (. (region B (. F (. H (. L (. WG ([])))))) (. (region H (. B (. WG ([])))) (. (region WG (. F (. A (. S (. H (. B (. L ([])))))))) (. (region L (. F (. B (. WG ([]))))) (. (region I (. F (. A (. S ([]))))) (. (region S (. F (. I (. A (. WG ([])))))) (. (region A (. I (. S (. WG ([]))))) ([]))))))))))))", null ], [ "(colors X (. (red) (. (yellow) (. (blue) (. (white) ([]))))))", null ] ] }, "graph": { "nodes": { "709": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T120 T119)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T119"], "free": [], "exprvars": [] } }, "type": "Nodes", "151": { "goal": [{ "clause": 3, "scope": 3, "term": "(select T36 T35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "470": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T96 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "130": { "goal": [ { "clause": 3, "scope": 3, "term": "(select T36 T35 X36)" }, { "clause": 4, "scope": 3, "term": "(select T36 T35 X36)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "152": { "goal": [{ "clause": 4, "scope": 3, "term": "(select T36 T35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "474": { "goal": [ { "clause": 7, "scope": 5, "term": "(member T90 T89)" }, { "clause": 8, "scope": 5, "term": "(member T90 T89)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "475": { "goal": [{ "clause": 7, "scope": 5, "term": "(member T90 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "476": { "goal": [{ "clause": 8, "scope": 5, "term": "(member T90 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "710": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "458": { "goal": [ { "clause": 5, "scope": 4, "term": "(members T43 T42)" }, { "clause": 6, "scope": 4, "term": "(members T43 T42)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "92": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T36 T35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "94": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T43 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "717": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "718": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "719": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (color_region T18 T17) (color_map T19 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "55": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "12": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "56": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T23 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "59": { "goal": [{ "clause": 2, "scope": 2, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "461": { "goal": [{ "clause": 5, "scope": 4, "term": "(members T43 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "462": { "goal": [{ "clause": 6, "scope": 4, "term": "(members T43 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "465": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T90 T89) (members T91 T89))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "169": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "466": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "469": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T90 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "8": { "goal": [ { "clause": 0, "scope": 1, "term": "(color_map T1 T2)" }, { "clause": 1, "scope": 1, "term": "(color_map T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "404": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "723": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 0, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "405": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "724": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "406": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T67 T66 X69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T66"], "free": ["X69"], "exprvars": [] } }, "703": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "725": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "61": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (select T36 T35 X36) (members T37 X36))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "407": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "704": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "62": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "705": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 8, "label": "CASE" }, { "from": 8, "to": 9, "label": "PARALLEL" }, { "from": 8, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 11, "label": "EVAL with clause\ncolor_map(.(X15, X16), X17) :- ','(color_region(X15, X17), color_map(X16, X17)).\nand substitutionX15 -> T18,\nX16 -> T19,\nT1 -> .(T18, T19),\nT2 -> T17,\nX17 -> T17,\nT15 -> T18,\nT16 -> T19" }, { "from": 9, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 723, "label": "EVAL with clause\ncolor_map([], X134).\nand substitutionT1 -> [],\nT2 -> T136,\nX134 -> T136" }, { "from": 10, "to": 724, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 55, "label": "SPLIT 1" }, { "from": 11, "to": 56, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT17 is ground\nreplacements:T19 -> T23" }, { "from": 55, "to": 59, "label": "CASE" }, { "from": 56, "to": 1, "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T17" }, { "from": 59, "to": 61, "label": "EVAL with clause\ncolor_region(region(X33, X34), X35) :- ','(select(X33, X35, X36), members(X34, X36)).\nand substitutionX33 -> T36,\nX34 -> T37,\nT18 -> region(T36, T37),\nT17 -> T35,\nX35 -> T35,\nT33 -> T36,\nT34 -> T37" }, { "from": 59, "to": 62, "label": "EVAL-BACKTRACK" }, { "from": 61, "to": 92, "label": "SPLIT 1" }, { "from": 61, "to": 94, "label": "SPLIT 2\nnew knowledge:\nT36 is ground\nT35 is ground\nT42 is ground\nreplacements:X36 -> T42,\nT37 -> T43" }, { "from": 92, "to": 130, "label": "CASE" }, { "from": 94, "to": 458, "label": "CASE" }, { "from": 130, "to": 151, "label": "PARALLEL" }, { "from": 130, "to": 152, "label": "PARALLEL" }, { "from": 151, "to": 169, "label": "EVAL with clause\nselect(X53, .(X53, X54), X54).\nand substitutionT36 -> T56,\nX53 -> T56,\nX54 -> T57,\nT35 -> .(T56, T57),\nX36 -> T57" }, { "from": 151, "to": 404, "label": "EVAL-BACKTRACK" }, { "from": 152, "to": 406, "label": "EVAL with clause\nselect(X65, .(X66, X67), .(X66, X68)) :- select(X65, X67, X68).\nand substitutionT36 -> T67,\nX65 -> T67,\nX66 -> T65,\nX67 -> T66,\nT35 -> .(T65, T66),\nX68 -> X69,\nX36 -> .(T65, X69),\nT64 -> T67" }, { "from": 152, "to": 407, "label": "EVAL-BACKTRACK" }, { "from": 169, "to": 405, "label": "SUCCESS" }, { "from": 406, "to": 92, "label": "INSTANCE with matching:\nT36 -> T67\nT35 -> T66\nX36 -> X69" }, { "from": 458, "to": 461, "label": "PARALLEL" }, { "from": 458, "to": 462, "label": "PARALLEL" }, { "from": 461, "to": 465, "label": "EVAL with clause\nmembers(.(X89, X90), X91) :- ','(member(X89, X91), members(X90, X91)).\nand substitutionX89 -> T90,\nX90 -> T91,\nT43 -> .(T90, T91),\nT42 -> T89,\nX91 -> T89,\nT87 -> T90,\nT88 -> T91" }, { "from": 461, "to": 466, "label": "EVAL-BACKTRACK" }, { "from": 462, "to": 717, "label": "EVAL with clause\nmembers([], X128).\nand substitutionT43 -> [],\nT42 -> T130,\nX128 -> T130" }, { "from": 462, "to": 718, "label": "EVAL-BACKTRACK" }, { "from": 465, "to": 469, "label": "SPLIT 1" }, { "from": 465, "to": 470, "label": "SPLIT 2\nnew knowledge:\nT90 is ground\nT89 is ground\nreplacements:T91 -> T96" }, { "from": 469, "to": 474, "label": "CASE" }, { "from": 470, "to": 94, "label": "INSTANCE with matching:\nT43 -> T96\nT42 -> T89" }, { "from": 474, "to": 475, "label": "PARALLEL" }, { "from": 474, "to": 476, "label": "PARALLEL" }, { "from": 475, "to": 703, "label": "EVAL with clause\nmember(X108, .(X108, X109)).\nand substitutionT90 -> T109,\nX108 -> T109,\nX109 -> T110,\nT89 -> .(T109, T110)" }, { "from": 475, "to": 704, "label": "EVAL-BACKTRACK" }, { "from": 476, "to": 709, "label": "EVAL with clause\nmember(X116, .(X117, X118)) :- member(X116, X118).\nand substitutionT90 -> T120,\nX116 -> T120,\nX117 -> T118,\nX118 -> T119,\nT89 -> .(T118, T119),\nT117 -> T120" }, { "from": 476, "to": 710, "label": "EVAL-BACKTRACK" }, { "from": 703, "to": 705, "label": "SUCCESS" }, { "from": 709, "to": 469, "label": "INSTANCE with matching:\nT90 -> T120\nT89 -> T119" }, { "from": 717, "to": 719, "label": "SUCCESS" }, { "from": 723, "to": 725, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (66) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T17) -> U1(f11_in(T17), T17) U1(f11_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) f1_in(T136) -> f1_out1([]) f92_in(.(T56, T57)) -> f92_out1(T56, T57) f92_in(.(T65, T66)) -> U2(f92_in(T66), .(T65, T66)) U2(f92_out1(T67, X69), .(T65, T66)) -> f92_out1(T67, .(T65, X69)) f94_in(T89) -> U3(f465_in(T89), T89) U3(f465_out1(T90, T91), T89) -> f94_out1(.(T90, T91)) f94_in(T130) -> f94_out1([]) f469_in(.(T109, T110)) -> f469_out1(T109) f469_in(.(T118, T119)) -> U4(f469_in(T119), .(T118, T119)) U4(f469_out1(T120), .(T118, T119)) -> f469_out1(T120) f55_in(T35) -> U5(f61_in(T35), T35) U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) f11_in(T17) -> U6(f55_in(T17), T17) U6(f55_out1(T18), T17) -> U7(f1_in(T17), T17, T18) U7(f1_out1(T23), T17, T18) -> f11_out1(T18, T23) f61_in(T35) -> U8(f92_in(T35), T35) U8(f92_out1(T36, T42), T35) -> U9(f94_in(T42), T35, T36, T42) U9(f94_out1(T43), T35, T36, T42) -> f61_out1(T36, T42, T43) f465_in(T89) -> U10(f469_in(T89), T89) U10(f469_out1(T90), T89) -> U11(f94_in(T89), T89, T90) U11(f94_out1(T96), T89, T90) -> f465_out1(T90, T96) Q is empty. ---------------------------------------- (67) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T17) -> U1^1(f11_in(T17), T17) F1_IN(T17) -> F11_IN(T17) F92_IN(.(T65, T66)) -> U2^1(f92_in(T66), .(T65, T66)) F92_IN(.(T65, T66)) -> F92_IN(T66) F94_IN(T89) -> U3^1(f465_in(T89), T89) F94_IN(T89) -> F465_IN(T89) F469_IN(.(T118, T119)) -> U4^1(f469_in(T119), .(T118, T119)) F469_IN(.(T118, T119)) -> F469_IN(T119) F55_IN(T35) -> U5^1(f61_in(T35), T35) F55_IN(T35) -> F61_IN(T35) F11_IN(T17) -> U6^1(f55_in(T17), T17) F11_IN(T17) -> F55_IN(T17) U6^1(f55_out1(T18), T17) -> U7^1(f1_in(T17), T17, T18) U6^1(f55_out1(T18), T17) -> F1_IN(T17) F61_IN(T35) -> U8^1(f92_in(T35), T35) F61_IN(T35) -> F92_IN(T35) U8^1(f92_out1(T36, T42), T35) -> U9^1(f94_in(T42), T35, T36, T42) U8^1(f92_out1(T36, T42), T35) -> F94_IN(T42) F465_IN(T89) -> U10^1(f469_in(T89), T89) F465_IN(T89) -> F469_IN(T89) U10^1(f469_out1(T90), T89) -> U11^1(f94_in(T89), T89, T90) U10^1(f469_out1(T90), T89) -> F94_IN(T89) The TRS R consists of the following rules: f1_in(T17) -> U1(f11_in(T17), T17) U1(f11_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) f1_in(T136) -> f1_out1([]) f92_in(.(T56, T57)) -> f92_out1(T56, T57) f92_in(.(T65, T66)) -> U2(f92_in(T66), .(T65, T66)) U2(f92_out1(T67, X69), .(T65, T66)) -> f92_out1(T67, .(T65, X69)) f94_in(T89) -> U3(f465_in(T89), T89) U3(f465_out1(T90, T91), T89) -> f94_out1(.(T90, T91)) f94_in(T130) -> f94_out1([]) f469_in(.(T109, T110)) -> f469_out1(T109) f469_in(.(T118, T119)) -> U4(f469_in(T119), .(T118, T119)) U4(f469_out1(T120), .(T118, T119)) -> f469_out1(T120) f55_in(T35) -> U5(f61_in(T35), T35) U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) f11_in(T17) -> U6(f55_in(T17), T17) U6(f55_out1(T18), T17) -> U7(f1_in(T17), T17, T18) U7(f1_out1(T23), T17, T18) -> f11_out1(T18, T23) f61_in(T35) -> U8(f92_in(T35), T35) U8(f92_out1(T36, T42), T35) -> U9(f94_in(T42), T35, T36, T42) U9(f94_out1(T43), T35, T36, T42) -> f61_out1(T36, T42, T43) f465_in(T89) -> U10(f469_in(T89), T89) U10(f469_out1(T90), T89) -> U11(f94_in(T89), T89, T90) U11(f94_out1(T96), T89, T90) -> f465_out1(T90, T96) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 14 less nodes. ---------------------------------------- (70) Complex Obligation (AND) ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: F469_IN(.(T118, T119)) -> F469_IN(T119) The TRS R consists of the following rules: f1_in(T17) -> U1(f11_in(T17), T17) U1(f11_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) f1_in(T136) -> f1_out1([]) f92_in(.(T56, T57)) -> f92_out1(T56, T57) f92_in(.(T65, T66)) -> U2(f92_in(T66), .(T65, T66)) U2(f92_out1(T67, X69), .(T65, T66)) -> f92_out1(T67, .(T65, X69)) f94_in(T89) -> U3(f465_in(T89), T89) U3(f465_out1(T90, T91), T89) -> f94_out1(.(T90, T91)) f94_in(T130) -> f94_out1([]) f469_in(.(T109, T110)) -> f469_out1(T109) f469_in(.(T118, T119)) -> U4(f469_in(T119), .(T118, T119)) U4(f469_out1(T120), .(T118, T119)) -> f469_out1(T120) f55_in(T35) -> U5(f61_in(T35), T35) U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) f11_in(T17) -> U6(f55_in(T17), T17) U6(f55_out1(T18), T17) -> U7(f1_in(T17), T17, T18) U7(f1_out1(T23), T17, T18) -> f11_out1(T18, T23) f61_in(T35) -> U8(f92_in(T35), T35) U8(f92_out1(T36, T42), T35) -> U9(f94_in(T42), T35, T36, T42) U9(f94_out1(T43), T35, T36, T42) -> f61_out1(T36, T42, T43) f465_in(T89) -> U10(f469_in(T89), T89) U10(f469_out1(T90), T89) -> U11(f94_in(T89), T89, T90) U11(f94_out1(T96), T89, T90) -> f465_out1(T90, T96) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) 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. ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: F469_IN(.(T118, T119)) -> F469_IN(T119) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F469_IN(.(T118, T119)) -> F469_IN(T119) The graph contains the following edges 1 > 1 ---------------------------------------- (75) YES ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F94_IN(T89) -> F465_IN(T89) F465_IN(T89) -> U10^1(f469_in(T89), T89) U10^1(f469_out1(T90), T89) -> F94_IN(T89) The TRS R consists of the following rules: f1_in(T17) -> U1(f11_in(T17), T17) U1(f11_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) f1_in(T136) -> f1_out1([]) f92_in(.(T56, T57)) -> f92_out1(T56, T57) f92_in(.(T65, T66)) -> U2(f92_in(T66), .(T65, T66)) U2(f92_out1(T67, X69), .(T65, T66)) -> f92_out1(T67, .(T65, X69)) f94_in(T89) -> U3(f465_in(T89), T89) U3(f465_out1(T90, T91), T89) -> f94_out1(.(T90, T91)) f94_in(T130) -> f94_out1([]) f469_in(.(T109, T110)) -> f469_out1(T109) f469_in(.(T118, T119)) -> U4(f469_in(T119), .(T118, T119)) U4(f469_out1(T120), .(T118, T119)) -> f469_out1(T120) f55_in(T35) -> U5(f61_in(T35), T35) U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) f11_in(T17) -> U6(f55_in(T17), T17) U6(f55_out1(T18), T17) -> U7(f1_in(T17), T17, T18) U7(f1_out1(T23), T17, T18) -> f11_out1(T18, T23) f61_in(T35) -> U8(f92_in(T35), T35) U8(f92_out1(T36, T42), T35) -> U9(f94_in(T42), T35, T36, T42) U9(f94_out1(T43), T35, T36, T42) -> f61_out1(T36, T42, T43) f465_in(T89) -> U10(f469_in(T89), T89) U10(f469_out1(T90), T89) -> U11(f94_in(T89), T89, T90) U11(f94_out1(T96), T89, T90) -> f465_out1(T90, T96) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) 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 = F465_IN(.(T109, T110)) evaluates to t =F465_IN(.(T109, T110)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F465_IN(.(T109, T110)) -> U10^1(f469_in(.(T109, T110)), .(T109, T110)) with rule F465_IN(T89) -> U10^1(f469_in(T89), T89) at position [] and matcher [T89 / .(T109, T110)] U10^1(f469_in(.(T109, T110)), .(T109, T110)) -> U10^1(f469_out1(T109), .(T109, T110)) with rule f469_in(.(T109', T110')) -> f469_out1(T109') at position [0] and matcher [T109' / T109, T110' / T110] U10^1(f469_out1(T109), .(T109, T110)) -> F94_IN(.(T109, T110)) with rule U10^1(f469_out1(T90), T89') -> F94_IN(T89') at position [] and matcher [T90 / T109, T89' / .(T109, T110)] F94_IN(.(T109, T110)) -> F465_IN(.(T109, T110)) with rule F94_IN(T89) -> F465_IN(T89) 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. ---------------------------------------- (78) NO ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: F92_IN(.(T65, T66)) -> F92_IN(T66) The TRS R consists of the following rules: f1_in(T17) -> U1(f11_in(T17), T17) U1(f11_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) f1_in(T136) -> f1_out1([]) f92_in(.(T56, T57)) -> f92_out1(T56, T57) f92_in(.(T65, T66)) -> U2(f92_in(T66), .(T65, T66)) U2(f92_out1(T67, X69), .(T65, T66)) -> f92_out1(T67, .(T65, X69)) f94_in(T89) -> U3(f465_in(T89), T89) U3(f465_out1(T90, T91), T89) -> f94_out1(.(T90, T91)) f94_in(T130) -> f94_out1([]) f469_in(.(T109, T110)) -> f469_out1(T109) f469_in(.(T118, T119)) -> U4(f469_in(T119), .(T118, T119)) U4(f469_out1(T120), .(T118, T119)) -> f469_out1(T120) f55_in(T35) -> U5(f61_in(T35), T35) U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) f11_in(T17) -> U6(f55_in(T17), T17) U6(f55_out1(T18), T17) -> U7(f1_in(T17), T17, T18) U7(f1_out1(T23), T17, T18) -> f11_out1(T18, T23) f61_in(T35) -> U8(f92_in(T35), T35) U8(f92_out1(T36, T42), T35) -> U9(f94_in(T42), T35, T36, T42) U9(f94_out1(T43), T35, T36, T42) -> f61_out1(T36, T42, T43) f465_in(T89) -> U10(f469_in(T89), T89) U10(f469_out1(T90), T89) -> U11(f94_in(T89), T89, T90) U11(f94_out1(T96), T89, T90) -> f465_out1(T90, T96) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) 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. ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: F92_IN(.(T65, T66)) -> F92_IN(T66) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) 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: *F92_IN(.(T65, T66)) -> F92_IN(T66) The graph contains the following edges 1 > 1 ---------------------------------------- (83) YES ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T17) -> F11_IN(T17) F11_IN(T17) -> U6^1(f55_in(T17), T17) U6^1(f55_out1(T18), T17) -> F1_IN(T17) The TRS R consists of the following rules: f1_in(T17) -> U1(f11_in(T17), T17) U1(f11_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) f1_in(T136) -> f1_out1([]) f92_in(.(T56, T57)) -> f92_out1(T56, T57) f92_in(.(T65, T66)) -> U2(f92_in(T66), .(T65, T66)) U2(f92_out1(T67, X69), .(T65, T66)) -> f92_out1(T67, .(T65, X69)) f94_in(T89) -> U3(f465_in(T89), T89) U3(f465_out1(T90, T91), T89) -> f94_out1(.(T90, T91)) f94_in(T130) -> f94_out1([]) f469_in(.(T109, T110)) -> f469_out1(T109) f469_in(.(T118, T119)) -> U4(f469_in(T119), .(T118, T119)) U4(f469_out1(T120), .(T118, T119)) -> f469_out1(T120) f55_in(T35) -> U5(f61_in(T35), T35) U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) f11_in(T17) -> U6(f55_in(T17), T17) U6(f55_out1(T18), T17) -> U7(f1_in(T17), T17, T18) U7(f1_out1(T23), T17, T18) -> f11_out1(T18, T23) f61_in(T35) -> U8(f92_in(T35), T35) U8(f92_out1(T36, T42), T35) -> U9(f94_in(T42), T35, T36, T42) U9(f94_out1(T43), T35, T36, T42) -> f61_out1(T36, T42, T43) f465_in(T89) -> U10(f469_in(T89), T89) U10(f469_out1(T90), T89) -> U11(f94_in(T89), T89, T90) U11(f94_out1(T96), T89, T90) -> f465_out1(T90, T96) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) 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 = F11_IN(.(T56, T57)) evaluates to t =F11_IN(.(T56, T57)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F11_IN(.(T56, T57)) -> U6^1(f55_in(.(T56, T57)), .(T56, T57)) with rule F11_IN(T17) -> U6^1(f55_in(T17), T17) at position [] and matcher [T17 / .(T56, T57)] U6^1(f55_in(.(T56, T57)), .(T56, T57)) -> U6^1(U5(f61_in(.(T56, T57)), .(T56, T57)), .(T56, T57)) with rule f55_in(T35') -> U5(f61_in(T35'), T35') at position [0] and matcher [T35' / .(T56, T57)] U6^1(U5(f61_in(.(T56, T57)), .(T56, T57)), .(T56, T57)) -> U6^1(U5(U8(f92_in(.(T56, T57)), .(T56, T57)), .(T56, T57)), .(T56, T57)) with rule f61_in(T35') -> U8(f92_in(T35'), T35') at position [0,0] and matcher [T35' / .(T56, T57)] U6^1(U5(U8(f92_in(.(T56, T57)), .(T56, T57)), .(T56, T57)), .(T56, T57)) -> U6^1(U5(U8(f92_out1(T56, T57), .(T56, T57)), .(T56, T57)), .(T56, T57)) with rule f92_in(.(T56', T57')) -> f92_out1(T56', T57') at position [0,0,0] and matcher [T56' / T56, T57' / T57] U6^1(U5(U8(f92_out1(T56, T57), .(T56, T57)), .(T56, T57)), .(T56, T57)) -> U6^1(U5(U9(f94_in(T57), .(T56, T57), T56, T57), .(T56, T57)), .(T56, T57)) with rule U8(f92_out1(T36, T42'), T35'') -> U9(f94_in(T42'), T35'', T36, T42') at position [0,0] and matcher [T36 / T56, T42' / T57, T35'' / .(T56, T57)] U6^1(U5(U9(f94_in(T57), .(T56, T57), T56, T57), .(T56, T57)), .(T56, T57)) -> U6^1(U5(U9(f94_out1([]), .(T56, T57), T56, T57), .(T56, T57)), .(T56, T57)) with rule f94_in(T130) -> f94_out1([]) at position [0,0,0] and matcher [T130 / T57] U6^1(U5(U9(f94_out1([]), .(T56, T57), T56, T57), .(T56, T57)), .(T56, T57)) -> U6^1(U5(f61_out1(T56, T57, []), .(T56, T57)), .(T56, T57)) with rule U9(f94_out1(T43), T35', T36', T42) -> f61_out1(T36', T42, T43) at position [0,0] and matcher [T43 / [], T35' / .(T56, T57), T36' / T56, T42 / T57] U6^1(U5(f61_out1(T56, T57, []), .(T56, T57)), .(T56, T57)) -> U6^1(f55_out1(region(T56, [])), .(T56, T57)) with rule U5(f61_out1(T36, X36, T37), T35) -> f55_out1(region(T36, T37)) at position [0] and matcher [T36 / T56, X36 / T57, T37 / [], T35 / .(T56, T57)] U6^1(f55_out1(region(T56, [])), .(T56, T57)) -> F1_IN(.(T56, T57)) with rule U6^1(f55_out1(T18), T17') -> F1_IN(T17') at position [] and matcher [T18 / region(T56, []), T17' / .(T56, T57)] F1_IN(.(T56, T57)) -> F11_IN(.(T56, T57)) with rule F1_IN(T17) -> F11_IN(T17) 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. ---------------------------------------- (86) NO ---------------------------------------- (87) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(color_map (. Region Regions) Colors)", "(',' (color_region Region Colors) (color_map Regions Colors))" ], [ "(color_map ([]) Colors)", null ], [ "(color_region (region Color Neighbors) Colors)", "(',' (select Color Colors Colors1) (members Neighbors Colors1))" ], [ "(select X (. X Xs) Xs)", null ], [ "(select X (. Y Ys) (. Y Zs))", "(select X Ys Zs)" ], [ "(members (. X Xs) Ys)", "(',' (member X Ys) (members Xs Ys))" ], [ "(members ([]) Ys)", null ], [ "(member X (. X X1))", null ], [ "(member X (. X2 T))", "(member X T)" ], [ "(test_color Name Pairs)", "(',' (colors Name Colors) (',' (color_map Map Colors) (',' (map Name Symbols Map) (symbols Symbols Map Pairs))))" ], [ "(symbols ([]) ([]) ([]))", null ], [ "(symbols (. S Ss) (. (region C N) Rs) (. (pair S C) Ps))", "(symbols Ss Rs Ps)" ], [ "(map (test) (. (a) (. (b) (. (c) (. (d) (. (e) (. (f) ([]))))))) (. (region A (. B (. C (. D ([]))))) (. (region B (. A (. C (. E ([]))))) (. (region C (. A (. B (. D (. E (. F ([]))))))) (. (region D (. A (. C (. F ([]))))) (. (region E (. B (. C (. F ([]))))) (. (region F (. C (. D (. E ([]))))) ([]))))))))", null ], [ "(map (west_europe) (. (portugal) (. (spain) (. (france) (. (belgium) (. (holland) (. (west_germany) (. (luxembourg) (. (italy) (. (switzerland) (. (austria) ([]))))))))))) (. (region P (. E ([]))) (. (region E (. F (. P ([])))) (. (region F (. E (. I (. S (. B (. WG (. L ([])))))))) (. (region B (. F (. H (. L (. WG ([])))))) (. (region H (. B (. WG ([])))) (. (region WG (. F (. A (. S (. H (. B (. L ([])))))))) (. (region L (. F (. B (. WG ([]))))) (. (region I (. F (. A (. S ([]))))) (. (region S (. F (. I (. A (. WG ([])))))) (. (region A (. I (. S (. WG ([]))))) ([]))))))))))))", null ], [ "(colors X (. (red) (. (yellow) (. (blue) (. (white) ([]))))))", null ] ] }, "graph": { "nodes": { "46": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (color_region T9 T8) (color_map T10 T8))" }, { "clause": 1, "scope": 1, "term": "(color_map T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "47": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [[ "(color_map T1 T2)", "(color_map (. X6 X7) X8)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [ "X6", "X7", "X8" ], "exprvars": [] } }, "48": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (color_region T9 T8) (color_map T10 T8))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(color_map T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (color_region T9 T8) (color_map T10 T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "190": { "goal": [ { "clause": 3, "scope": 3, "term": "(select T26 T25 X26)" }, { "clause": 4, "scope": 3, "term": "(select T26 T25 X26)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": ["X26"], "exprvars": [] } }, "type": "Nodes", "471": { "goal": [ { "clause": 7, "scope": 5, "term": "(member T86 T85)" }, { "clause": 8, "scope": 5, "term": "(member T86 T85)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T85"], "free": [], "exprvars": [] } }, "472": { "goal": [{ "clause": 7, "scope": 5, "term": "(member T86 T85)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T85"], "free": [], "exprvars": [] } }, "473": { "goal": [{ "clause": 8, "scope": 5, "term": "(member T86 T85)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T85"], "free": [], "exprvars": [] } }, "254": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "454": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T34 T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [], "exprvars": [] } }, "455": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T67 T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "477": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "478": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "336": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T59 T58 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T58"], "free": ["X59"], "exprvars": [] } }, "457": { "goal": [ { "clause": 5, "scope": 4, "term": "(members T34 T33)" }, { "clause": 6, "scope": 4, "term": "(members T34 T33)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [], "exprvars": [] } }, "479": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "338": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "459": { "goal": [{ "clause": 5, "scope": 4, "term": "(members T34 T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [], "exprvars": [] } }, "635": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "636": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "714": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "50": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(color_map T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "715": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (select T26 T25 X26) (members T27 X26)) (color_map T28 T25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": ["X26"], "exprvars": [] } }, "518": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "716": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T26 T25 X26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": ["X26"], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (members T34 T33) (color_map T35 T25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T33" ], "free": [], "exprvars": [] } }, "260": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "460": { "goal": [{ "clause": 6, "scope": 4, "term": "(members T34 T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [], "exprvars": [] } }, "463": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T86 T85) (members T87 T85))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T85"], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "266": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "464": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "642": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(color_map T1 T2)" }, { "clause": 1, "scope": 1, "term": "(color_map T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "467": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T86 T85)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T85"], "free": [], "exprvars": [] } }, "643": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "720": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "468": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T92 T85)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T85"], "free": [], "exprvars": [] } }, "721": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "722": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "206": { "goal": [{ "clause": 3, "scope": 3, "term": "(select T26 T25 X26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": ["X26"], "exprvars": [] } }, "209": { "goal": [{ "clause": 4, "scope": 3, "term": "(select T26 T25 X26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": ["X26"], "exprvars": [] } }, "509": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T116 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 46, "label": "EVAL with clause\ncolor_map(.(X6, X7), X8) :- ','(color_region(X6, X8), color_map(X7, X8)).\nand substitutionX6 -> T9,\nX7 -> T10,\nT1 -> .(T9, T10),\nT2 -> T8,\nX8 -> T8,\nT6 -> T9,\nT7 -> T10" }, { "from": 5, "to": 47, "label": "EVAL-BACKTRACK" }, { "from": 46, "to": 48, "label": "CASE" }, { "from": 47, "to": 720, "label": "EVAL with clause\ncolor_map([], X129).\nand substitutionT1 -> [],\nT2 -> T134,\nX129 -> T134" }, { "from": 47, "to": 721, "label": "EVAL-BACKTRACK" }, { "from": 48, "to": 49, "label": "PARALLEL" }, { "from": 48, "to": 50, "label": "PARALLEL" }, { "from": 49, "to": 51, "label": "EVAL with clause\ncolor_region(region(X23, X24), X25) :- ','(select(X23, X25, X26), members(X24, X26)).\nand substitutionX23 -> T26,\nX24 -> T27,\nT9 -> region(T26, T27),\nT8 -> T25,\nX25 -> T25,\nT23 -> T26,\nT24 -> T27,\nT10 -> T28" }, { "from": 49, "to": 52, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 643, "label": "FAILURE" }, { "from": 51, "to": 53, "label": "SPLIT 1" }, { "from": 51, "to": 54, "label": "SPLIT 2\nnew knowledge:\nT26 is ground\nT25 is ground\nT33 is ground\nreplacements:X26 -> T33,\nT27 -> T34,\nT28 -> T35" }, { "from": 53, "to": 190, "label": "CASE" }, { "from": 54, "to": 454, "label": "SPLIT 1" }, { "from": 54, "to": 455, "label": "SPLIT 2\nnew knowledge:\nT34 is ground\nT33 is ground\nreplacements:T35 -> T67" }, { "from": 190, "to": 206, "label": "PARALLEL" }, { "from": 190, "to": 209, "label": "PARALLEL" }, { "from": 206, "to": 254, "label": "EVAL with clause\nselect(X43, .(X43, X44), X44).\nand substitutionT26 -> T48,\nX43 -> T48,\nX44 -> T49,\nT25 -> .(T48, T49),\nX26 -> T49" }, { "from": 206, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 209, "to": 336, "label": "EVAL with clause\nselect(X55, .(X56, X57), .(X56, X58)) :- select(X55, X57, X58).\nand substitutionT26 -> T59,\nX55 -> T59,\nX56 -> T57,\nX57 -> T58,\nT25 -> .(T57, T58),\nX58 -> X59,\nX26 -> .(T57, X59),\nT56 -> T59" }, { "from": 209, "to": 338, "label": "EVAL-BACKTRACK" }, { "from": 254, "to": 266, "label": "SUCCESS" }, { "from": 336, "to": 53, "label": "INSTANCE with matching:\nT26 -> T59\nT25 -> T58\nX26 -> X59" }, { "from": 454, "to": 457, "label": "CASE" }, { "from": 455, "to": 2, "label": "INSTANCE with matching:\nT1 -> T67\nT2 -> T25" }, { "from": 457, "to": 459, "label": "PARALLEL" }, { "from": 457, "to": 460, "label": "PARALLEL" }, { "from": 459, "to": 463, "label": "EVAL with clause\nmembers(.(X82, X83), X84) :- ','(member(X82, X84), members(X83, X84)).\nand substitutionX82 -> T86,\nX83 -> T87,\nT34 -> .(T86, T87),\nT33 -> T85,\nX84 -> T85,\nT83 -> T86,\nT84 -> T87" }, { "from": 459, "to": 464, "label": "EVAL-BACKTRACK" }, { "from": 460, "to": 635, "label": "EVAL with clause\nmembers([], X121).\nand substitutionT34 -> [],\nT33 -> T126,\nX121 -> T126" }, { "from": 460, "to": 636, "label": "EVAL-BACKTRACK" }, { "from": 463, "to": 467, "label": "SPLIT 1" }, { "from": 463, "to": 468, "label": "SPLIT 2\nnew knowledge:\nT86 is ground\nT85 is ground\nreplacements:T87 -> T92" }, { "from": 467, "to": 471, "label": "CASE" }, { "from": 468, "to": 454, "label": "INSTANCE with matching:\nT34 -> T92\nT33 -> T85" }, { "from": 471, "to": 472, "label": "PARALLEL" }, { "from": 471, "to": 473, "label": "PARALLEL" }, { "from": 472, "to": 477, "label": "EVAL with clause\nmember(X101, .(X101, X102)).\nand substitutionT86 -> T105,\nX101 -> T105,\nX102 -> T106,\nT85 -> .(T105, T106)" }, { "from": 472, "to": 478, "label": "EVAL-BACKTRACK" }, { "from": 473, "to": 509, "label": "EVAL with clause\nmember(X109, .(X110, X111)) :- member(X109, X111).\nand substitutionT86 -> T116,\nX109 -> T116,\nX110 -> T114,\nX111 -> T115,\nT85 -> .(T114, T115),\nT113 -> T116" }, { "from": 473, "to": 518, "label": "EVAL-BACKTRACK" }, { "from": 477, "to": 479, "label": "SUCCESS" }, { "from": 509, "to": 467, "label": "INSTANCE with matching:\nT86 -> T116\nT85 -> T115" }, { "from": 635, "to": 642, "label": "SUCCESS" }, { "from": 643, "to": 714, "label": "EVAL with clause\ncolor_map([], X127).\nand substitutionT1 -> [],\nT8 -> T132,\nX127 -> T132" }, { "from": 643, "to": 715, "label": "EVAL-BACKTRACK" }, { "from": 714, "to": 716, "label": "SUCCESS" }, { "from": 720, "to": 722, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (88) Obligation: Triples: selectA(X1, .(X2, X3), .(X2, X4)) :- selectA(X1, X3, X4). membersC(.(X1, X2), X3) :- memberD(X1, X3). membersC(.(X1, X2), X3) :- ','(membercD(X1, X3), membersC(X2, X3)). memberD(X1, .(X2, X3)) :- memberD(X1, X3). color_mapB(.(region(X1, X2), X3), X4) :- selectA(X1, X4, X5). color_mapB(.(region(X1, X2), X3), X4) :- ','(selectcA(X1, X4, X5), membersC(X2, X5)). color_mapB(.(region(X1, X2), X3), X4) :- ','(selectcA(X1, X4, X5), ','(memberscC(X2, X5), color_mapB(X3, X4))). Clauses: selectcA(X1, .(X1, X2), X2). selectcA(X1, .(X2, X3), .(X2, X4)) :- selectcA(X1, X3, X4). color_mapcB(.(region(X1, X2), X3), X4) :- ','(selectcA(X1, X4, X5), ','(memberscC(X2, X5), color_mapcB(X3, X4))). color_mapcB([], X1). color_mapcB([], X1). memberscC(.(X1, X2), X3) :- ','(membercD(X1, X3), memberscC(X2, X3)). memberscC([], X1). membercD(X1, .(X1, X2)). membercD(X1, .(X2, X3)) :- membercD(X1, X3). Afs: color_mapB(x1, x2) = color_mapB(x2) ---------------------------------------- (89) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: color_mapB_in_2: (f,b) selectA_in_3: (f,b,f) selectcA_in_3: (f,b,f) membersC_in_2: (f,b) memberD_in_2: (f,b) membercD_in_2: (f,b) memberscC_in_2: (f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> U6_AG(X1, X2, X3, X4, selectA_in_aga(X1, X4, X5)) COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> SELECTA_IN_AGA(X1, X4, X5) SELECTA_IN_AGA(X1, .(X2, X3), .(X2, X4)) -> U1_AGA(X1, X2, X3, X4, selectA_in_aga(X1, X3, X4)) SELECTA_IN_AGA(X1, .(X2, X3), .(X2, X4)) -> SELECTA_IN_AGA(X1, X3, X4) COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> U7_AG(X1, X2, X3, X4, selectcA_in_aga(X1, X4, X5)) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> U8_AG(X1, X2, X3, X4, membersC_in_ag(X2, X5)) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> MEMBERSC_IN_AG(X2, X5) MEMBERSC_IN_AG(.(X1, X2), X3) -> U2_AG(X1, X2, X3, memberD_in_ag(X1, X3)) MEMBERSC_IN_AG(.(X1, X2), X3) -> MEMBERD_IN_AG(X1, X3) MEMBERD_IN_AG(X1, .(X2, X3)) -> U5_AG(X1, X2, X3, memberD_in_ag(X1, X3)) MEMBERD_IN_AG(X1, .(X2, X3)) -> MEMBERD_IN_AG(X1, X3) MEMBERSC_IN_AG(.(X1, X2), X3) -> U3_AG(X1, X2, X3, membercD_in_ag(X1, X3)) U3_AG(X1, X2, X3, membercD_out_ag(X1, X3)) -> U4_AG(X1, X2, X3, membersC_in_ag(X2, X3)) U3_AG(X1, X2, X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X2, X3) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> U9_AG(X1, X2, X3, X4, memberscC_in_ag(X2, X5)) U9_AG(X1, X2, X3, X4, memberscC_out_ag(X2, X5)) -> U10_AG(X1, X2, X3, X4, color_mapB_in_ag(X3, X4)) U9_AG(X1, X2, X3, X4, memberscC_out_ag(X2, X5)) -> COLOR_MAPB_IN_AG(X3, X4) The TRS R consists of the following rules: selectcA_in_aga(X1, .(X1, X2), X2) -> selectcA_out_aga(X1, .(X1, X2), X2) selectcA_in_aga(X1, .(X2, X3), .(X2, X4)) -> U12_aga(X1, X2, X3, X4, selectcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, selectcA_out_aga(X1, X3, X4)) -> selectcA_out_aga(X1, .(X2, X3), .(X2, X4)) membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) memberscC_in_ag(.(X1, X2), X3) -> U16_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U16_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> U17_ag(X1, X2, X3, memberscC_in_ag(X2, X3)) memberscC_in_ag([], X1) -> memberscC_out_ag([], X1) U17_ag(X1, X2, X3, memberscC_out_ag(X2, X3)) -> memberscC_out_ag(.(X1, X2), X3) The argument filtering Pi contains the following mapping: color_mapB_in_ag(x1, x2) = color_mapB_in_ag(x2) selectA_in_aga(x1, x2, x3) = selectA_in_aga(x2) .(x1, x2) = .(x1, x2) selectcA_in_aga(x1, x2, x3) = selectcA_in_aga(x2) selectcA_out_aga(x1, x2, x3) = selectcA_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) membersC_in_ag(x1, x2) = membersC_in_ag(x2) memberD_in_ag(x1, x2) = memberD_in_ag(x2) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) memberscC_in_ag(x1, x2) = memberscC_in_ag(x2) U16_ag(x1, x2, x3, x4) = U16_ag(x3, x4) U17_ag(x1, x2, x3, x4) = U17_ag(x1, x3, x4) memberscC_out_ag(x1, x2) = memberscC_out_ag(x1, x2) COLOR_MAPB_IN_AG(x1, x2) = COLOR_MAPB_IN_AG(x2) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) SELECTA_IN_AGA(x1, x2, x3) = SELECTA_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x2, x3, x5) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x4, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x4, x5) MEMBERSC_IN_AG(x1, x2) = MEMBERSC_IN_AG(x2) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) MEMBERD_IN_AG(x1, x2) = MEMBERD_IN_AG(x2) U5_AG(x1, x2, x3, x4) = U5_AG(x2, x3, x4) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) U4_AG(x1, x2, x3, x4) = U4_AG(x3, x4) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x4, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (90) Obligation: Pi DP problem: The TRS P consists of the following rules: COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> U6_AG(X1, X2, X3, X4, selectA_in_aga(X1, X4, X5)) COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> SELECTA_IN_AGA(X1, X4, X5) SELECTA_IN_AGA(X1, .(X2, X3), .(X2, X4)) -> U1_AGA(X1, X2, X3, X4, selectA_in_aga(X1, X3, X4)) SELECTA_IN_AGA(X1, .(X2, X3), .(X2, X4)) -> SELECTA_IN_AGA(X1, X3, X4) COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> U7_AG(X1, X2, X3, X4, selectcA_in_aga(X1, X4, X5)) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> U8_AG(X1, X2, X3, X4, membersC_in_ag(X2, X5)) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> MEMBERSC_IN_AG(X2, X5) MEMBERSC_IN_AG(.(X1, X2), X3) -> U2_AG(X1, X2, X3, memberD_in_ag(X1, X3)) MEMBERSC_IN_AG(.(X1, X2), X3) -> MEMBERD_IN_AG(X1, X3) MEMBERD_IN_AG(X1, .(X2, X3)) -> U5_AG(X1, X2, X3, memberD_in_ag(X1, X3)) MEMBERD_IN_AG(X1, .(X2, X3)) -> MEMBERD_IN_AG(X1, X3) MEMBERSC_IN_AG(.(X1, X2), X3) -> U3_AG(X1, X2, X3, membercD_in_ag(X1, X3)) U3_AG(X1, X2, X3, membercD_out_ag(X1, X3)) -> U4_AG(X1, X2, X3, membersC_in_ag(X2, X3)) U3_AG(X1, X2, X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X2, X3) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> U9_AG(X1, X2, X3, X4, memberscC_in_ag(X2, X5)) U9_AG(X1, X2, X3, X4, memberscC_out_ag(X2, X5)) -> U10_AG(X1, X2, X3, X4, color_mapB_in_ag(X3, X4)) U9_AG(X1, X2, X3, X4, memberscC_out_ag(X2, X5)) -> COLOR_MAPB_IN_AG(X3, X4) The TRS R consists of the following rules: selectcA_in_aga(X1, .(X1, X2), X2) -> selectcA_out_aga(X1, .(X1, X2), X2) selectcA_in_aga(X1, .(X2, X3), .(X2, X4)) -> U12_aga(X1, X2, X3, X4, selectcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, selectcA_out_aga(X1, X3, X4)) -> selectcA_out_aga(X1, .(X2, X3), .(X2, X4)) membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) memberscC_in_ag(.(X1, X2), X3) -> U16_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U16_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> U17_ag(X1, X2, X3, memberscC_in_ag(X2, X3)) memberscC_in_ag([], X1) -> memberscC_out_ag([], X1) U17_ag(X1, X2, X3, memberscC_out_ag(X2, X3)) -> memberscC_out_ag(.(X1, X2), X3) The argument filtering Pi contains the following mapping: color_mapB_in_ag(x1, x2) = color_mapB_in_ag(x2) selectA_in_aga(x1, x2, x3) = selectA_in_aga(x2) .(x1, x2) = .(x1, x2) selectcA_in_aga(x1, x2, x3) = selectcA_in_aga(x2) selectcA_out_aga(x1, x2, x3) = selectcA_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) membersC_in_ag(x1, x2) = membersC_in_ag(x2) memberD_in_ag(x1, x2) = memberD_in_ag(x2) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) memberscC_in_ag(x1, x2) = memberscC_in_ag(x2) U16_ag(x1, x2, x3, x4) = U16_ag(x3, x4) U17_ag(x1, x2, x3, x4) = U17_ag(x1, x3, x4) memberscC_out_ag(x1, x2) = memberscC_out_ag(x1, x2) COLOR_MAPB_IN_AG(x1, x2) = COLOR_MAPB_IN_AG(x2) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) SELECTA_IN_AGA(x1, x2, x3) = SELECTA_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x2, x3, x5) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x4, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x4, x5) MEMBERSC_IN_AG(x1, x2) = MEMBERSC_IN_AG(x2) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) MEMBERD_IN_AG(x1, x2) = MEMBERD_IN_AG(x2) U5_AG(x1, x2, x3, x4) = U5_AG(x2, x3, x4) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) U4_AG(x1, x2, x3, x4) = U4_AG(x3, x4) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (91) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes. ---------------------------------------- (92) Complex Obligation (AND) ---------------------------------------- (93) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERD_IN_AG(X1, .(X2, X3)) -> MEMBERD_IN_AG(X1, X3) The TRS R consists of the following rules: selectcA_in_aga(X1, .(X1, X2), X2) -> selectcA_out_aga(X1, .(X1, X2), X2) selectcA_in_aga(X1, .(X2, X3), .(X2, X4)) -> U12_aga(X1, X2, X3, X4, selectcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, selectcA_out_aga(X1, X3, X4)) -> selectcA_out_aga(X1, .(X2, X3), .(X2, X4)) membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) memberscC_in_ag(.(X1, X2), X3) -> U16_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U16_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> U17_ag(X1, X2, X3, memberscC_in_ag(X2, X3)) memberscC_in_ag([], X1) -> memberscC_out_ag([], X1) U17_ag(X1, X2, X3, memberscC_out_ag(X2, X3)) -> memberscC_out_ag(.(X1, X2), X3) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) selectcA_in_aga(x1, x2, x3) = selectcA_in_aga(x2) selectcA_out_aga(x1, x2, x3) = selectcA_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) memberscC_in_ag(x1, x2) = memberscC_in_ag(x2) U16_ag(x1, x2, x3, x4) = U16_ag(x3, x4) U17_ag(x1, x2, x3, x4) = U17_ag(x1, x3, x4) memberscC_out_ag(x1, x2) = memberscC_out_ag(x1, x2) MEMBERD_IN_AG(x1, x2) = MEMBERD_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (94) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (95) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERD_IN_AG(X1, .(X2, X3)) -> MEMBERD_IN_AG(X1, X3) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) MEMBERD_IN_AG(x1, x2) = MEMBERD_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (96) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERD_IN_AG(.(X2, X3)) -> MEMBERD_IN_AG(X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (98) 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: *MEMBERD_IN_AG(.(X2, X3)) -> MEMBERD_IN_AG(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (99) YES ---------------------------------------- (100) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERSC_IN_AG(.(X1, X2), X3) -> U3_AG(X1, X2, X3, membercD_in_ag(X1, X3)) U3_AG(X1, X2, X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X2, X3) The TRS R consists of the following rules: selectcA_in_aga(X1, .(X1, X2), X2) -> selectcA_out_aga(X1, .(X1, X2), X2) selectcA_in_aga(X1, .(X2, X3), .(X2, X4)) -> U12_aga(X1, X2, X3, X4, selectcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, selectcA_out_aga(X1, X3, X4)) -> selectcA_out_aga(X1, .(X2, X3), .(X2, X4)) membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) memberscC_in_ag(.(X1, X2), X3) -> U16_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U16_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> U17_ag(X1, X2, X3, memberscC_in_ag(X2, X3)) memberscC_in_ag([], X1) -> memberscC_out_ag([], X1) U17_ag(X1, X2, X3, memberscC_out_ag(X2, X3)) -> memberscC_out_ag(.(X1, X2), X3) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) selectcA_in_aga(x1, x2, x3) = selectcA_in_aga(x2) selectcA_out_aga(x1, x2, x3) = selectcA_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) memberscC_in_ag(x1, x2) = memberscC_in_ag(x2) U16_ag(x1, x2, x3, x4) = U16_ag(x3, x4) U17_ag(x1, x2, x3, x4) = U17_ag(x1, x3, x4) memberscC_out_ag(x1, x2) = memberscC_out_ag(x1, x2) MEMBERSC_IN_AG(x1, x2) = MEMBERSC_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (101) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (102) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERSC_IN_AG(.(X1, X2), X3) -> U3_AG(X1, X2, X3, membercD_in_ag(X1, X3)) U3_AG(X1, X2, X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X2, X3) The TRS R consists of the following rules: membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) MEMBERSC_IN_AG(x1, x2) = MEMBERSC_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(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: MEMBERSC_IN_AG(X3) -> U3_AG(X3, membercD_in_ag(X3)) U3_AG(X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X3) The TRS R consists of the following rules: membercD_in_ag(.(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(.(X2, X3)) -> U18_ag(X2, X3, membercD_in_ag(X3)) U18_ag(X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) The set Q consists of the following terms: membercD_in_ag(x0) U18_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (105) TransformationProof (SOUND) By narrowing [LPAR04] the rule MEMBERSC_IN_AG(X3) -> U3_AG(X3, membercD_in_ag(X3)) at position [1] we obtained the following new rules [LPAR04]: (MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), membercD_out_ag(x0, .(x0, x1))),MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), membercD_out_ag(x0, .(x0, x1)))) (MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), U18_ag(x0, x1, membercD_in_ag(x1))),MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), U18_ag(x0, x1, membercD_in_ag(x1)))) ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AG(X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X3) MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), membercD_out_ag(x0, .(x0, x1))) MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), U18_ag(x0, x1, membercD_in_ag(x1))) The TRS R consists of the following rules: membercD_in_ag(.(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(.(X2, X3)) -> U18_ag(X2, X3, membercD_in_ag(X3)) U18_ag(X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) The set Q consists of the following terms: membercD_in_ag(x0) U18_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (107) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U3_AG(X3, membercD_out_ag(X1, X3)) -> MEMBERSC_IN_AG(X3) we obtained the following new rules [LPAR04]: (U3_AG(.(z0, z1), membercD_out_ag(z0, .(z0, z1))) -> MEMBERSC_IN_AG(.(z0, z1)),U3_AG(.(z0, z1), membercD_out_ag(z0, .(z0, z1))) -> MEMBERSC_IN_AG(.(z0, z1))) (U3_AG(.(z0, z1), membercD_out_ag(x1, .(z0, z1))) -> MEMBERSC_IN_AG(.(z0, z1)),U3_AG(.(z0, z1), membercD_out_ag(x1, .(z0, z1))) -> MEMBERSC_IN_AG(.(z0, z1))) ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), membercD_out_ag(x0, .(x0, x1))) MEMBERSC_IN_AG(.(x0, x1)) -> U3_AG(.(x0, x1), U18_ag(x0, x1, membercD_in_ag(x1))) U3_AG(.(z0, z1), membercD_out_ag(z0, .(z0, z1))) -> MEMBERSC_IN_AG(.(z0, z1)) U3_AG(.(z0, z1), membercD_out_ag(x1, .(z0, z1))) -> MEMBERSC_IN_AG(.(z0, z1)) The TRS R consists of the following rules: membercD_in_ag(.(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(.(X2, X3)) -> U18_ag(X2, X3, membercD_in_ag(X3)) U18_ag(X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) The set Q consists of the following terms: membercD_in_ag(x0) U18_ag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (109) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECTA_IN_AGA(X1, .(X2, X3), .(X2, X4)) -> SELECTA_IN_AGA(X1, X3, X4) The TRS R consists of the following rules: selectcA_in_aga(X1, .(X1, X2), X2) -> selectcA_out_aga(X1, .(X1, X2), X2) selectcA_in_aga(X1, .(X2, X3), .(X2, X4)) -> U12_aga(X1, X2, X3, X4, selectcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, selectcA_out_aga(X1, X3, X4)) -> selectcA_out_aga(X1, .(X2, X3), .(X2, X4)) membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) memberscC_in_ag(.(X1, X2), X3) -> U16_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U16_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> U17_ag(X1, X2, X3, memberscC_in_ag(X2, X3)) memberscC_in_ag([], X1) -> memberscC_out_ag([], X1) U17_ag(X1, X2, X3, memberscC_out_ag(X2, X3)) -> memberscC_out_ag(.(X1, X2), X3) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) selectcA_in_aga(x1, x2, x3) = selectcA_in_aga(x2) selectcA_out_aga(x1, x2, x3) = selectcA_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) memberscC_in_ag(x1, x2) = memberscC_in_ag(x2) U16_ag(x1, x2, x3, x4) = U16_ag(x3, x4) U17_ag(x1, x2, x3, x4) = U17_ag(x1, x3, x4) memberscC_out_ag(x1, x2) = memberscC_out_ag(x1, x2) SELECTA_IN_AGA(x1, x2, x3) = SELECTA_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (110) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (111) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECTA_IN_AGA(X1, .(X2, X3), .(X2, X4)) -> SELECTA_IN_AGA(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) SELECTA_IN_AGA(x1, x2, x3) = SELECTA_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (112) Obligation: Pi DP problem: The TRS P consists of the following rules: COLOR_MAPB_IN_AG(.(region(X1, X2), X3), X4) -> U7_AG(X1, X2, X3, X4, selectcA_in_aga(X1, X4, X5)) U7_AG(X1, X2, X3, X4, selectcA_out_aga(X1, X4, X5)) -> U9_AG(X1, X2, X3, X4, memberscC_in_ag(X2, X5)) U9_AG(X1, X2, X3, X4, memberscC_out_ag(X2, X5)) -> COLOR_MAPB_IN_AG(X3, X4) The TRS R consists of the following rules: selectcA_in_aga(X1, .(X1, X2), X2) -> selectcA_out_aga(X1, .(X1, X2), X2) selectcA_in_aga(X1, .(X2, X3), .(X2, X4)) -> U12_aga(X1, X2, X3, X4, selectcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, selectcA_out_aga(X1, X3, X4)) -> selectcA_out_aga(X1, .(X2, X3), .(X2, X4)) membercD_in_ag(X1, .(X1, X2)) -> membercD_out_ag(X1, .(X1, X2)) membercD_in_ag(X1, .(X2, X3)) -> U18_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U18_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> membercD_out_ag(X1, .(X2, X3)) memberscC_in_ag(.(X1, X2), X3) -> U16_ag(X1, X2, X3, membercD_in_ag(X1, X3)) U16_ag(X1, X2, X3, membercD_out_ag(X1, X3)) -> U17_ag(X1, X2, X3, memberscC_in_ag(X2, X3)) memberscC_in_ag([], X1) -> memberscC_out_ag([], X1) U17_ag(X1, X2, X3, memberscC_out_ag(X2, X3)) -> memberscC_out_ag(.(X1, X2), X3) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) selectcA_in_aga(x1, x2, x3) = selectcA_in_aga(x2) selectcA_out_aga(x1, x2, x3) = selectcA_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) membercD_in_ag(x1, x2) = membercD_in_ag(x2) membercD_out_ag(x1, x2) = membercD_out_ag(x1, x2) U18_ag(x1, x2, x3, x4) = U18_ag(x2, x3, x4) memberscC_in_ag(x1, x2) = memberscC_in_ag(x2) U16_ag(x1, x2, x3, x4) = U16_ag(x3, x4) U17_ag(x1, x2, x3, x4) = U17_ag(x1, x3, x4) memberscC_out_ag(x1, x2) = memberscC_out_ag(x1, x2) COLOR_MAPB_IN_AG(x1, x2) = COLOR_MAPB_IN_AG(x2) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (113) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(color_map (. Region Regions) Colors)", "(',' (color_region Region Colors) (color_map Regions Colors))" ], [ "(color_map ([]) Colors)", null ], [ "(color_region (region Color Neighbors) Colors)", "(',' (select Color Colors Colors1) (members Neighbors Colors1))" ], [ "(select X (. X Xs) Xs)", null ], [ "(select X (. Y Ys) (. Y Zs))", "(select X Ys Zs)" ], [ "(members (. X Xs) Ys)", "(',' (member X Ys) (members Xs Ys))" ], [ "(members ([]) Ys)", null ], [ "(member X (. X X1))", null ], [ "(member X (. X2 T))", "(member X T)" ], [ "(test_color Name Pairs)", "(',' (colors Name Colors) (',' (color_map Map Colors) (',' (map Name Symbols Map) (symbols Symbols Map Pairs))))" ], [ "(symbols ([]) ([]) ([]))", null ], [ "(symbols (. S Ss) (. (region C N) Rs) (. (pair S C) Ps))", "(symbols Ss Rs Ps)" ], [ "(map (test) (. (a) (. (b) (. (c) (. (d) (. (e) (. (f) ([]))))))) (. (region A (. B (. C (. D ([]))))) (. (region B (. A (. C (. E ([]))))) (. (region C (. A (. B (. D (. E (. F ([]))))))) (. (region D (. A (. C (. F ([]))))) (. (region E (. B (. C (. F ([]))))) (. (region F (. C (. D (. E ([]))))) ([]))))))))", null ], [ "(map (west_europe) (. (portugal) (. (spain) (. (france) (. (belgium) (. (holland) (. (west_germany) (. (luxembourg) (. (italy) (. (switzerland) (. (austria) ([]))))))))))) (. (region P (. E ([]))) (. (region E (. F (. P ([])))) (. (region F (. E (. I (. S (. B (. WG (. L ([])))))))) (. (region B (. F (. H (. L (. WG ([])))))) (. (region H (. B (. WG ([])))) (. (region WG (. F (. A (. S (. H (. B (. L ([])))))))) (. (region L (. F (. B (. WG ([]))))) (. (region I (. F (. A (. S ([]))))) (. (region S (. F (. I (. A (. WG ([])))))) (. (region A (. I (. S (. WG ([]))))) ([]))))))))))))", null ], [ "(colors X (. (red) (. (yellow) (. (blue) (. (white) ([]))))))", null ] ] }, "graph": { "nodes": { "type": "Nodes", "450": { "goal": [{ "clause": 6, "scope": 4, "term": "(members T43 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "451": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T90 T89) (members T91 T89))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "452": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "696": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "115": { "goal": [{ "clause": 3, "scope": 3, "term": "(select T36 T35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "698": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T67 T66 X69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T66"], "free": ["X69"], "exprvars": [] } }, "678": { "goal": [ { "clause": 7, "scope": 5, "term": "(member T90 T89)" }, { "clause": 8, "scope": 5, "term": "(member T90 T89)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "711": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "712": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "119": { "goal": [{ "clause": 4, "scope": 3, "term": "(select T36 T35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "339": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "658": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T90 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "713": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (color_region T18 T17) (color_map T19 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "57": { "goal": [{ "clause": 2, "scope": 2, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "14": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (select T36 T35 X36) (members T37 X36))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T23 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "241": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "681": { "goal": [{ "clause": 7, "scope": 5, "term": "(member T90 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "682": { "goal": [{ "clause": 8, "scope": 5, "term": "(member T90 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "661": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T96 T89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T89"], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(color_map T1 T2)" }, { "clause": 1, "scope": 1, "term": "(color_map T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "700": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "448": { "goal": [ { "clause": 5, "scope": 4, "term": "(members T43 T42)" }, { "clause": 6, "scope": 4, "term": "(members T43 T42)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "701": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T120 T119)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T119"], "free": [], "exprvars": [] } }, "449": { "goal": [{ "clause": 5, "scope": 4, "term": "(members T43 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "702": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "82": { "goal": [ { "clause": 3, "scope": 3, "term": "(select T36 T35 X36)" }, { "clause": 4, "scope": 3, "term": "(select T36 T35 X36)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "63": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T36 T35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X36"], "exprvars": [] } }, "706": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T43 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T42"], "free": [], "exprvars": [] } }, "707": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "708": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 6, "label": "PARALLEL" }, { "from": 4, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 13, "label": "EVAL with clause\ncolor_map(.(X15, X16), X17) :- ','(color_region(X15, X17), color_map(X16, X17)).\nand substitutionX15 -> T18,\nX16 -> T19,\nT1 -> .(T18, T19),\nT2 -> T17,\nX17 -> T17,\nT15 -> T18,\nT16 -> T19" }, { "from": 6, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 711, "label": "EVAL with clause\ncolor_map([], X134).\nand substitutionT1 -> [],\nT2 -> T136,\nX134 -> T136" }, { "from": 7, "to": 712, "label": "EVAL-BACKTRACK" }, { "from": 13, "to": 16, "label": "SPLIT 1" }, { "from": 13, "to": 18, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT17 is ground\nreplacements:T19 -> T23" }, { "from": 16, "to": 57, "label": "CASE" }, { "from": 18, "to": 3, "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T17" }, { "from": 57, "to": 58, "label": "EVAL with clause\ncolor_region(region(X33, X34), X35) :- ','(select(X33, X35, X36), members(X34, X36)).\nand substitutionX33 -> T36,\nX34 -> T37,\nT18 -> region(T36, T37),\nT17 -> T35,\nX35 -> T35,\nT33 -> T36,\nT34 -> T37" }, { "from": 57, "to": 60, "label": "EVAL-BACKTRACK" }, { "from": 58, "to": 63, "label": "SPLIT 1" }, { "from": 58, "to": 64, "label": "SPLIT 2\nnew knowledge:\nT36 is ground\nT35 is ground\nT42 is ground\nreplacements:X36 -> T42,\nT37 -> T43" }, { "from": 63, "to": 82, "label": "CASE" }, { "from": 64, "to": 448, "label": "CASE" }, { "from": 82, "to": 115, "label": "PARALLEL" }, { "from": 82, "to": 119, "label": "PARALLEL" }, { "from": 115, "to": 224, "label": "EVAL with clause\nselect(X53, .(X53, X54), X54).\nand substitutionT36 -> T56,\nX53 -> T56,\nX54 -> T57,\nT35 -> .(T56, T57),\nX36 -> T57" }, { "from": 115, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 119, "to": 337, "label": "EVAL with clause\nselect(X65, .(X66, X67), .(X66, X68)) :- select(X65, X67, X68).\nand substitutionT36 -> T67,\nX65 -> T67,\nX66 -> T65,\nX67 -> T66,\nT35 -> .(T65, T66),\nX68 -> X69,\nX36 -> .(T65, X69),\nT64 -> T67" }, { "from": 119, "to": 339, "label": "EVAL-BACKTRACK" }, { "from": 224, "to": 241, "label": "SUCCESS" }, { "from": 337, "to": 63, "label": "INSTANCE with matching:\nT36 -> T67\nT35 -> T66\nX36 -> X69" }, { "from": 448, "to": 449, "label": "PARALLEL" }, { "from": 448, "to": 450, "label": "PARALLEL" }, { "from": 449, "to": 451, "label": "EVAL with clause\nmembers(.(X89, X90), X91) :- ','(member(X89, X91), members(X90, X91)).\nand substitutionX89 -> T90,\nX90 -> T91,\nT43 -> .(T90, T91),\nT42 -> T89,\nX91 -> T89,\nT87 -> T90,\nT88 -> T91" }, { "from": 449, "to": 452, "label": "EVAL-BACKTRACK" }, { "from": 450, "to": 706, "label": "EVAL with clause\nmembers([], X128).\nand substitutionT43 -> [],\nT42 -> T130,\nX128 -> T130" }, { "from": 450, "to": 707, "label": "EVAL-BACKTRACK" }, { "from": 451, "to": 658, "label": "SPLIT 1" }, { "from": 451, "to": 661, "label": "SPLIT 2\nnew knowledge:\nT90 is ground\nT89 is ground\nreplacements:T91 -> T96" }, { "from": 658, "to": 678, "label": "CASE" }, { "from": 661, "to": 64, "label": "INSTANCE with matching:\nT43 -> T96\nT42 -> T89" }, { "from": 678, "to": 681, "label": "PARALLEL" }, { "from": 678, "to": 682, "label": "PARALLEL" }, { "from": 681, "to": 696, "label": "EVAL with clause\nmember(X108, .(X108, X109)).\nand substitutionT90 -> T109,\nX108 -> T109,\nX109 -> T110,\nT89 -> .(T109, T110)" }, { "from": 681, "to": 698, "label": "EVAL-BACKTRACK" }, { "from": 682, "to": 701, "label": "EVAL with clause\nmember(X116, .(X117, X118)) :- member(X116, X118).\nand substitutionT90 -> T120,\nX116 -> T120,\nX117 -> T118,\nX118 -> T119,\nT89 -> .(T118, T119),\nT117 -> T120" }, { "from": 682, "to": 702, "label": "EVAL-BACKTRACK" }, { "from": 696, "to": 700, "label": "SUCCESS" }, { "from": 701, "to": 658, "label": "INSTANCE with matching:\nT90 -> T120\nT89 -> T119" }, { "from": 706, "to": 708, "label": "SUCCESS" }, { "from": 711, "to": 713, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (114) Complex Obligation (AND) ---------------------------------------- (115) Obligation: Rules: f658_in(T89) -> f678_in(T89) :|: TRUE f678_out(x) -> f658_out(x) :|: TRUE f702_out -> f682_out(x1) :|: TRUE f682_in(.(T118, T119)) -> f701_in(T119) :|: TRUE f701_out(x2) -> f682_out(.(x3, x2)) :|: TRUE f682_in(x4) -> f702_in :|: TRUE f681_out(x5) -> f678_out(x5) :|: TRUE f678_in(x6) -> f682_in(x6) :|: TRUE f678_in(x7) -> f681_in(x7) :|: TRUE f682_out(x8) -> f678_out(x8) :|: TRUE f658_out(x9) -> f701_out(x9) :|: TRUE f701_in(x10) -> f658_in(x10) :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x11) -> f4_in(x11) :|: TRUE f4_in(x12) -> f6_in(x12) :|: TRUE f7_out(x13) -> f4_out(x13) :|: TRUE f6_out(x14) -> f4_out(x14) :|: TRUE f4_in(x15) -> f7_in(x15) :|: TRUE f13_out(T17) -> f6_out(T17) :|: TRUE f6_in(x16) -> f14_in :|: TRUE f6_in(x17) -> f13_in(x17) :|: TRUE f14_out -> f6_out(x18) :|: TRUE f13_in(x19) -> f16_in(x19) :|: TRUE f18_out(x20) -> f13_out(x20) :|: TRUE f16_out(x21) -> f18_in(x21) :|: TRUE f57_out(x22) -> f16_out(x22) :|: TRUE f16_in(x23) -> f57_in(x23) :|: TRUE f58_out(T35) -> f57_out(T35) :|: TRUE f57_in(x24) -> f58_in(x24) :|: TRUE f57_in(x25) -> f60_in :|: TRUE f60_out -> f57_out(x26) :|: TRUE f58_in(x27) -> f63_in(x27) :|: TRUE f63_out(x28) -> f64_in(x29) :|: TRUE f64_out(x30) -> f58_out(x31) :|: TRUE f64_in(T42) -> f448_in(T42) :|: TRUE f448_out(x32) -> f64_out(x32) :|: TRUE f448_in(x33) -> f449_in(x33) :|: TRUE f448_in(x34) -> f450_in(x34) :|: TRUE f450_out(x35) -> f448_out(x35) :|: TRUE f449_out(x36) -> f448_out(x36) :|: TRUE f449_in(x37) -> f452_in :|: TRUE f451_out(x38) -> f449_out(x38) :|: TRUE f449_in(x39) -> f451_in(x39) :|: TRUE f452_out -> f449_out(x40) :|: TRUE f451_in(x41) -> f658_in(x41) :|: TRUE f658_out(x42) -> f661_in(x42) :|: TRUE f661_out(x43) -> f451_out(x43) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (116) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (117) TRUE ---------------------------------------- (118) Obligation: Rules: f681_out(T89) -> f678_out(T89) :|: TRUE f678_in(x) -> f682_in(x) :|: TRUE f678_in(x1) -> f681_in(x1) :|: TRUE f682_out(x2) -> f678_out(x2) :|: TRUE f451_in(x3) -> f658_in(x3) :|: TRUE f658_out(x4) -> f661_in(x4) :|: TRUE f661_out(x5) -> f451_out(x5) :|: TRUE f661_in(x6) -> f64_in(x6) :|: TRUE f64_out(x7) -> f661_out(x7) :|: TRUE f448_in(T42) -> f449_in(T42) :|: TRUE f448_in(x8) -> f450_in(x8) :|: TRUE f450_out(x9) -> f448_out(x9) :|: TRUE f449_out(x10) -> f448_out(x10) :|: TRUE f64_in(x11) -> f448_in(x11) :|: TRUE f448_out(x12) -> f64_out(x12) :|: TRUE f658_in(x13) -> f678_in(x13) :|: TRUE f678_out(x14) -> f658_out(x14) :|: TRUE f681_in(x15) -> f698_in :|: TRUE f698_out -> f681_out(x16) :|: TRUE f696_out -> f681_out(.(T109, T110)) :|: TRUE f681_in(.(x17, x18)) -> f696_in :|: TRUE f702_out -> f682_out(x19) :|: TRUE f682_in(.(T118, T119)) -> f701_in(T119) :|: TRUE f701_out(x20) -> f682_out(.(x21, x20)) :|: TRUE f682_in(x22) -> f702_in :|: TRUE f449_in(x23) -> f452_in :|: TRUE f451_out(x24) -> f449_out(x24) :|: TRUE f449_in(x25) -> f451_in(x25) :|: TRUE f452_out -> f449_out(x26) :|: TRUE f658_out(x27) -> f701_out(x27) :|: TRUE f701_in(x28) -> f658_in(x28) :|: TRUE f696_in -> f696_out :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x29) -> f4_in(x29) :|: TRUE f4_in(x30) -> f6_in(x30) :|: TRUE f7_out(x31) -> f4_out(x31) :|: TRUE f6_out(x32) -> f4_out(x32) :|: TRUE f4_in(x33) -> f7_in(x33) :|: TRUE f13_out(T17) -> f6_out(T17) :|: TRUE f6_in(x34) -> f14_in :|: TRUE f6_in(x35) -> f13_in(x35) :|: TRUE f14_out -> f6_out(x36) :|: TRUE f13_in(x37) -> f16_in(x37) :|: TRUE f18_out(x38) -> f13_out(x38) :|: TRUE f16_out(x39) -> f18_in(x39) :|: TRUE f57_out(x40) -> f16_out(x40) :|: TRUE f16_in(x41) -> f57_in(x41) :|: TRUE f58_out(T35) -> f57_out(T35) :|: TRUE f57_in(x42) -> f58_in(x42) :|: TRUE f57_in(x43) -> f60_in :|: TRUE f60_out -> f57_out(x44) :|: TRUE f58_in(x45) -> f63_in(x45) :|: TRUE f63_out(x46) -> f64_in(x47) :|: TRUE f64_out(x48) -> f58_out(x49) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (119) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (120) TRUE ---------------------------------------- (121) Obligation: Rules: f82_in(T35) -> f115_in(T35) :|: TRUE f82_in(x) -> f119_in(x) :|: TRUE f119_out(x1) -> f82_out(x1) :|: TRUE f115_out(x2) -> f82_out(x2) :|: TRUE f82_out(x3) -> f63_out(x3) :|: TRUE f63_in(x4) -> f82_in(x4) :|: TRUE f63_out(T66) -> f337_out(T66) :|: TRUE f337_in(x5) -> f63_in(x5) :|: TRUE f339_out -> f119_out(x6) :|: TRUE f119_in(.(x7, x8)) -> f337_in(x8) :|: TRUE f119_in(x9) -> f339_in :|: TRUE f337_out(x10) -> f119_out(.(x11, x10)) :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x12) -> f4_in(x12) :|: TRUE f4_in(x13) -> f6_in(x13) :|: TRUE f7_out(x14) -> f4_out(x14) :|: TRUE f6_out(x15) -> f4_out(x15) :|: TRUE f4_in(x16) -> f7_in(x16) :|: TRUE f13_out(T17) -> f6_out(T17) :|: TRUE f6_in(x17) -> f14_in :|: TRUE f6_in(x18) -> f13_in(x18) :|: TRUE f14_out -> f6_out(x19) :|: TRUE f13_in(x20) -> f16_in(x20) :|: TRUE f18_out(x21) -> f13_out(x21) :|: TRUE f16_out(x22) -> f18_in(x22) :|: TRUE f57_out(x23) -> f16_out(x23) :|: TRUE f16_in(x24) -> f57_in(x24) :|: TRUE f58_out(x25) -> f57_out(x25) :|: TRUE f57_in(x26) -> f58_in(x26) :|: TRUE f57_in(x27) -> f60_in :|: TRUE f60_out -> f57_out(x28) :|: TRUE f58_in(x29) -> f63_in(x29) :|: TRUE f63_out(x30) -> f64_in(x31) :|: TRUE f64_out(x32) -> f58_out(x33) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (122) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f82_in(x) -> f119_in(x) :|: TRUE f63_in(x4) -> f82_in(x4) :|: TRUE f337_in(x5) -> f63_in(x5) :|: TRUE f119_in(.(x7, x8)) -> f337_in(x8) :|: TRUE ---------------------------------------- (123) Obligation: Rules: f82_in(x) -> f119_in(x) :|: TRUE f63_in(x4) -> f82_in(x4) :|: TRUE f337_in(x5) -> f63_in(x5) :|: TRUE f119_in(.(x7, x8)) -> f337_in(x8) :|: TRUE ---------------------------------------- (124) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (125) Obligation: Rules: f337_in(.(x7:0, x8:0)) -> f337_in(x8:0) :|: TRUE ---------------------------------------- (126) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (127) Obligation: Rules: f337_in(.(x7:0, x8:0)) -> f337_in(x8:0) :|: TRUE ---------------------------------------- (128) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f337_in(.(x7:0, x8:0)) -> f337_in(x8:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (129) Obligation: Termination digraph: Nodes: (1) f337_in(.(x7:0, x8:0)) -> f337_in(x8:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (130) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (131) Obligation: Rules: f337_in(.(x8:0)) -> f337_in(x8:0) :|: TRUE ---------------------------------------- (132) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f337_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (133) Obligation: Rules: f337_in(.(x8:0)) -> f337_in(x8:0) ---------------------------------------- (134) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (135) Obligation: Q DP problem: The TRS P consists of the following rules: f337_in(.(x8:0)) -> f337_in(x8:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (136) 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: *f337_in(.(x8:0)) -> f337_in(x8:0) The graph contains the following edges 1 > 1 ---------------------------------------- (137) YES ---------------------------------------- (138) Obligation: Rules: f681_out(T89) -> f678_out(T89) :|: TRUE f678_in(x) -> f682_in(x) :|: TRUE f678_in(x1) -> f681_in(x1) :|: TRUE f682_out(x2) -> f678_out(x2) :|: TRUE f661_in(x3) -> f64_in(x3) :|: TRUE f64_out(x4) -> f661_out(x4) :|: TRUE f448_in(T42) -> f449_in(T42) :|: TRUE f448_in(x5) -> f450_in(x5) :|: TRUE f450_out(x6) -> f448_out(x6) :|: TRUE f449_out(x7) -> f448_out(x7) :|: TRUE f13_in(T17) -> f16_in(T17) :|: TRUE f18_out(x8) -> f13_out(x8) :|: TRUE f16_out(x9) -> f18_in(x9) :|: TRUE f658_in(x10) -> f678_in(x10) :|: TRUE f678_out(x11) -> f658_out(x11) :|: TRUE f234_out -> f115_out(T35) :|: TRUE f115_in(.(T56, T57)) -> f224_in :|: TRUE f224_out -> f115_out(.(x12, x13)) :|: TRUE f115_in(x14) -> f234_in :|: TRUE f224_in -> f224_out :|: TRUE f681_in(x15) -> f698_in :|: TRUE f698_out -> f681_out(x16) :|: TRUE f696_out -> f681_out(.(T109, T110)) :|: TRUE f681_in(.(x17, x18)) -> f696_in :|: TRUE f82_in(x19) -> f115_in(x19) :|: TRUE f82_in(x20) -> f119_in(x20) :|: TRUE f119_out(x21) -> f82_out(x21) :|: TRUE f115_out(x22) -> f82_out(x22) :|: TRUE f18_in(x23) -> f3_in(x23) :|: TRUE f3_out(x24) -> f18_out(x24) :|: TRUE f658_out(T119) -> f701_out(T119) :|: TRUE f701_in(x25) -> f658_in(x25) :|: TRUE f58_in(x26) -> f63_in(x26) :|: TRUE f63_out(x27) -> f64_in(x28) :|: TRUE f64_out(x29) -> f58_out(x30) :|: TRUE f339_out -> f119_out(x31) :|: TRUE f119_in(.(T65, T66)) -> f337_in(T66) :|: TRUE f119_in(x32) -> f339_in :|: TRUE f337_out(x33) -> f119_out(.(x34, x33)) :|: TRUE f58_out(x35) -> f57_out(x35) :|: TRUE f57_in(x36) -> f58_in(x36) :|: TRUE f57_in(x37) -> f60_in :|: TRUE f60_out -> f57_out(x38) :|: TRUE f63_out(x39) -> f337_out(x39) :|: TRUE f337_in(x40) -> f63_in(x40) :|: TRUE f451_in(x41) -> f658_in(x41) :|: TRUE f658_out(x42) -> f661_in(x42) :|: TRUE f661_out(x43) -> f451_out(x43) :|: TRUE f706_in -> f706_out :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x44) -> f4_in(x44) :|: TRUE f57_out(x45) -> f16_out(x45) :|: TRUE f16_in(x46) -> f57_in(x46) :|: TRUE f64_in(x47) -> f448_in(x47) :|: TRUE f448_out(x48) -> f64_out(x48) :|: TRUE f4_in(x49) -> f6_in(x49) :|: TRUE f7_out(x50) -> f4_out(x50) :|: TRUE f6_out(x51) -> f4_out(x51) :|: TRUE f4_in(x52) -> f7_in(x52) :|: TRUE f82_out(x53) -> f63_out(x53) :|: TRUE f63_in(x54) -> f82_in(x54) :|: TRUE f702_out -> f682_out(x55) :|: TRUE f682_in(.(x56, x57)) -> f701_in(x57) :|: TRUE f701_out(x58) -> f682_out(.(x59, x58)) :|: TRUE f682_in(x60) -> f702_in :|: TRUE f13_out(x61) -> f6_out(x61) :|: TRUE f6_in(x62) -> f14_in :|: TRUE f6_in(x63) -> f13_in(x63) :|: TRUE f14_out -> f6_out(x64) :|: TRUE f449_in(x65) -> f452_in :|: TRUE f451_out(x66) -> f449_out(x66) :|: TRUE f449_in(x67) -> f451_in(x67) :|: TRUE f452_out -> f449_out(x68) :|: TRUE f706_out -> f450_out(T130) :|: TRUE f707_out -> f450_out(x69) :|: TRUE f450_in(x70) -> f706_in :|: TRUE f450_in(x71) -> f707_in :|: TRUE f696_in -> f696_out :|: TRUE Start term: f3_in(T2) ---------------------------------------- (139) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f681_out(T89) -> f678_out(T89) :|: TRUE f678_in(x) -> f682_in(x) :|: TRUE f678_in(x1) -> f681_in(x1) :|: TRUE f682_out(x2) -> f678_out(x2) :|: TRUE f661_in(x3) -> f64_in(x3) :|: TRUE f64_out(x4) -> f661_out(x4) :|: TRUE f448_in(T42) -> f449_in(T42) :|: TRUE f448_in(x5) -> f450_in(x5) :|: TRUE f450_out(x6) -> f448_out(x6) :|: TRUE f449_out(x7) -> f448_out(x7) :|: TRUE f13_in(T17) -> f16_in(T17) :|: TRUE f16_out(x9) -> f18_in(x9) :|: TRUE f658_in(x10) -> f678_in(x10) :|: TRUE f678_out(x11) -> f658_out(x11) :|: TRUE f115_in(.(T56, T57)) -> f224_in :|: TRUE f224_out -> f115_out(.(x12, x13)) :|: TRUE f224_in -> f224_out :|: TRUE f696_out -> f681_out(.(T109, T110)) :|: TRUE f681_in(.(x17, x18)) -> f696_in :|: TRUE f82_in(x19) -> f115_in(x19) :|: TRUE f82_in(x20) -> f119_in(x20) :|: TRUE f119_out(x21) -> f82_out(x21) :|: TRUE f115_out(x22) -> f82_out(x22) :|: TRUE f18_in(x23) -> f3_in(x23) :|: TRUE f658_out(T119) -> f701_out(T119) :|: TRUE f701_in(x25) -> f658_in(x25) :|: TRUE f58_in(x26) -> f63_in(x26) :|: TRUE f63_out(x27) -> f64_in(x28) :|: TRUE f64_out(x29) -> f58_out(x30) :|: TRUE f119_in(.(T65, T66)) -> f337_in(T66) :|: TRUE f337_out(x33) -> f119_out(.(x34, x33)) :|: TRUE f58_out(x35) -> f57_out(x35) :|: TRUE f57_in(x36) -> f58_in(x36) :|: TRUE f63_out(x39) -> f337_out(x39) :|: TRUE f337_in(x40) -> f63_in(x40) :|: TRUE f451_in(x41) -> f658_in(x41) :|: TRUE f658_out(x42) -> f661_in(x42) :|: TRUE f661_out(x43) -> f451_out(x43) :|: TRUE f706_in -> f706_out :|: TRUE f3_in(x44) -> f4_in(x44) :|: TRUE f57_out(x45) -> f16_out(x45) :|: TRUE f16_in(x46) -> f57_in(x46) :|: TRUE f64_in(x47) -> f448_in(x47) :|: TRUE f448_out(x48) -> f64_out(x48) :|: TRUE f4_in(x49) -> f6_in(x49) :|: TRUE f82_out(x53) -> f63_out(x53) :|: TRUE f63_in(x54) -> f82_in(x54) :|: TRUE f682_in(.(x56, x57)) -> f701_in(x57) :|: TRUE f701_out(x58) -> f682_out(.(x59, x58)) :|: TRUE f6_in(x63) -> f13_in(x63) :|: TRUE f451_out(x66) -> f449_out(x66) :|: TRUE f449_in(x67) -> f451_in(x67) :|: TRUE f706_out -> f450_out(T130) :|: TRUE f450_in(x70) -> f706_in :|: TRUE f696_in -> f696_out :|: TRUE ---------------------------------------- (140) Obligation: Rules: f681_out(T89) -> f678_out(T89) :|: TRUE f678_in(x) -> f682_in(x) :|: TRUE f678_in(x1) -> f681_in(x1) :|: TRUE f682_out(x2) -> f678_out(x2) :|: TRUE f661_in(x3) -> f64_in(x3) :|: TRUE f64_out(x4) -> f661_out(x4) :|: TRUE f448_in(T42) -> f449_in(T42) :|: TRUE f448_in(x5) -> f450_in(x5) :|: TRUE f450_out(x6) -> f448_out(x6) :|: TRUE f449_out(x7) -> f448_out(x7) :|: TRUE f13_in(T17) -> f16_in(T17) :|: TRUE f16_out(x9) -> f18_in(x9) :|: TRUE f658_in(x10) -> f678_in(x10) :|: TRUE f678_out(x11) -> f658_out(x11) :|: TRUE f115_in(.(T56, T57)) -> f224_in :|: TRUE f224_out -> f115_out(.(x12, x13)) :|: TRUE f224_in -> f224_out :|: TRUE f696_out -> f681_out(.(T109, T110)) :|: TRUE f681_in(.(x17, x18)) -> f696_in :|: TRUE f82_in(x19) -> f115_in(x19) :|: TRUE f82_in(x20) -> f119_in(x20) :|: TRUE f119_out(x21) -> f82_out(x21) :|: TRUE f115_out(x22) -> f82_out(x22) :|: TRUE f18_in(x23) -> f3_in(x23) :|: TRUE f658_out(T119) -> f701_out(T119) :|: TRUE f701_in(x25) -> f658_in(x25) :|: TRUE f58_in(x26) -> f63_in(x26) :|: TRUE f63_out(x27) -> f64_in(x28) :|: TRUE f64_out(x29) -> f58_out(x30) :|: TRUE f119_in(.(T65, T66)) -> f337_in(T66) :|: TRUE f337_out(x33) -> f119_out(.(x34, x33)) :|: TRUE f58_out(x35) -> f57_out(x35) :|: TRUE f57_in(x36) -> f58_in(x36) :|: TRUE f63_out(x39) -> f337_out(x39) :|: TRUE f337_in(x40) -> f63_in(x40) :|: TRUE f451_in(x41) -> f658_in(x41) :|: TRUE f658_out(x42) -> f661_in(x42) :|: TRUE f661_out(x43) -> f451_out(x43) :|: TRUE f706_in -> f706_out :|: TRUE f3_in(x44) -> f4_in(x44) :|: TRUE f57_out(x45) -> f16_out(x45) :|: TRUE f16_in(x46) -> f57_in(x46) :|: TRUE f64_in(x47) -> f448_in(x47) :|: TRUE f448_out(x48) -> f64_out(x48) :|: TRUE f4_in(x49) -> f6_in(x49) :|: TRUE f82_out(x53) -> f63_out(x53) :|: TRUE f63_in(x54) -> f82_in(x54) :|: TRUE f682_in(.(x56, x57)) -> f701_in(x57) :|: TRUE f701_out(x58) -> f682_out(.(x59, x58)) :|: TRUE f6_in(x63) -> f13_in(x63) :|: TRUE f451_out(x66) -> f449_out(x66) :|: TRUE f449_in(x67) -> f451_in(x67) :|: TRUE f706_out -> f450_out(T130) :|: TRUE f450_in(x70) -> f706_in :|: TRUE f696_in -> f696_out :|: TRUE ---------------------------------------- (141) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (142) Obligation: Rules: f658_out(x42:0) -> f448_in(x42:0) :|: TRUE f63_out(x27:0) -> f448_in(x28:0) :|: TRUE f658_in(.(x56:0, x57:0)) -> f658_in(x57:0) :|: TRUE f63_out(x39:0) -> f63_out(.(x34:0, x39:0)) :|: TRUE f82_in(.(T56:0, T57:0)) -> f63_out(.(x12:0, x13:0)) :|: TRUE f64_out(x4:0) -> f64_out(x4:0) :|: TRUE f82_in(.(T65:0, T66:0)) -> f82_in(T66:0) :|: TRUE f658_out(T119:0) -> f658_out(.(x59:0, T119:0)) :|: TRUE f448_in(x5:0) -> f64_out(T130:0) :|: TRUE f658_in(.(x17:0, x18:0)) -> f658_out(.(T109:0, T110:0)) :|: TRUE f64_out(x29:0) -> f82_in(x30:0) :|: TRUE f448_in(T42:0) -> f658_in(T42:0) :|: TRUE ---------------------------------------- (143) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (144) Obligation: Rules: f658_out(x42:0) -> f448_in(x42:0) :|: TRUE f63_out(x27:0) -> f448_in(x28:0) :|: TRUE f658_in(.(x56:0, x57:0)) -> f658_in(x57:0) :|: TRUE f63_out(x39:0) -> f63_out(.(x34:0, x39:0)) :|: TRUE f82_in(.(T56:0, T57:0)) -> f63_out(.(x12:0, x13:0)) :|: TRUE f64_out(x4:0) -> f64_out(x4:0) :|: TRUE f82_in(.(T65:0, T66:0)) -> f82_in(T66:0) :|: TRUE f658_out(T119:0) -> f658_out(.(x59:0, T119:0)) :|: TRUE f448_in(x5:0) -> f64_out(T130:0) :|: TRUE f658_in(.(x17:0, x18:0)) -> f658_out(.(T109:0, T110:0)) :|: TRUE f64_out(x29:0) -> f82_in(x30:0) :|: TRUE f448_in(T42:0) -> f658_in(T42:0) :|: TRUE ---------------------------------------- (145) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f658_out(x42:0) -> f448_in(x42:0) :|: TRUE (2) f63_out(x27:0) -> f448_in(x28:0) :|: TRUE (3) f658_in(.(x56:0, x57:0)) -> f658_in(x57:0) :|: TRUE (4) f63_out(x39:0) -> f63_out(.(x34:0, x39:0)) :|: TRUE (5) f82_in(.(T56:0, T57:0)) -> f63_out(.(x12:0, x13:0)) :|: TRUE (6) f64_out(x4:0) -> f64_out(x4:0) :|: TRUE (7) f82_in(.(T65:0, T66:0)) -> f82_in(T66:0) :|: TRUE (8) f658_out(T119:0) -> f658_out(.(x59:0, T119:0)) :|: TRUE (9) f448_in(x5:0) -> f64_out(T130:0) :|: TRUE (10) f658_in(.(x17:0, x18:0)) -> f658_out(.(T109:0, T110:0)) :|: TRUE (11) f64_out(x29:0) -> f82_in(x30:0) :|: TRUE (12) f448_in(T42:0) -> f658_in(T42:0) :|: TRUE Arcs: (1) -> (9), (12) (2) -> (9), (12) (3) -> (3), (10) (4) -> (2), (4) (5) -> (2), (4) (6) -> (6), (11) (7) -> (5), (7) (8) -> (1), (8) (9) -> (6), (11) (10) -> (1), (8) (11) -> (5), (7) (12) -> (3), (10) This digraph is fully evaluated! ---------------------------------------- (146) Obligation: Termination digraph: Nodes: (1) f658_out(x42:0) -> f448_in(x42:0) :|: TRUE (2) f658_out(T119:0) -> f658_out(.(x59:0, T119:0)) :|: TRUE (3) f658_in(.(x17:0, x18:0)) -> f658_out(.(T109:0, T110:0)) :|: TRUE (4) f658_in(.(x56:0, x57:0)) -> f658_in(x57:0) :|: TRUE (5) f448_in(T42:0) -> f658_in(T42:0) :|: TRUE (6) f63_out(x27:0) -> f448_in(x28:0) :|: TRUE (7) f63_out(x39:0) -> f63_out(.(x34:0, x39:0)) :|: TRUE (8) f82_in(.(T56:0, T57:0)) -> f63_out(.(x12:0, x13:0)) :|: TRUE (9) f82_in(.(T65:0, T66:0)) -> f82_in(T66:0) :|: TRUE (10) f64_out(x29:0) -> f82_in(x30:0) :|: TRUE (11) f64_out(x4:0) -> f64_out(x4:0) :|: TRUE (12) f448_in(x5:0) -> f64_out(T130:0) :|: TRUE Arcs: (1) -> (5), (12) (2) -> (1), (2) (3) -> (1), (2) (4) -> (3), (4) (5) -> (3), (4) (6) -> (5), (12) (7) -> (6), (7) (8) -> (6), (7) (9) -> (8), (9) (10) -> (8), (9) (11) -> (10), (11) (12) -> (10), (11) This digraph is fully evaluated! ---------------------------------------- (147) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (148) Obligation: Rules: f658_out(x42:0) -> f448_in(x42:0) :|: TRUE f658_out(T119:0) -> f658_out(.(T119:0)) :|: TRUE f658_in(.(x18:0)) -> f658_out(.(T110:0)) :|: TRUE f658_in(.(x57:0)) -> f658_in(x57:0) :|: TRUE f448_in(T42:0) -> f658_in(T42:0) :|: TRUE f63_out(x27:0) -> f448_in(x28:0) :|: TRUE f63_out(x39:0) -> f63_out(.(x39:0)) :|: TRUE f82_in(.(T57:0)) -> f63_out(.(x13:0)) :|: TRUE f82_in(.(T66:0)) -> f82_in(T66:0) :|: TRUE f64_out(x29:0) -> f82_in(x30:0) :|: TRUE f64_out(x4:0) -> f64_out(x4:0) :|: TRUE f448_in(x5:0) -> f64_out(T130:0) :|: TRUE ---------------------------------------- (149) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (150) Obligation: Rules: f658_out(x) -> f448_in(x) :|: TRUE f658_out(x1) -> f658_out(.(x1)) :|: TRUE f658_in(.(x2)) -> f658_out(.(x3)) :|: TRUE f658_in(.(x4)) -> f658_in(x4) :|: TRUE f448_in(x5) -> f658_in(x5) :|: TRUE f63_out(x6) -> f448_in(x7) :|: TRUE f63_out(x8) -> f63_out(.(x8)) :|: TRUE f82_in(.(x9)) -> f63_out(.(x10)) :|: TRUE f82_in(.(x11)) -> f82_in(x11) :|: TRUE f64_out(x12) -> f82_in(x13) :|: TRUE f64_out(x14) -> f64_out(x14) :|: TRUE f448_in(x15) -> f64_out(x16) :|: TRUE