/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern 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, 6 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, 35 ms] (66) QTRS (67) DependencyPairsProof [EQUIVALENT, 0 ms] (68) QDP (69) DependencyGraphProof [EQUIVALENT, 0 ms] (70) AND (71) QDP (72) UsableRulesProof [EQUIVALENT, 1 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, 53 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, 0 ms] (125) IRSwT (126) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (127) IRSwT (128) IRSwTTerminationDigraphProof [EQUIVALENT, 7 ms] (129) IRSwT (130) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (131) IRSwT (132) TempFilterProof [SOUND, 2 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, 24 ms] (142) IRSwT (143) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (144) IRSwT (145) IRSwTTerminationDigraphProof [EQUIVALENT, 64 ms] (146) IRSwT (147) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (148) IRSwT ---------------------------------------- (0) Obligation: Clauses: color_map(.(Region, Regions), Colors) :- ','(color_region(Region, Colors), color_map(Regions, Colors)). color_map([], Colors). color_region(region(Name, 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, Map) :- ','(map(Name, Map), ','(colors(Name, Colors), color_map(Map, Colors))). map(test, .(region(a, A, .(B, .(C, .(D, [])))), .(region(b, B, .(A, .(C, .(E, [])))), .(region(c, C, .(A, .(B, .(D, .(E, .(F, [])))))), .(region(d, D, .(A, .(C, .(F, [])))), .(region(e, E, .(B, .(C, .(F, [])))), .(region(f, F, .(C, .(D, .(E, [])))), []))))))). map(west_europe, .(region(portugal, P, .(E, [])), .(region(spain, E, .(F, .(P, []))), .(region(france, F, .(E, .(I, .(S, .(B, .(WG, .(L, []))))))), .(region(belgium, B, .(F, .(H, .(L, .(WG, []))))), .(region(holland, H, .(B, .(WG, []))), .(region(west_germany, WG, .(F, .(A, .(S, .(H, .(B, .(L, []))))))), .(region(luxembourg, L, .(F, .(B, .(WG, [])))), .(region(italy, I, .(F, .(A, .(S, [])))), .(region(switzerland, S, .(F, .(I, .(A, .(WG, []))))), .(region(austria, 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) ---------------------------------------- (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(Name, Color, Neighbors), Colors) -> U3_AG(Name, Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Name, Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Name, 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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, x5) = U3_AG(x5) 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, x5) = U4_AG(x2, x5) 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(Name, Color, Neighbors), Colors) -> U3_AG(Name, Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Name, Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Name, 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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, x5) = U3_AG(x5) 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, x5) = U4_AG(x2, x5) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x4) color_map_out_ag(x1, x2) = color_map_out_ag(x1) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) U3_ag(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x5) 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, x5) = U4_ag(x2, x5) 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, x3) = region(x2, x3) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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(Name, Color, Neighbors), Colors) -> U3_AG(Name, Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Name, Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Name, 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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, x5) = U3_AG(x4, x5) 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, x5) = U4_AG(x2, x4, x5) 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(Name, Color, Neighbors), Colors) -> U3_AG(Name, Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) COLOR_REGION_IN_AG(region(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_AG(Name, Color, Neighbors, Colors, members_in_ag(Neighbors, Colors1)) U3_AG(Name, 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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, x5) = U3_AG(x4, x5) 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, x5) = U4_AG(x2, x4, x5) 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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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(Name, Color, Neighbors), Colors) -> U3_ag(Name, 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(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) color_map_out_ag(x1, x2) = color_map_out_ag(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(Name, Color, Neighbors), Colors) -> U3_ag(Name, Color, Neighbors, Colors, select_in_aga(Color, Colors, Colors1)) U3_ag(Name, Color, Neighbors, Colors, select_out_aga(Color, Colors, Colors1)) -> U4_ag(Name, 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(Name, Color, Neighbors, Colors, members_out_ag(Neighbors, Colors1)) -> color_region_out_ag(region(Name, 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, x5) = U3_ag(x4, x5) 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, x5) = U4_ag(x2, x4, x5) 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, x3) = region(x2, x3) 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": 3, "program": { "directives": [], "clauses": [ [ "(color_map (. Region Regions) Colors)", "(',' (color_region Region Colors) (color_map Regions Colors))" ], [ "(color_map ([]) Colors)", null ], [ "(color_region (region Name 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 Map)", "(',' (map Name Map) (',' (colors Name Colors) (color_map Map Colors)))" ], [ "(map (test) (. (region (a) A (. B (. C (. D ([]))))) (. (region (b) B (. A (. C (. E ([]))))) (. (region (c) C (. A (. B (. D (. E (. F ([]))))))) (. (region (d) D (. A (. C (. F ([]))))) (. (region (e) E (. B (. C (. F ([]))))) (. (region (f) F (. C (. D (. E ([]))))) ([]))))))))", null ], [ "(map (west_europe) (. (region (portugal) P (. E ([]))) (. (region (spain) E (. F (. P ([])))) (. (region (france) F (. E (. I (. S (. B (. WG (. L ([])))))))) (. (region (belgium) B (. F (. H (. L (. WG ([])))))) (. (region (holland) H (. B (. WG ([])))) (. (region (west_germany) WG (. F (. A (. S (. H (. B (. L ([])))))))) (. (region (luxembourg) L (. F (. B (. WG ([]))))) (. (region (italy) I (. F (. A (. S ([]))))) (. (region (switzerland) S (. F (. I (. A (. WG ([])))))) (. (region (austria) A (. I (. S (. WG ([]))))) ([]))))))))))))", null ], [ "(colors X (. (red) (. (yellow) (. (blue) (. (white) ([]))))))", null ] ] }, "graph": { "nodes": { "66": { "goal": [{ "clause": 0, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "67": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "571": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "550": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "572": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "331": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "551": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "299": { "goal": [ { "clause": 3, "scope": 3, "term": "(select T41 T40 X41)" }, { "clause": 4, "scope": 3, "term": "(select T41 T40 X41)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "310": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "552": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T101 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "553": { "goal": [ { "clause": 7, "scope": 5, "term": "(member T95 T94)" }, { "clause": 8, "scope": 5, "term": "(member T95 T94)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "257": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (select T41 T40 X41) (members T42 X41))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "576": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T125 T124)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T124"], "free": [], "exprvars": [] } }, "555": { "goal": [{ "clause": 7, "scope": 5, "term": "(member T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "577": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "556": { "goal": [{ "clause": 8, "scope": 5, "term": "(member T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "117": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T72 T71 X74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": ["X74"], "exprvars": [] } }, "160": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "281": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T41 T40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "161": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T24 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "284": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T48 T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "263": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "188": { "goal": [{ "clause": 2, "scope": 2, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "620": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "621": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "303": { "goal": [{ "clause": 3, "scope": 3, "term": "(select T41 T40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "622": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "304": { "goal": [{ "clause": 4, "scope": 3, "term": "(select T41 T40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "546": { "goal": [ { "clause": 5, "scope": 4, "term": "(members T48 T47)" }, { "clause": 6, "scope": 4, "term": "(members T48 T47)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "568": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "623": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "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": [] } }, "107": { "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": [] } }, "305": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "547": { "goal": [{ "clause": 5, "scope": 4, "term": "(members T48 T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "624": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "306": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "548": { "goal": [{ "clause": 6, "scope": 4, "term": "(members T48 T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "625": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "549": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T95 T94) (members T96 T94))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 8, "label": "CASE" }, { "from": 8, "to": 66, "label": "PARALLEL" }, { "from": 8, "to": 67, "label": "PARALLEL" }, { "from": 66, "to": 107, "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": 66, "to": 117, "label": "EVAL-BACKTRACK" }, { "from": 67, "to": 623, "label": "EVAL with clause\ncolor_map([], X139).\nand substitutionT1 -> [],\nT2 -> T141,\nX139 -> T141" }, { "from": 67, "to": 624, "label": "EVAL-BACKTRACK" }, { "from": 107, "to": 160, "label": "SPLIT 1" }, { "from": 107, "to": 161, "label": "SPLIT 2\nnew knowledge:\nT17 is ground\nreplacements:T19 -> T24" }, { "from": 160, "to": 188, "label": "CASE" }, { "from": 161, "to": 3, "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> T17" }, { "from": 188, "to": 257, "label": "EVAL with clause\ncolor_region(region(X37, X38, X39), X40) :- ','(select(X38, X40, X41), members(X39, X41)).\nand substitutionX37 -> T37,\nX38 -> T41,\nX39 -> T42,\nT18 -> region(T37, T41, T42),\nT17 -> T40,\nX40 -> T40,\nT38 -> T41,\nT39 -> T42" }, { "from": 188, "to": 263, "label": "EVAL-BACKTRACK" }, { "from": 257, "to": 281, "label": "SPLIT 1" }, { "from": 257, "to": 284, "label": "SPLIT 2\nnew knowledge:\nT41 is ground\nT40 is ground\nT47 is ground\nreplacements:X41 -> T47,\nT42 -> T48" }, { "from": 281, "to": 299, "label": "CASE" }, { "from": 284, "to": 546, "label": "CASE" }, { "from": 299, "to": 303, "label": "PARALLEL" }, { "from": 299, "to": 304, "label": "PARALLEL" }, { "from": 303, "to": 305, "label": "EVAL with clause\nselect(X58, .(X58, X59), X59).\nand substitutionT41 -> T61,\nX58 -> T61,\nX59 -> T62,\nT40 -> .(T61, T62),\nX41 -> T62" }, { "from": 303, "to": 306, "label": "EVAL-BACKTRACK" }, { "from": 304, "to": 319, "label": "EVAL with clause\nselect(X70, .(X71, X72), .(X71, X73)) :- select(X70, X72, X73).\nand substitutionT41 -> T72,\nX70 -> T72,\nX71 -> T70,\nX72 -> T71,\nT40 -> .(T70, T71),\nX73 -> X74,\nX41 -> .(T70, X74),\nT69 -> T72" }, { "from": 304, "to": 331, "label": "EVAL-BACKTRACK" }, { "from": 305, "to": 310, "label": "SUCCESS" }, { "from": 319, "to": 281, "label": "INSTANCE with matching:\nT41 -> T72\nT40 -> T71\nX41 -> X74" }, { "from": 546, "to": 547, "label": "PARALLEL" }, { "from": 546, "to": 548, "label": "PARALLEL" }, { "from": 547, "to": 549, "label": "EVAL with clause\nmembers(.(X94, X95), X96) :- ','(member(X94, X96), members(X95, X96)).\nand substitutionX94 -> T95,\nX95 -> T96,\nT48 -> .(T95, T96),\nT47 -> T94,\nX96 -> T94,\nT92 -> T95,\nT93 -> T96" }, { "from": 547, "to": 550, "label": "EVAL-BACKTRACK" }, { "from": 548, "to": 620, "label": "EVAL with clause\nmembers([], X133).\nand substitutionT48 -> [],\nT47 -> T135,\nX133 -> T135" }, { "from": 548, "to": 621, "label": "EVAL-BACKTRACK" }, { "from": 549, "to": 551, "label": "SPLIT 1" }, { "from": 549, "to": 552, "label": "SPLIT 2\nnew knowledge:\nT95 is ground\nT94 is ground\nreplacements:T96 -> T101" }, { "from": 551, "to": 553, "label": "CASE" }, { "from": 552, "to": 284, "label": "INSTANCE with matching:\nT48 -> T101\nT47 -> T94" }, { "from": 553, "to": 555, "label": "PARALLEL" }, { "from": 553, "to": 556, "label": "PARALLEL" }, { "from": 555, "to": 568, "label": "EVAL with clause\nmember(X113, .(X113, X114)).\nand substitutionT95 -> T114,\nX113 -> T114,\nX114 -> T115,\nT94 -> .(T114, T115)" }, { "from": 555, "to": 571, "label": "EVAL-BACKTRACK" }, { "from": 556, "to": 576, "label": "EVAL with clause\nmember(X121, .(X122, X123)) :- member(X121, X123).\nand substitutionT95 -> T125,\nX121 -> T125,\nX122 -> T123,\nX123 -> T124,\nT94 -> .(T123, T124),\nT122 -> T125" }, { "from": 556, "to": 577, "label": "EVAL-BACKTRACK" }, { "from": 568, "to": 572, "label": "SUCCESS" }, { "from": 576, "to": 551, "label": "INSTANCE with matching:\nT95 -> T125\nT94 -> T124" }, { "from": 620, "to": 622, "label": "SUCCESS" }, { "from": 623, "to": 625, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (66) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in(T17) -> U1(f107_in(T17), T17) U1(f107_out1, T17) -> f3_out1 f3_in(T141) -> f3_out1 f281_in(.(T61, T62)) -> f281_out1(T61, T62) f281_in(.(T70, T71)) -> U2(f281_in(T71), .(T70, T71)) U2(f281_out1(T72, X74), .(T70, T71)) -> f281_out1(T72, .(T70, X74)) f284_in(T94) -> U3(f549_in(T94), T94) U3(f549_out1(T95, T96), T94) -> f284_out1(.(T95, T96)) f284_in(T135) -> f284_out1([]) f551_in(.(T114, T115)) -> f551_out1(T114) f551_in(.(T123, T124)) -> U4(f551_in(T124), .(T123, T124)) U4(f551_out1(T125), .(T123, T124)) -> f551_out1(T125) f160_in(T40) -> U5(f257_in(T40), T40) U5(f257_out1(T41, X41, T42), T40) -> f160_out1 f107_in(T17) -> U6(f160_in(T17), T17) U6(f160_out1, T17) -> U7(f3_in(T17), T17) U7(f3_out1, T17) -> f107_out1 f257_in(T40) -> U8(f281_in(T40), T40) U8(f281_out1(T41, T47), T40) -> U9(f284_in(T47), T40, T41, T47) U9(f284_out1(T48), T40, T41, T47) -> f257_out1(T41, T47, T48) f549_in(T94) -> U10(f551_in(T94), T94) U10(f551_out1(T95), T94) -> U11(f284_in(T94), T94, T95) U11(f284_out1(T101), T94, T95) -> f549_out1(T95, T101) 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: F3_IN(T17) -> U1^1(f107_in(T17), T17) F3_IN(T17) -> F107_IN(T17) F281_IN(.(T70, T71)) -> U2^1(f281_in(T71), .(T70, T71)) F281_IN(.(T70, T71)) -> F281_IN(T71) F284_IN(T94) -> U3^1(f549_in(T94), T94) F284_IN(T94) -> F549_IN(T94) F551_IN(.(T123, T124)) -> U4^1(f551_in(T124), .(T123, T124)) F551_IN(.(T123, T124)) -> F551_IN(T124) F160_IN(T40) -> U5^1(f257_in(T40), T40) F160_IN(T40) -> F257_IN(T40) F107_IN(T17) -> U6^1(f160_in(T17), T17) F107_IN(T17) -> F160_IN(T17) U6^1(f160_out1, T17) -> U7^1(f3_in(T17), T17) U6^1(f160_out1, T17) -> F3_IN(T17) F257_IN(T40) -> U8^1(f281_in(T40), T40) F257_IN(T40) -> F281_IN(T40) U8^1(f281_out1(T41, T47), T40) -> U9^1(f284_in(T47), T40, T41, T47) U8^1(f281_out1(T41, T47), T40) -> F284_IN(T47) F549_IN(T94) -> U10^1(f551_in(T94), T94) F549_IN(T94) -> F551_IN(T94) U10^1(f551_out1(T95), T94) -> U11^1(f284_in(T94), T94, T95) U10^1(f551_out1(T95), T94) -> F284_IN(T94) The TRS R consists of the following rules: f3_in(T17) -> U1(f107_in(T17), T17) U1(f107_out1, T17) -> f3_out1 f3_in(T141) -> f3_out1 f281_in(.(T61, T62)) -> f281_out1(T61, T62) f281_in(.(T70, T71)) -> U2(f281_in(T71), .(T70, T71)) U2(f281_out1(T72, X74), .(T70, T71)) -> f281_out1(T72, .(T70, X74)) f284_in(T94) -> U3(f549_in(T94), T94) U3(f549_out1(T95, T96), T94) -> f284_out1(.(T95, T96)) f284_in(T135) -> f284_out1([]) f551_in(.(T114, T115)) -> f551_out1(T114) f551_in(.(T123, T124)) -> U4(f551_in(T124), .(T123, T124)) U4(f551_out1(T125), .(T123, T124)) -> f551_out1(T125) f160_in(T40) -> U5(f257_in(T40), T40) U5(f257_out1(T41, X41, T42), T40) -> f160_out1 f107_in(T17) -> U6(f160_in(T17), T17) U6(f160_out1, T17) -> U7(f3_in(T17), T17) U7(f3_out1, T17) -> f107_out1 f257_in(T40) -> U8(f281_in(T40), T40) U8(f281_out1(T41, T47), T40) -> U9(f284_in(T47), T40, T41, T47) U9(f284_out1(T48), T40, T41, T47) -> f257_out1(T41, T47, T48) f549_in(T94) -> U10(f551_in(T94), T94) U10(f551_out1(T95), T94) -> U11(f284_in(T94), T94, T95) U11(f284_out1(T101), T94, T95) -> f549_out1(T95, T101) 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: F551_IN(.(T123, T124)) -> F551_IN(T124) The TRS R consists of the following rules: f3_in(T17) -> U1(f107_in(T17), T17) U1(f107_out1, T17) -> f3_out1 f3_in(T141) -> f3_out1 f281_in(.(T61, T62)) -> f281_out1(T61, T62) f281_in(.(T70, T71)) -> U2(f281_in(T71), .(T70, T71)) U2(f281_out1(T72, X74), .(T70, T71)) -> f281_out1(T72, .(T70, X74)) f284_in(T94) -> U3(f549_in(T94), T94) U3(f549_out1(T95, T96), T94) -> f284_out1(.(T95, T96)) f284_in(T135) -> f284_out1([]) f551_in(.(T114, T115)) -> f551_out1(T114) f551_in(.(T123, T124)) -> U4(f551_in(T124), .(T123, T124)) U4(f551_out1(T125), .(T123, T124)) -> f551_out1(T125) f160_in(T40) -> U5(f257_in(T40), T40) U5(f257_out1(T41, X41, T42), T40) -> f160_out1 f107_in(T17) -> U6(f160_in(T17), T17) U6(f160_out1, T17) -> U7(f3_in(T17), T17) U7(f3_out1, T17) -> f107_out1 f257_in(T40) -> U8(f281_in(T40), T40) U8(f281_out1(T41, T47), T40) -> U9(f284_in(T47), T40, T41, T47) U9(f284_out1(T48), T40, T41, T47) -> f257_out1(T41, T47, T48) f549_in(T94) -> U10(f551_in(T94), T94) U10(f551_out1(T95), T94) -> U11(f284_in(T94), T94, T95) U11(f284_out1(T101), T94, T95) -> f549_out1(T95, T101) 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: F551_IN(.(T123, T124)) -> F551_IN(T124) 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: *F551_IN(.(T123, T124)) -> F551_IN(T124) The graph contains the following edges 1 > 1 ---------------------------------------- (75) YES ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F284_IN(T94) -> F549_IN(T94) F549_IN(T94) -> U10^1(f551_in(T94), T94) U10^1(f551_out1(T95), T94) -> F284_IN(T94) The TRS R consists of the following rules: f3_in(T17) -> U1(f107_in(T17), T17) U1(f107_out1, T17) -> f3_out1 f3_in(T141) -> f3_out1 f281_in(.(T61, T62)) -> f281_out1(T61, T62) f281_in(.(T70, T71)) -> U2(f281_in(T71), .(T70, T71)) U2(f281_out1(T72, X74), .(T70, T71)) -> f281_out1(T72, .(T70, X74)) f284_in(T94) -> U3(f549_in(T94), T94) U3(f549_out1(T95, T96), T94) -> f284_out1(.(T95, T96)) f284_in(T135) -> f284_out1([]) f551_in(.(T114, T115)) -> f551_out1(T114) f551_in(.(T123, T124)) -> U4(f551_in(T124), .(T123, T124)) U4(f551_out1(T125), .(T123, T124)) -> f551_out1(T125) f160_in(T40) -> U5(f257_in(T40), T40) U5(f257_out1(T41, X41, T42), T40) -> f160_out1 f107_in(T17) -> U6(f160_in(T17), T17) U6(f160_out1, T17) -> U7(f3_in(T17), T17) U7(f3_out1, T17) -> f107_out1 f257_in(T40) -> U8(f281_in(T40), T40) U8(f281_out1(T41, T47), T40) -> U9(f284_in(T47), T40, T41, T47) U9(f284_out1(T48), T40, T41, T47) -> f257_out1(T41, T47, T48) f549_in(T94) -> U10(f551_in(T94), T94) U10(f551_out1(T95), T94) -> U11(f284_in(T94), T94, T95) U11(f284_out1(T101), T94, T95) -> f549_out1(T95, T101) 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 = F549_IN(.(T114, T115)) evaluates to t =F549_IN(.(T114, T115)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F549_IN(.(T114, T115)) -> U10^1(f551_in(.(T114, T115)), .(T114, T115)) with rule F549_IN(T94) -> U10^1(f551_in(T94), T94) at position [] and matcher [T94 / .(T114, T115)] U10^1(f551_in(.(T114, T115)), .(T114, T115)) -> U10^1(f551_out1(T114), .(T114, T115)) with rule f551_in(.(T114', T115')) -> f551_out1(T114') at position [0] and matcher [T114' / T114, T115' / T115] U10^1(f551_out1(T114), .(T114, T115)) -> F284_IN(.(T114, T115)) with rule U10^1(f551_out1(T95), T94') -> F284_IN(T94') at position [] and matcher [T95 / T114, T94' / .(T114, T115)] F284_IN(.(T114, T115)) -> F549_IN(.(T114, T115)) with rule F284_IN(T94) -> F549_IN(T94) 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: F281_IN(.(T70, T71)) -> F281_IN(T71) The TRS R consists of the following rules: f3_in(T17) -> U1(f107_in(T17), T17) U1(f107_out1, T17) -> f3_out1 f3_in(T141) -> f3_out1 f281_in(.(T61, T62)) -> f281_out1(T61, T62) f281_in(.(T70, T71)) -> U2(f281_in(T71), .(T70, T71)) U2(f281_out1(T72, X74), .(T70, T71)) -> f281_out1(T72, .(T70, X74)) f284_in(T94) -> U3(f549_in(T94), T94) U3(f549_out1(T95, T96), T94) -> f284_out1(.(T95, T96)) f284_in(T135) -> f284_out1([]) f551_in(.(T114, T115)) -> f551_out1(T114) f551_in(.(T123, T124)) -> U4(f551_in(T124), .(T123, T124)) U4(f551_out1(T125), .(T123, T124)) -> f551_out1(T125) f160_in(T40) -> U5(f257_in(T40), T40) U5(f257_out1(T41, X41, T42), T40) -> f160_out1 f107_in(T17) -> U6(f160_in(T17), T17) U6(f160_out1, T17) -> U7(f3_in(T17), T17) U7(f3_out1, T17) -> f107_out1 f257_in(T40) -> U8(f281_in(T40), T40) U8(f281_out1(T41, T47), T40) -> U9(f284_in(T47), T40, T41, T47) U9(f284_out1(T48), T40, T41, T47) -> f257_out1(T41, T47, T48) f549_in(T94) -> U10(f551_in(T94), T94) U10(f551_out1(T95), T94) -> U11(f284_in(T94), T94, T95) U11(f284_out1(T101), T94, T95) -> f549_out1(T95, T101) 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: F281_IN(.(T70, T71)) -> F281_IN(T71) 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: *F281_IN(.(T70, T71)) -> F281_IN(T71) The graph contains the following edges 1 > 1 ---------------------------------------- (83) YES ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN(T17) -> F107_IN(T17) F107_IN(T17) -> U6^1(f160_in(T17), T17) U6^1(f160_out1, T17) -> F3_IN(T17) The TRS R consists of the following rules: f3_in(T17) -> U1(f107_in(T17), T17) U1(f107_out1, T17) -> f3_out1 f3_in(T141) -> f3_out1 f281_in(.(T61, T62)) -> f281_out1(T61, T62) f281_in(.(T70, T71)) -> U2(f281_in(T71), .(T70, T71)) U2(f281_out1(T72, X74), .(T70, T71)) -> f281_out1(T72, .(T70, X74)) f284_in(T94) -> U3(f549_in(T94), T94) U3(f549_out1(T95, T96), T94) -> f284_out1(.(T95, T96)) f284_in(T135) -> f284_out1([]) f551_in(.(T114, T115)) -> f551_out1(T114) f551_in(.(T123, T124)) -> U4(f551_in(T124), .(T123, T124)) U4(f551_out1(T125), .(T123, T124)) -> f551_out1(T125) f160_in(T40) -> U5(f257_in(T40), T40) U5(f257_out1(T41, X41, T42), T40) -> f160_out1 f107_in(T17) -> U6(f160_in(T17), T17) U6(f160_out1, T17) -> U7(f3_in(T17), T17) U7(f3_out1, T17) -> f107_out1 f257_in(T40) -> U8(f281_in(T40), T40) U8(f281_out1(T41, T47), T40) -> U9(f284_in(T47), T40, T41, T47) U9(f284_out1(T48), T40, T41, T47) -> f257_out1(T41, T47, T48) f549_in(T94) -> U10(f551_in(T94), T94) U10(f551_out1(T95), T94) -> U11(f284_in(T94), T94, T95) U11(f284_out1(T101), T94, T95) -> f549_out1(T95, T101) 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 = F107_IN(.(T61, T62)) evaluates to t =F107_IN(.(T61, T62)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F107_IN(.(T61, T62)) -> U6^1(f160_in(.(T61, T62)), .(T61, T62)) with rule F107_IN(T17) -> U6^1(f160_in(T17), T17) at position [] and matcher [T17 / .(T61, T62)] U6^1(f160_in(.(T61, T62)), .(T61, T62)) -> U6^1(U5(f257_in(.(T61, T62)), .(T61, T62)), .(T61, T62)) with rule f160_in(T40') -> U5(f257_in(T40'), T40') at position [0] and matcher [T40' / .(T61, T62)] U6^1(U5(f257_in(.(T61, T62)), .(T61, T62)), .(T61, T62)) -> U6^1(U5(U8(f281_in(.(T61, T62)), .(T61, T62)), .(T61, T62)), .(T61, T62)) with rule f257_in(T40') -> U8(f281_in(T40'), T40') at position [0,0] and matcher [T40' / .(T61, T62)] U6^1(U5(U8(f281_in(.(T61, T62)), .(T61, T62)), .(T61, T62)), .(T61, T62)) -> U6^1(U5(U8(f281_out1(T61, T62), .(T61, T62)), .(T61, T62)), .(T61, T62)) with rule f281_in(.(T61', T62')) -> f281_out1(T61', T62') at position [0,0,0] and matcher [T61' / T61, T62' / T62] U6^1(U5(U8(f281_out1(T61, T62), .(T61, T62)), .(T61, T62)), .(T61, T62)) -> U6^1(U5(U9(f284_in(T62), .(T61, T62), T61, T62), .(T61, T62)), .(T61, T62)) with rule U8(f281_out1(T41, T47'), T40'') -> U9(f284_in(T47'), T40'', T41, T47') at position [0,0] and matcher [T41 / T61, T47' / T62, T40'' / .(T61, T62)] U6^1(U5(U9(f284_in(T62), .(T61, T62), T61, T62), .(T61, T62)), .(T61, T62)) -> U6^1(U5(U9(f284_out1([]), .(T61, T62), T61, T62), .(T61, T62)), .(T61, T62)) with rule f284_in(T135) -> f284_out1([]) at position [0,0,0] and matcher [T135 / T62] U6^1(U5(U9(f284_out1([]), .(T61, T62), T61, T62), .(T61, T62)), .(T61, T62)) -> U6^1(U5(f257_out1(T61, T62, []), .(T61, T62)), .(T61, T62)) with rule U9(f284_out1(T48), T40', T41', T47) -> f257_out1(T41', T47, T48) at position [0,0] and matcher [T48 / [], T40' / .(T61, T62), T41' / T61, T47 / T62] U6^1(U5(f257_out1(T61, T62, []), .(T61, T62)), .(T61, T62)) -> U6^1(f160_out1, .(T61, T62)) with rule U5(f257_out1(T41, X41, T42), T40) -> f160_out1 at position [0] and matcher [T41 / T61, X41 / T62, T42 / [], T40 / .(T61, T62)] U6^1(f160_out1, .(T61, T62)) -> F3_IN(.(T61, T62)) with rule U6^1(f160_out1, T17') -> F3_IN(T17') at position [] and matcher [T17' / .(T61, T62)] F3_IN(.(T61, T62)) -> F107_IN(.(T61, T62)) with rule F3_IN(T17) -> F107_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": 1, "program": { "directives": [], "clauses": [ [ "(color_map (. Region Regions) Colors)", "(',' (color_region Region Colors) (color_map Regions Colors))" ], [ "(color_map ([]) Colors)", null ], [ "(color_region (region Name 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 Map)", "(',' (map Name Map) (',' (colors Name Colors) (color_map Map Colors)))" ], [ "(map (test) (. (region (a) A (. B (. C (. D ([]))))) (. (region (b) B (. A (. C (. E ([]))))) (. (region (c) C (. A (. B (. D (. E (. F ([]))))))) (. (region (d) D (. A (. C (. F ([]))))) (. (region (e) E (. B (. C (. F ([]))))) (. (region (f) F (. C (. D (. E ([]))))) ([]))))))))", null ], [ "(map (west_europe) (. (region (portugal) P (. E ([]))) (. (region (spain) E (. F (. P ([])))) (. (region (france) F (. E (. I (. S (. B (. WG (. L ([])))))))) (. (region (belgium) B (. F (. H (. L (. WG ([])))))) (. (region (holland) H (. B (. WG ([])))) (. (region (west_germany) WG (. F (. A (. S (. H (. B (. L ([])))))))) (. (region (luxembourg) L (. F (. B (. WG ([]))))) (. (region (italy) I (. F (. A (. S ([]))))) (. (region (switzerland) S (. F (. I (. A (. WG ([])))))) (. (region (austria) A (. I (. S (. WG ([]))))) ([]))))))))))))", null ], [ "(colors X (. (red) (. (yellow) (. (blue) (. (white) ([]))))))", null ] ] }, "graph": { "nodes": { "44": { "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": [] } }, "45": { "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": [] } }, "type": "Nodes", "630": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "631": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "610": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T97 T90)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T90"], "free": [], "exprvars": [] } }, "632": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "611": { "goal": [ { "clause": 7, "scope": 5, "term": "(member T91 T90)" }, { "clause": 8, "scope": 5, "term": "(member T91 T90)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T90"], "free": [], "exprvars": [] } }, "633": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "612": { "goal": [{ "clause": 7, "scope": 5, "term": "(member T91 T90)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T90"], "free": [], "exprvars": [] } }, "634": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "613": { "goal": [{ "clause": 8, "scope": 5, "term": "(member T91 T90)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T90"], "free": [], "exprvars": [] } }, "614": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "615": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "539": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T39 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [], "exprvars": [] } }, "616": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (select T31 T30 X31) (members T32 X31)) (color_map T33 T30))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": ["X31"], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "55": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T31 T30 X31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": ["X31"], "exprvars": [] } }, "57": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (members T39 T38) (color_map T40 T30))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T38" ], "free": [], "exprvars": [] } }, "58": { "goal": [ { "clause": 3, "scope": 3, "term": "(select T31 T30 X31)" }, { "clause": 4, "scope": 3, "term": "(select T31 T30 X31)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": ["X31"], "exprvars": [] } }, "59": { "goal": [{ "clause": 3, "scope": 3, "term": "(select T31 T30 X31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": ["X31"], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T64 T63 X64)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T63"], "free": ["X64"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "265": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "540": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T72 T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "288": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "543": { "goal": [ { "clause": 5, "scope": 4, "term": "(members T39 T38)" }, { "clause": 6, "scope": 4, "term": "(members T39 T38)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "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": [] } }, "544": { "goal": [{ "clause": 5, "scope": 4, "term": "(members T39 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [], "exprvars": [] } }, "545": { "goal": [{ "clause": 6, "scope": 4, "term": "(members T39 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [], "exprvars": [] } }, "667": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "668": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "669": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [{ "clause": 4, "scope": 3, "term": "(select T31 T30 X31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": ["X31"], "exprvars": [] } }, "626": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T121 T120)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T120"], "free": [], "exprvars": [] } }, "627": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "628": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "41": { "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": [] } }, "63": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "607": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T91 T90) (members T92 T90))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T90"], "free": [], "exprvars": [] } }, "629": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "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": [] } }, "608": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "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": [] } }, "609": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T91 T90)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T90"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 41, "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": 42, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 43, "label": "CASE" }, { "from": 42, "to": 667, "label": "EVAL with clause\ncolor_map([], X134).\nand substitutionT1 -> [],\nT2 -> T139,\nX134 -> T139" }, { "from": 42, "to": 668, "label": "EVAL-BACKTRACK" }, { "from": 43, "to": 44, "label": "PARALLEL" }, { "from": 43, "to": 45, "label": "PARALLEL" }, { "from": 44, "to": 51, "label": "EVAL with clause\ncolor_region(region(X27, X28, X29), X30) :- ','(select(X28, X30, X31), members(X29, X31)).\nand substitutionX27 -> T27,\nX28 -> T31,\nX29 -> T32,\nT9 -> region(T27, T31, T32),\nT8 -> T30,\nX30 -> T30,\nT28 -> T31,\nT29 -> T32,\nT10 -> T33" }, { "from": 44, "to": 52, "label": "EVAL-BACKTRACK" }, { "from": 45, "to": 631, "label": "FAILURE" }, { "from": 51, "to": 55, "label": "SPLIT 1" }, { "from": 51, "to": 57, "label": "SPLIT 2\nnew knowledge:\nT31 is ground\nT30 is ground\nT38 is ground\nreplacements:X31 -> T38,\nT32 -> T39,\nT33 -> T40" }, { "from": 55, "to": 58, "label": "CASE" }, { "from": 57, "to": 539, "label": "SPLIT 1" }, { "from": 57, "to": 540, "label": "SPLIT 2\nnew knowledge:\nT39 is ground\nT38 is ground\nreplacements:T40 -> T72" }, { "from": 58, "to": 59, "label": "PARALLEL" }, { "from": 58, "to": 60, "label": "PARALLEL" }, { "from": 59, "to": 63, "label": "EVAL with clause\nselect(X48, .(X48, X49), X49).\nand substitutionT31 -> T53,\nX48 -> T53,\nX49 -> T54,\nT30 -> .(T53, T54),\nX31 -> T54" }, { "from": 59, "to": 259, "label": "EVAL-BACKTRACK" }, { "from": 60, "to": 283, "label": "EVAL with clause\nselect(X60, .(X61, X62), .(X61, X63)) :- select(X60, X62, X63).\nand substitutionT31 -> T64,\nX60 -> T64,\nX61 -> T62,\nX62 -> T63,\nT30 -> .(T62, T63),\nX63 -> X64,\nX31 -> .(T62, X64),\nT61 -> T64" }, { "from": 60, "to": 288, "label": "EVAL-BACKTRACK" }, { "from": 63, "to": 265, "label": "SUCCESS" }, { "from": 283, "to": 55, "label": "INSTANCE with matching:\nT31 -> T64\nT30 -> T63\nX31 -> X64" }, { "from": 539, "to": 543, "label": "CASE" }, { "from": 540, "to": 1, "label": "INSTANCE with matching:\nT1 -> T72\nT2 -> T30" }, { "from": 543, "to": 544, "label": "PARALLEL" }, { "from": 543, "to": 545, "label": "PARALLEL" }, { "from": 544, "to": 607, "label": "EVAL with clause\nmembers(.(X87, X88), X89) :- ','(member(X87, X89), members(X88, X89)).\nand substitutionX87 -> T91,\nX88 -> T92,\nT39 -> .(T91, T92),\nT38 -> T90,\nX89 -> T90,\nT88 -> T91,\nT89 -> T92" }, { "from": 544, "to": 608, "label": "EVAL-BACKTRACK" }, { "from": 545, "to": 628, "label": "EVAL with clause\nmembers([], X126).\nand substitutionT39 -> [],\nT38 -> T131,\nX126 -> T131" }, { "from": 545, "to": 629, "label": "EVAL-BACKTRACK" }, { "from": 607, "to": 609, "label": "SPLIT 1" }, { "from": 607, "to": 610, "label": "SPLIT 2\nnew knowledge:\nT91 is ground\nT90 is ground\nreplacements:T92 -> T97" }, { "from": 609, "to": 611, "label": "CASE" }, { "from": 610, "to": 539, "label": "INSTANCE with matching:\nT39 -> T97\nT38 -> T90" }, { "from": 611, "to": 612, "label": "PARALLEL" }, { "from": 611, "to": 613, "label": "PARALLEL" }, { "from": 612, "to": 614, "label": "EVAL with clause\nmember(X106, .(X106, X107)).\nand substitutionT91 -> T110,\nX106 -> T110,\nX107 -> T111,\nT90 -> .(T110, T111)" }, { "from": 612, "to": 615, "label": "EVAL-BACKTRACK" }, { "from": 613, "to": 626, "label": "EVAL with clause\nmember(X114, .(X115, X116)) :- member(X114, X116).\nand substitutionT91 -> T121,\nX114 -> T121,\nX115 -> T119,\nX116 -> T120,\nT90 -> .(T119, T120),\nT118 -> T121" }, { "from": 613, "to": 627, "label": "EVAL-BACKTRACK" }, { "from": 614, "to": 616, "label": "SUCCESS" }, { "from": 626, "to": 609, "label": "INSTANCE with matching:\nT91 -> T121\nT90 -> T120" }, { "from": 628, "to": 630, "label": "SUCCESS" }, { "from": 631, "to": 632, "label": "EVAL with clause\ncolor_map([], X132).\nand substitutionT1 -> [],\nT8 -> T137,\nX132 -> T137" }, { "from": 631, "to": 633, "label": "EVAL-BACKTRACK" }, { "from": 632, "to": 634, "label": "SUCCESS" }, { "from": 667, "to": 669, "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), X5) :- selectA(X2, X5, X6). color_mapB(.(region(X1, X2, X3), X4), X5) :- ','(selectcA(X2, X5, X6), membersC(X3, X6)). color_mapB(.(region(X1, X2, X3), X4), X5) :- ','(selectcA(X2, X5, X6), ','(memberscC(X3, X6), color_mapB(X4, X5))). Clauses: selectcA(X1, .(X1, X2), X2). selectcA(X1, .(X2, X3), .(X2, X4)) :- selectcA(X1, X3, X4). color_mapcB(.(region(X1, X2, X3), X4), X5) :- ','(selectcA(X2, X5, X6), ','(memberscC(X3, X6), color_mapcB(X4, X5))). 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), X5) -> U6_AG(X1, X2, X3, X4, X5, selectA_in_aga(X2, X5, X6)) COLOR_MAPB_IN_AG(.(region(X1, X2, X3), X4), X5) -> SELECTA_IN_AGA(X2, X5, X6) 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), X5) -> U7_AG(X1, X2, X3, X4, X5, selectcA_in_aga(X2, X5, X6)) U7_AG(X1, X2, X3, X4, X5, selectcA_out_aga(X2, X5, X6)) -> U8_AG(X1, X2, X3, X4, X5, membersC_in_ag(X3, X6)) U7_AG(X1, X2, X3, X4, X5, selectcA_out_aga(X2, X5, X6)) -> MEMBERSC_IN_AG(X3, X6) 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, X5, selectcA_out_aga(X2, X5, X6)) -> U9_AG(X1, X2, X3, X4, X5, memberscC_in_ag(X3, X6)) U9_AG(X1, X2, X3, X4, X5, memberscC_out_ag(X3, X6)) -> U10_AG(X1, X2, X3, X4, X5, color_mapB_in_ag(X4, X5)) U9_AG(X1, X2, X3, X4, X5, memberscC_out_ag(X3, X6)) -> COLOR_MAPB_IN_AG(X4, X5) 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) region(x1, x2, x3) = region(x2, x3) 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, x6) = U6_AG(x5, x6) 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, x6) = U7_AG(x5, x6) U8_AG(x1, x2, x3, x4, x5, x6) = U8_AG(x5, x6) 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, x6) = U9_AG(x5, x6) U10_AG(x1, x2, x3, x4, x5, x6) = U10_AG(x5, x6) 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), X5) -> U6_AG(X1, X2, X3, X4, X5, selectA_in_aga(X2, X5, X6)) COLOR_MAPB_IN_AG(.(region(X1, X2, X3), X4), X5) -> SELECTA_IN_AGA(X2, X5, X6) 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), X5) -> U7_AG(X1, X2, X3, X4, X5, selectcA_in_aga(X2, X5, X6)) U7_AG(X1, X2, X3, X4, X5, selectcA_out_aga(X2, X5, X6)) -> U8_AG(X1, X2, X3, X4, X5, membersC_in_ag(X3, X6)) U7_AG(X1, X2, X3, X4, X5, selectcA_out_aga(X2, X5, X6)) -> MEMBERSC_IN_AG(X3, X6) 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, X5, selectcA_out_aga(X2, X5, X6)) -> U9_AG(X1, X2, X3, X4, X5, memberscC_in_ag(X3, X6)) U9_AG(X1, X2, X3, X4, X5, memberscC_out_ag(X3, X6)) -> U10_AG(X1, X2, X3, X4, X5, color_mapB_in_ag(X4, X5)) U9_AG(X1, X2, X3, X4, X5, memberscC_out_ag(X3, X6)) -> COLOR_MAPB_IN_AG(X4, X5) 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) region(x1, x2, x3) = region(x2, x3) 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, x6) = U6_AG(x5, x6) 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, x6) = U7_AG(x5, x6) U8_AG(x1, x2, x3, x4, x5, x6) = U8_AG(x5, x6) 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, x6) = U9_AG(x5, x6) U10_AG(x1, x2, x3, x4, x5, x6) = U10_AG(x5, x6) 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), X5) -> U7_AG(X1, X2, X3, X4, X5, selectcA_in_aga(X2, X5, X6)) U7_AG(X1, X2, X3, X4, X5, selectcA_out_aga(X2, X5, X6)) -> U9_AG(X1, X2, X3, X4, X5, memberscC_in_ag(X3, X6)) U9_AG(X1, X2, X3, X4, X5, memberscC_out_ag(X3, X6)) -> COLOR_MAPB_IN_AG(X4, X5) 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) region(x1, x2, x3) = region(x2, x3) 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, x6) = U7_AG(x5, x6) U9_AG(x1, x2, x3, x4, x5, x6) = U9_AG(x5, x6) 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": 2, "program": { "directives": [], "clauses": [ [ "(color_map (. Region Regions) Colors)", "(',' (color_region Region Colors) (color_map Regions Colors))" ], [ "(color_map ([]) Colors)", null ], [ "(color_region (region Name 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 Map)", "(',' (map Name Map) (',' (colors Name Colors) (color_map Map Colors)))" ], [ "(map (test) (. (region (a) A (. B (. C (. D ([]))))) (. (region (b) B (. A (. C (. E ([]))))) (. (region (c) C (. A (. B (. D (. E (. F ([]))))))) (. (region (d) D (. A (. C (. F ([]))))) (. (region (e) E (. B (. C (. F ([]))))) (. (region (f) F (. C (. D (. E ([]))))) ([]))))))))", null ], [ "(map (west_europe) (. (region (portugal) P (. E ([]))) (. (region (spain) E (. F (. P ([])))) (. (region (france) F (. E (. I (. S (. B (. WG (. L ([])))))))) (. (region (belgium) B (. F (. H (. L (. WG ([])))))) (. (region (holland) H (. B (. WG ([])))) (. (region (west_germany) WG (. F (. A (. S (. H (. B (. L ([])))))))) (. (region (luxembourg) L (. F (. B (. WG ([]))))) (. (region (italy) I (. F (. A (. S ([]))))) (. (region (switzerland) S (. F (. I (. A (. WG ([])))))) (. (region (austria) A (. I (. S (. WG ([]))))) ([]))))))))))))", null ], [ "(colors X (. (red) (. (yellow) (. (blue) (. (white) ([]))))))", null ] ] }, "graph": { "nodes": { "46": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T41 T40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "25": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (select T41 T40 X41) (members T42 X41))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T48 T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "48": { "goal": [ { "clause": 3, "scope": 3, "term": "(select T41 T40 X41)" }, { "clause": 4, "scope": 3, "term": "(select T41 T40 X41)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "49": { "goal": [{ "clause": 3, "scope": 3, "term": "(select T41 T40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "type": "Nodes", "570": { "goal": [{ "clause": 8, "scope": 5, "term": "(member T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "573": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "574": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "575": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "512": { "goal": [ { "clause": 5, "scope": 4, "term": "(members T48 T47)" }, { "clause": 6, "scope": 4, "term": "(members T48 T47)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "578": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T125 T124)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T124"], "free": [], "exprvars": [] } }, "535": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T95 T94) (members T96 T94))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "579": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "538": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": 4, "scope": 3, "term": "(select T41 T40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X41"], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T24 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": 2, "scope": 2, "term": "(color_region T18 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "581": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "582": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "583": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "541": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "563": { "goal": [ { "clause": 7, "scope": 5, "term": "(member T95 T94)" }, { "clause": 8, "scope": 5, "term": "(member T95 T94)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "542": { "goal": [{ "clause": -1, "scope": -1, "term": "(members T101 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "586": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "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": [] } }, "588": { "goal": [], "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": [] } }, "589": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 1, "scope": 1, "term": "(color_map T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "569": { "goal": [{ "clause": 7, "scope": 5, "term": "(member T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "9": { "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": [] } }, "526": { "goal": [{ "clause": 5, "scope": 4, "term": "(members T48 T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "527": { "goal": [{ "clause": 6, "scope": 4, "term": "(members T48 T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [], "exprvars": [] } }, "61": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T72 T71 X74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": ["X74"], "exprvars": [] } }, "62": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 6, "label": "PARALLEL" }, { "from": 4, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 9, "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": 10, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 586, "label": "EVAL with clause\ncolor_map([], X139).\nand substitutionT1 -> [],\nT2 -> T141,\nX139 -> T141" }, { "from": 7, "to": 588, "label": "EVAL-BACKTRACK" }, { "from": 9, "to": 11, "label": "SPLIT 1" }, { "from": 9, "to": 12, "label": "SPLIT 2\nnew knowledge:\nT17 is ground\nreplacements:T19 -> T24" }, { "from": 11, "to": 13, "label": "CASE" }, { "from": 12, "to": 2, "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> T17" }, { "from": 13, "to": 25, "label": "EVAL with clause\ncolor_region(region(X37, X38, X39), X40) :- ','(select(X38, X40, X41), members(X39, X41)).\nand substitutionX37 -> T37,\nX38 -> T41,\nX39 -> T42,\nT18 -> region(T37, T41, T42),\nT17 -> T40,\nX40 -> T40,\nT38 -> T41,\nT39 -> T42" }, { "from": 13, "to": 36, "label": "EVAL-BACKTRACK" }, { "from": 25, "to": 46, "label": "SPLIT 1" }, { "from": 25, "to": 47, "label": "SPLIT 2\nnew knowledge:\nT41 is ground\nT40 is ground\nT47 is ground\nreplacements:X41 -> T47,\nT42 -> T48" }, { "from": 46, "to": 48, "label": "CASE" }, { "from": 47, "to": 512, "label": "CASE" }, { "from": 48, "to": 49, "label": "PARALLEL" }, { "from": 48, "to": 50, "label": "PARALLEL" }, { "from": 49, "to": 53, "label": "EVAL with clause\nselect(X58, .(X58, X59), X59).\nand substitutionT41 -> T61,\nX58 -> T61,\nX59 -> T62,\nT40 -> .(T61, T62),\nX41 -> T62" }, { "from": 49, "to": 54, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 61, "label": "EVAL with clause\nselect(X70, .(X71, X72), .(X71, X73)) :- select(X70, X72, X73).\nand substitutionT41 -> T72,\nX70 -> T72,\nX71 -> T70,\nX72 -> T71,\nT40 -> .(T70, T71),\nX73 -> X74,\nX41 -> .(T70, X74),\nT69 -> T72" }, { "from": 50, "to": 62, "label": "EVAL-BACKTRACK" }, { "from": 53, "to": 56, "label": "SUCCESS" }, { "from": 61, "to": 46, "label": "INSTANCE with matching:\nT41 -> T72\nT40 -> T71\nX41 -> X74" }, { "from": 512, "to": 526, "label": "PARALLEL" }, { "from": 512, "to": 527, "label": "PARALLEL" }, { "from": 526, "to": 535, "label": "EVAL with clause\nmembers(.(X94, X95), X96) :- ','(member(X94, X96), members(X95, X96)).\nand substitutionX94 -> T95,\nX95 -> T96,\nT48 -> .(T95, T96),\nT47 -> T94,\nX96 -> T94,\nT92 -> T95,\nT93 -> T96" }, { "from": 526, "to": 538, "label": "EVAL-BACKTRACK" }, { "from": 527, "to": 581, "label": "EVAL with clause\nmembers([], X133).\nand substitutionT48 -> [],\nT47 -> T135,\nX133 -> T135" }, { "from": 527, "to": 582, "label": "EVAL-BACKTRACK" }, { "from": 535, "to": 541, "label": "SPLIT 1" }, { "from": 535, "to": 542, "label": "SPLIT 2\nnew knowledge:\nT95 is ground\nT94 is ground\nreplacements:T96 -> T101" }, { "from": 541, "to": 563, "label": "CASE" }, { "from": 542, "to": 47, "label": "INSTANCE with matching:\nT48 -> T101\nT47 -> T94" }, { "from": 563, "to": 569, "label": "PARALLEL" }, { "from": 563, "to": 570, "label": "PARALLEL" }, { "from": 569, "to": 573, "label": "EVAL with clause\nmember(X113, .(X113, X114)).\nand substitutionT95 -> T114,\nX113 -> T114,\nX114 -> T115,\nT94 -> .(T114, T115)" }, { "from": 569, "to": 574, "label": "EVAL-BACKTRACK" }, { "from": 570, "to": 578, "label": "EVAL with clause\nmember(X121, .(X122, X123)) :- member(X121, X123).\nand substitutionT95 -> T125,\nX121 -> T125,\nX122 -> T123,\nX123 -> T124,\nT94 -> .(T123, T124),\nT122 -> T125" }, { "from": 570, "to": 579, "label": "EVAL-BACKTRACK" }, { "from": 573, "to": 575, "label": "SUCCESS" }, { "from": 578, "to": 541, "label": "INSTANCE with matching:\nT95 -> T125\nT94 -> T124" }, { "from": 581, "to": 583, "label": "SUCCESS" }, { "from": 586, "to": 589, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (114) Complex Obligation (AND) ---------------------------------------- (115) Obligation: Rules: f570_in(T94) -> f579_in :|: TRUE f579_out -> f570_out(x) :|: TRUE f578_out(T124) -> f570_out(.(T123, T124)) :|: TRUE f570_in(.(x1, x2)) -> f578_in(x2) :|: TRUE f578_in(x3) -> f541_in(x3) :|: TRUE f541_out(x4) -> f578_out(x4) :|: TRUE f563_out(x5) -> f541_out(x5) :|: TRUE f541_in(x6) -> f563_in(x6) :|: TRUE f569_out(x7) -> f563_out(x7) :|: TRUE f563_in(x8) -> f569_in(x8) :|: TRUE f570_out(x9) -> f563_out(x9) :|: TRUE f563_in(x10) -> f570_in(x10) :|: TRUE f2_in(T2) -> f4_in(T2) :|: TRUE f4_out(x11) -> f2_out(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 f6_in(T17) -> f9_in(T17) :|: TRUE f10_out -> f6_out(x16) :|: TRUE f9_out(x17) -> f6_out(x17) :|: TRUE f6_in(x18) -> f10_in :|: TRUE f11_out(x19) -> f12_in(x19) :|: TRUE f9_in(x20) -> f11_in(x20) :|: TRUE f12_out(x21) -> f9_out(x21) :|: TRUE f13_out(x22) -> f11_out(x22) :|: TRUE f11_in(x23) -> f13_in(x23) :|: TRUE f36_out -> f13_out(x24) :|: TRUE f13_in(T40) -> f25_in(T40) :|: TRUE f13_in(x25) -> f36_in :|: TRUE f25_out(x26) -> f13_out(x26) :|: TRUE f47_out(x27) -> f25_out(x28) :|: TRUE f46_out(x29) -> f47_in(x30) :|: TRUE f25_in(x31) -> f46_in(x31) :|: TRUE f512_out(T47) -> f47_out(T47) :|: TRUE f47_in(x32) -> f512_in(x32) :|: TRUE f527_out(x33) -> f512_out(x33) :|: TRUE f512_in(x34) -> f527_in(x34) :|: TRUE f526_out(x35) -> f512_out(x35) :|: TRUE f512_in(x36) -> f526_in(x36) :|: TRUE f526_in(x37) -> f535_in(x37) :|: TRUE f538_out -> f526_out(x38) :|: TRUE f535_out(x39) -> f526_out(x39) :|: TRUE f526_in(x40) -> f538_in :|: TRUE f541_out(x41) -> f542_in(x41) :|: TRUE f542_out(x42) -> f535_out(x42) :|: TRUE f535_in(x43) -> f541_in(x43) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (116) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (117) TRUE ---------------------------------------- (118) Obligation: Rules: f569_out(T94) -> f563_out(T94) :|: TRUE f563_in(x) -> f569_in(x) :|: TRUE f570_out(x1) -> f563_out(x1) :|: TRUE f563_in(x2) -> f570_in(x2) :|: TRUE f526_in(x3) -> f535_in(x3) :|: TRUE f538_out -> f526_out(T47) :|: TRUE f535_out(x4) -> f526_out(x4) :|: TRUE f526_in(x5) -> f538_in :|: TRUE f570_in(x6) -> f579_in :|: TRUE f579_out -> f570_out(x7) :|: TRUE f578_out(T124) -> f570_out(.(T123, T124)) :|: TRUE f570_in(.(x8, x9)) -> f578_in(x9) :|: TRUE f578_in(x10) -> f541_in(x10) :|: TRUE f541_out(x11) -> f578_out(x11) :|: TRUE f569_in(.(T114, T115)) -> f573_in :|: TRUE f569_in(x12) -> f574_in :|: TRUE f573_out -> f569_out(.(x13, x14)) :|: TRUE f574_out -> f569_out(x15) :|: TRUE f563_out(x16) -> f541_out(x16) :|: TRUE f541_in(x17) -> f563_in(x17) :|: TRUE f527_out(x18) -> f512_out(x18) :|: TRUE f512_in(x19) -> f527_in(x19) :|: TRUE f526_out(x20) -> f512_out(x20) :|: TRUE f512_in(x21) -> f526_in(x21) :|: TRUE f541_out(x22) -> f542_in(x22) :|: TRUE f542_out(x23) -> f535_out(x23) :|: TRUE f535_in(x24) -> f541_in(x24) :|: TRUE f512_out(x25) -> f47_out(x25) :|: TRUE f47_in(x26) -> f512_in(x26) :|: TRUE f573_in -> f573_out :|: TRUE f542_in(x27) -> f47_in(x27) :|: TRUE f47_out(x28) -> f542_out(x28) :|: TRUE f2_in(T2) -> f4_in(T2) :|: TRUE f4_out(x29) -> f2_out(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 f6_in(T17) -> f9_in(T17) :|: TRUE f10_out -> f6_out(x34) :|: TRUE f9_out(x35) -> f6_out(x35) :|: TRUE f6_in(x36) -> f10_in :|: TRUE f11_out(x37) -> f12_in(x37) :|: TRUE f9_in(x38) -> f11_in(x38) :|: TRUE f12_out(x39) -> f9_out(x39) :|: TRUE f13_out(x40) -> f11_out(x40) :|: TRUE f11_in(x41) -> f13_in(x41) :|: TRUE f36_out -> f13_out(x42) :|: TRUE f13_in(T40) -> f25_in(T40) :|: TRUE f13_in(x43) -> f36_in :|: TRUE f25_out(x44) -> f13_out(x44) :|: TRUE f47_out(x45) -> f25_out(x46) :|: TRUE f46_out(x47) -> f47_in(x48) :|: TRUE f25_in(x49) -> f46_in(x49) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (119) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (120) TRUE ---------------------------------------- (121) Obligation: Rules: f46_in(T40) -> f48_in(T40) :|: TRUE f48_out(x) -> f46_out(x) :|: TRUE f50_in(x1) -> f62_in :|: TRUE f62_out -> f50_out(x2) :|: TRUE f50_in(.(T70, T71)) -> f61_in(T71) :|: TRUE f61_out(x3) -> f50_out(.(x4, x3)) :|: TRUE f48_in(x5) -> f50_in(x5) :|: TRUE f48_in(x6) -> f49_in(x6) :|: TRUE f50_out(x7) -> f48_out(x7) :|: TRUE f49_out(x8) -> f48_out(x8) :|: TRUE f46_out(x9) -> f61_out(x9) :|: TRUE f61_in(x10) -> f46_in(x10) :|: TRUE f2_in(T2) -> f4_in(T2) :|: TRUE f4_out(x11) -> f2_out(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 f6_in(T17) -> f9_in(T17) :|: TRUE f10_out -> f6_out(x16) :|: TRUE f9_out(x17) -> f6_out(x17) :|: TRUE f6_in(x18) -> f10_in :|: TRUE f11_out(x19) -> f12_in(x19) :|: TRUE f9_in(x20) -> f11_in(x20) :|: TRUE f12_out(x21) -> f9_out(x21) :|: TRUE f13_out(x22) -> f11_out(x22) :|: TRUE f11_in(x23) -> f13_in(x23) :|: TRUE f36_out -> f13_out(x24) :|: TRUE f13_in(x25) -> f25_in(x25) :|: TRUE f13_in(x26) -> f36_in :|: TRUE f25_out(x27) -> f13_out(x27) :|: TRUE f47_out(x28) -> f25_out(x29) :|: TRUE f46_out(x30) -> f47_in(x31) :|: TRUE f25_in(x32) -> f46_in(x32) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (122) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f46_in(T40) -> f48_in(T40) :|: TRUE f50_in(.(T70, T71)) -> f61_in(T71) :|: TRUE f48_in(x5) -> f50_in(x5) :|: TRUE f61_in(x10) -> f46_in(x10) :|: TRUE ---------------------------------------- (123) Obligation: Rules: f46_in(T40) -> f48_in(T40) :|: TRUE f50_in(.(T70, T71)) -> f61_in(T71) :|: TRUE f48_in(x5) -> f50_in(x5) :|: TRUE f61_in(x10) -> f46_in(x10) :|: TRUE ---------------------------------------- (124) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (125) Obligation: Rules: f46_in(.(T70:0, T71:0)) -> f46_in(T71:0) :|: TRUE ---------------------------------------- (126) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (127) Obligation: Rules: f46_in(.(T70:0, T71:0)) -> f46_in(T71:0) :|: TRUE ---------------------------------------- (128) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f46_in(.(T70:0, T71:0)) -> f46_in(T71:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (129) Obligation: Termination digraph: Nodes: (1) f46_in(.(T70:0, T71:0)) -> f46_in(T71: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: f46_in(.(T71:0)) -> f46_in(T71:0) :|: TRUE ---------------------------------------- (132) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f46_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (133) Obligation: Rules: f46_in(.(T71:0)) -> f46_in(T71: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: f46_in(.(T71:0)) -> f46_in(T71: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: *f46_in(.(T71:0)) -> f46_in(T71:0) The graph contains the following edges 1 > 1 ---------------------------------------- (137) YES ---------------------------------------- (138) Obligation: Rules: f527_in(T47) -> f582_in :|: TRUE f582_out -> f527_out(x) :|: TRUE f527_in(T135) -> f581_in :|: TRUE f581_out -> f527_out(x1) :|: TRUE f569_out(T94) -> f563_out(T94) :|: TRUE f563_in(x2) -> f569_in(x2) :|: TRUE f570_out(x3) -> f563_out(x3) :|: TRUE f563_in(x4) -> f570_in(x4) :|: TRUE f6_in(T17) -> f9_in(T17) :|: TRUE f10_out -> f6_out(T2) :|: TRUE f9_out(x5) -> f6_out(x5) :|: TRUE f6_in(x6) -> f10_in :|: TRUE f581_in -> f581_out :|: TRUE f47_out(x7) -> f25_out(x8) :|: TRUE f46_out(x9) -> f47_in(x10) :|: TRUE f25_in(T40) -> f46_in(T40) :|: TRUE f13_out(x11) -> f11_out(x11) :|: TRUE f11_in(x12) -> f13_in(x12) :|: TRUE f578_in(T124) -> f541_in(T124) :|: TRUE f541_out(x13) -> f578_out(x13) :|: TRUE f50_in(x14) -> f62_in :|: TRUE f62_out -> f50_out(x15) :|: TRUE f50_in(.(T70, T71)) -> f61_in(T71) :|: TRUE f61_out(x16) -> f50_out(.(x17, x16)) :|: TRUE f563_out(x18) -> f541_out(x18) :|: TRUE f541_in(x19) -> f563_in(x19) :|: TRUE f527_out(x20) -> f512_out(x20) :|: TRUE f512_in(x21) -> f527_in(x21) :|: TRUE f526_out(x22) -> f512_out(x22) :|: TRUE f512_in(x23) -> f526_in(x23) :|: TRUE f542_in(x24) -> f47_in(x24) :|: TRUE f47_out(x25) -> f542_out(x25) :|: TRUE f49_in(x26) -> f54_in :|: TRUE f49_in(.(T61, T62)) -> f53_in :|: TRUE f53_out -> f49_out(.(x27, x28)) :|: TRUE f54_out -> f49_out(x29) :|: TRUE f2_out(x30) -> f12_out(x30) :|: TRUE f12_in(x31) -> f2_in(x31) :|: TRUE f36_out -> f13_out(x32) :|: TRUE f13_in(x33) -> f25_in(x33) :|: TRUE f13_in(x34) -> f36_in :|: TRUE f25_out(x35) -> f13_out(x35) :|: TRUE f11_out(x36) -> f12_in(x36) :|: TRUE f9_in(x37) -> f11_in(x37) :|: TRUE f12_out(x38) -> f9_out(x38) :|: TRUE f48_in(x39) -> f50_in(x39) :|: TRUE f48_in(x40) -> f49_in(x40) :|: TRUE f50_out(x41) -> f48_out(x41) :|: TRUE f49_out(x42) -> f48_out(x42) :|: TRUE f2_in(x43) -> f4_in(x43) :|: TRUE f4_out(x44) -> f2_out(x44) :|: TRUE f526_in(x45) -> f535_in(x45) :|: TRUE f538_out -> f526_out(x46) :|: TRUE f535_out(x47) -> f526_out(x47) :|: TRUE f526_in(x48) -> f538_in :|: TRUE f570_in(x49) -> f579_in :|: TRUE f579_out -> f570_out(x50) :|: TRUE f578_out(x51) -> f570_out(.(x52, x51)) :|: TRUE f570_in(.(x53, x54)) -> f578_in(x54) :|: TRUE f4_in(x55) -> f6_in(x55) :|: TRUE f7_out(x56) -> f4_out(x56) :|: TRUE f6_out(x57) -> f4_out(x57) :|: TRUE f4_in(x58) -> f7_in(x58) :|: TRUE f46_in(x59) -> f48_in(x59) :|: TRUE f48_out(x60) -> f46_out(x60) :|: TRUE f569_in(.(T114, T115)) -> f573_in :|: TRUE f569_in(x61) -> f574_in :|: TRUE f573_out -> f569_out(.(x62, x63)) :|: TRUE f574_out -> f569_out(x64) :|: TRUE f53_in -> f53_out :|: TRUE f512_out(x65) -> f47_out(x65) :|: TRUE f47_in(x66) -> f512_in(x66) :|: TRUE f541_out(x67) -> f542_in(x67) :|: TRUE f542_out(x68) -> f535_out(x68) :|: TRUE f535_in(x69) -> f541_in(x69) :|: TRUE f573_in -> f573_out :|: TRUE f46_out(x70) -> f61_out(x70) :|: TRUE f61_in(x71) -> f46_in(x71) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (139) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f527_in(T135) -> f581_in :|: TRUE f581_out -> f527_out(x1) :|: TRUE f569_out(T94) -> f563_out(T94) :|: TRUE f563_in(x2) -> f569_in(x2) :|: TRUE f570_out(x3) -> f563_out(x3) :|: TRUE f563_in(x4) -> f570_in(x4) :|: TRUE f6_in(T17) -> f9_in(T17) :|: TRUE f581_in -> f581_out :|: TRUE f47_out(x7) -> f25_out(x8) :|: TRUE f46_out(x9) -> f47_in(x10) :|: TRUE f25_in(T40) -> f46_in(T40) :|: TRUE f13_out(x11) -> f11_out(x11) :|: TRUE f11_in(x12) -> f13_in(x12) :|: TRUE f578_in(T124) -> f541_in(T124) :|: TRUE f541_out(x13) -> f578_out(x13) :|: TRUE f50_in(.(T70, T71)) -> f61_in(T71) :|: TRUE f61_out(x16) -> f50_out(.(x17, x16)) :|: TRUE f563_out(x18) -> f541_out(x18) :|: TRUE f541_in(x19) -> f563_in(x19) :|: TRUE f527_out(x20) -> f512_out(x20) :|: TRUE f512_in(x21) -> f527_in(x21) :|: TRUE f526_out(x22) -> f512_out(x22) :|: TRUE f512_in(x23) -> f526_in(x23) :|: TRUE f542_in(x24) -> f47_in(x24) :|: TRUE f47_out(x25) -> f542_out(x25) :|: TRUE f49_in(.(T61, T62)) -> f53_in :|: TRUE f53_out -> f49_out(.(x27, x28)) :|: TRUE f12_in(x31) -> f2_in(x31) :|: TRUE f13_in(x33) -> f25_in(x33) :|: TRUE f25_out(x35) -> f13_out(x35) :|: TRUE f11_out(x36) -> f12_in(x36) :|: TRUE f9_in(x37) -> f11_in(x37) :|: TRUE f48_in(x39) -> f50_in(x39) :|: TRUE f48_in(x40) -> f49_in(x40) :|: TRUE f50_out(x41) -> f48_out(x41) :|: TRUE f49_out(x42) -> f48_out(x42) :|: TRUE f2_in(x43) -> f4_in(x43) :|: TRUE f526_in(x45) -> f535_in(x45) :|: TRUE f535_out(x47) -> f526_out(x47) :|: TRUE f578_out(x51) -> f570_out(.(x52, x51)) :|: TRUE f570_in(.(x53, x54)) -> f578_in(x54) :|: TRUE f4_in(x55) -> f6_in(x55) :|: TRUE f46_in(x59) -> f48_in(x59) :|: TRUE f48_out(x60) -> f46_out(x60) :|: TRUE f569_in(.(T114, T115)) -> f573_in :|: TRUE f573_out -> f569_out(.(x62, x63)) :|: TRUE f53_in -> f53_out :|: TRUE f512_out(x65) -> f47_out(x65) :|: TRUE f47_in(x66) -> f512_in(x66) :|: TRUE f541_out(x67) -> f542_in(x67) :|: TRUE f542_out(x68) -> f535_out(x68) :|: TRUE f535_in(x69) -> f541_in(x69) :|: TRUE f573_in -> f573_out :|: TRUE f46_out(x70) -> f61_out(x70) :|: TRUE f61_in(x71) -> f46_in(x71) :|: TRUE ---------------------------------------- (140) Obligation: Rules: f527_in(T135) -> f581_in :|: TRUE f581_out -> f527_out(x1) :|: TRUE f569_out(T94) -> f563_out(T94) :|: TRUE f563_in(x2) -> f569_in(x2) :|: TRUE f570_out(x3) -> f563_out(x3) :|: TRUE f563_in(x4) -> f570_in(x4) :|: TRUE f6_in(T17) -> f9_in(T17) :|: TRUE f581_in -> f581_out :|: TRUE f47_out(x7) -> f25_out(x8) :|: TRUE f46_out(x9) -> f47_in(x10) :|: TRUE f25_in(T40) -> f46_in(T40) :|: TRUE f13_out(x11) -> f11_out(x11) :|: TRUE f11_in(x12) -> f13_in(x12) :|: TRUE f578_in(T124) -> f541_in(T124) :|: TRUE f541_out(x13) -> f578_out(x13) :|: TRUE f50_in(.(T70, T71)) -> f61_in(T71) :|: TRUE f61_out(x16) -> f50_out(.(x17, x16)) :|: TRUE f563_out(x18) -> f541_out(x18) :|: TRUE f541_in(x19) -> f563_in(x19) :|: TRUE f527_out(x20) -> f512_out(x20) :|: TRUE f512_in(x21) -> f527_in(x21) :|: TRUE f526_out(x22) -> f512_out(x22) :|: TRUE f512_in(x23) -> f526_in(x23) :|: TRUE f542_in(x24) -> f47_in(x24) :|: TRUE f47_out(x25) -> f542_out(x25) :|: TRUE f49_in(.(T61, T62)) -> f53_in :|: TRUE f53_out -> f49_out(.(x27, x28)) :|: TRUE f12_in(x31) -> f2_in(x31) :|: TRUE f13_in(x33) -> f25_in(x33) :|: TRUE f25_out(x35) -> f13_out(x35) :|: TRUE f11_out(x36) -> f12_in(x36) :|: TRUE f9_in(x37) -> f11_in(x37) :|: TRUE f48_in(x39) -> f50_in(x39) :|: TRUE f48_in(x40) -> f49_in(x40) :|: TRUE f50_out(x41) -> f48_out(x41) :|: TRUE f49_out(x42) -> f48_out(x42) :|: TRUE f2_in(x43) -> f4_in(x43) :|: TRUE f526_in(x45) -> f535_in(x45) :|: TRUE f535_out(x47) -> f526_out(x47) :|: TRUE f578_out(x51) -> f570_out(.(x52, x51)) :|: TRUE f570_in(.(x53, x54)) -> f578_in(x54) :|: TRUE f4_in(x55) -> f6_in(x55) :|: TRUE f46_in(x59) -> f48_in(x59) :|: TRUE f48_out(x60) -> f46_out(x60) :|: TRUE f569_in(.(T114, T115)) -> f573_in :|: TRUE f573_out -> f569_out(.(x62, x63)) :|: TRUE f53_in -> f53_out :|: TRUE f512_out(x65) -> f47_out(x65) :|: TRUE f47_in(x66) -> f512_in(x66) :|: TRUE f541_out(x67) -> f542_in(x67) :|: TRUE f542_out(x68) -> f535_out(x68) :|: TRUE f535_in(x69) -> f541_in(x69) :|: TRUE f573_in -> f573_out :|: TRUE f46_out(x70) -> f61_out(x70) :|: TRUE f61_in(x71) -> f46_in(x71) :|: TRUE ---------------------------------------- (141) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (142) Obligation: Rules: f46_out(x9:0) -> f512_in(x10:0) :|: TRUE f47_out(x7:0) -> f48_in(x8:0) :|: TRUE f47_out(x25:0) -> f47_out(x25:0) :|: TRUE f541_out(x13:0) -> f541_out(.(x52:0, x13:0)) :|: TRUE f541_out(x67:0) -> f512_in(x67:0) :|: TRUE f48_in(.(T70:0, T71:0)) -> f48_in(T71:0) :|: TRUE f512_in(x23:0) -> f563_in(x23:0) :|: TRUE f512_in(x21:0) -> f47_out(x1:0) :|: TRUE f48_in(.(T61:0, T62:0)) -> f46_out(.(x27:0, x28:0)) :|: TRUE f563_in(.(T114:0, T115:0)) -> f541_out(.(x62:0, x63:0)) :|: TRUE f563_in(.(x53:0, x54:0)) -> f563_in(x54:0) :|: TRUE f46_out(x70:0) -> f46_out(.(x17:0, x70:0)) :|: TRUE ---------------------------------------- (143) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (144) Obligation: Rules: f46_out(x9:0) -> f512_in(x10:0) :|: TRUE f47_out(x7:0) -> f48_in(x8:0) :|: TRUE f47_out(x25:0) -> f47_out(x25:0) :|: TRUE f541_out(x13:0) -> f541_out(.(x52:0, x13:0)) :|: TRUE f541_out(x67:0) -> f512_in(x67:0) :|: TRUE f48_in(.(T70:0, T71:0)) -> f48_in(T71:0) :|: TRUE f512_in(x23:0) -> f563_in(x23:0) :|: TRUE f512_in(x21:0) -> f47_out(x1:0) :|: TRUE f48_in(.(T61:0, T62:0)) -> f46_out(.(x27:0, x28:0)) :|: TRUE f563_in(.(T114:0, T115:0)) -> f541_out(.(x62:0, x63:0)) :|: TRUE f563_in(.(x53:0, x54:0)) -> f563_in(x54:0) :|: TRUE f46_out(x70:0) -> f46_out(.(x17:0, x70:0)) :|: TRUE ---------------------------------------- (145) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f46_out(x9:0) -> f512_in(x10:0) :|: TRUE (2) f47_out(x7:0) -> f48_in(x8:0) :|: TRUE (3) f47_out(x25:0) -> f47_out(x25:0) :|: TRUE (4) f541_out(x13:0) -> f541_out(.(x52:0, x13:0)) :|: TRUE (5) f541_out(x67:0) -> f512_in(x67:0) :|: TRUE (6) f48_in(.(T70:0, T71:0)) -> f48_in(T71:0) :|: TRUE (7) f512_in(x23:0) -> f563_in(x23:0) :|: TRUE (8) f512_in(x21:0) -> f47_out(x1:0) :|: TRUE (9) f48_in(.(T61:0, T62:0)) -> f46_out(.(x27:0, x28:0)) :|: TRUE (10) f563_in(.(T114:0, T115:0)) -> f541_out(.(x62:0, x63:0)) :|: TRUE (11) f563_in(.(x53:0, x54:0)) -> f563_in(x54:0) :|: TRUE (12) f46_out(x70:0) -> f46_out(.(x17:0, x70:0)) :|: TRUE Arcs: (1) -> (7), (8) (2) -> (6), (9) (3) -> (2), (3) (4) -> (4), (5) (5) -> (7), (8) (6) -> (6), (9) (7) -> (10), (11) (8) -> (2), (3) (9) -> (1), (12) (10) -> (4), (5) (11) -> (10), (11) (12) -> (1), (12) This digraph is fully evaluated! ---------------------------------------- (146) Obligation: Termination digraph: Nodes: (1) f46_out(x9:0) -> f512_in(x10:0) :|: TRUE (2) f46_out(x70:0) -> f46_out(.(x17:0, x70:0)) :|: TRUE (3) f48_in(.(T61:0, T62:0)) -> f46_out(.(x27:0, x28:0)) :|: TRUE (4) f48_in(.(T70:0, T71:0)) -> f48_in(T71:0) :|: TRUE (5) f47_out(x7:0) -> f48_in(x8:0) :|: TRUE (6) f47_out(x25:0) -> f47_out(x25:0) :|: TRUE (7) f512_in(x21:0) -> f47_out(x1:0) :|: TRUE (8) f541_out(x67:0) -> f512_in(x67:0) :|: TRUE (9) f541_out(x13:0) -> f541_out(.(x52:0, x13:0)) :|: TRUE (10) f563_in(.(T114:0, T115:0)) -> f541_out(.(x62:0, x63:0)) :|: TRUE (11) f563_in(.(x53:0, x54:0)) -> f563_in(x54:0) :|: TRUE (12) f512_in(x23:0) -> f563_in(x23:0) :|: TRUE Arcs: (1) -> (7), (12) (2) -> (1), (2) (3) -> (1), (2) (4) -> (3), (4) (5) -> (3), (4) (6) -> (5), (6) (7) -> (5), (6) (8) -> (7), (12) (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: f46_out(x9:0) -> f512_in(x10:0) :|: TRUE f46_out(x70:0) -> f46_out(.(x70:0)) :|: TRUE f48_in(.(T62:0)) -> f46_out(.(x28:0)) :|: TRUE f48_in(.(T71:0)) -> f48_in(T71:0) :|: TRUE f47_out(x7:0) -> f48_in(x8:0) :|: TRUE f47_out(x25:0) -> f47_out(x25:0) :|: TRUE f512_in(x21:0) -> f47_out(x1:0) :|: TRUE f541_out(x67:0) -> f512_in(x67:0) :|: TRUE f541_out(x13:0) -> f541_out(.(x13:0)) :|: TRUE f563_in(.(T115:0)) -> f541_out(.(x63:0)) :|: TRUE f563_in(.(x54:0)) -> f563_in(x54:0) :|: TRUE f512_in(x23:0) -> f563_in(x23:0) :|: TRUE