/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern slowsort(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 1 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) UsableRulesReductionPairsProof [EQUIVALENT, 13 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) TRUE (23) PiDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) PiDP (26) PiDPToQDPProof [SOUND, 0 ms] (27) QDP (28) NonTerminationLoopProof [COMPLETE, 0 ms] (29) NO (30) PiDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) PiDP (33) PrologToPiTRSProof [SOUND, 0 ms] (34) PiTRS (35) DependencyPairsProof [EQUIVALENT, 0 ms] (36) PiDP (37) DependencyGraphProof [EQUIVALENT, 0 ms] (38) AND (39) PiDP (40) UsableRulesProof [EQUIVALENT, 1 ms] (41) PiDP (42) PiDPToQDPProof [EQUIVALENT, 0 ms] (43) QDP (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] (45) YES (46) PiDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) PiDP (49) PiDPToQDPProof [EQUIVALENT, 0 ms] (50) QDP (51) MRRProof [EQUIVALENT, 17 ms] (52) QDP (53) DependencyGraphProof [EQUIVALENT, 0 ms] (54) TRUE (55) PiDP (56) UsableRulesProof [EQUIVALENT, 0 ms] (57) PiDP (58) PiDPToQDPProof [SOUND, 0 ms] (59) QDP (60) NonTerminationLoopProof [COMPLETE, 0 ms] (61) NO (62) PiDP (63) UsableRulesProof [EQUIVALENT, 0 ms] (64) PiDP (65) PiDPToQDPProof [SOUND, 0 ms] (66) QDP (67) QDPSizeChangeProof [EQUIVALENT, 0 ms] (68) YES (69) PrologToDTProblemTransformerProof [SOUND, 40 ms] (70) TRIPLES (71) TriplesToPiDPProof [SOUND, 0 ms] (72) PiDP (73) DependencyGraphProof [EQUIVALENT, 0 ms] (74) AND (75) PiDP (76) UsableRulesProof [EQUIVALENT, 1 ms] (77) PiDP (78) PiDPToQDPProof [EQUIVALENT, 0 ms] (79) QDP (80) QDPSizeChangeProof [EQUIVALENT, 0 ms] (81) YES (82) PiDP (83) UsableRulesProof [EQUIVALENT, 0 ms] (84) PiDP (85) PiDPToQDPProof [SOUND, 0 ms] (86) QDP (87) NonTerminationLoopProof [COMPLETE, 0 ms] (88) NO (89) PiDP (90) UsableRulesProof [EQUIVALENT, 0 ms] (91) PiDP (92) PrologToTRSTransformerProof [SOUND, 36 ms] (93) QTRS (94) DependencyPairsProof [EQUIVALENT, 6 ms] (95) QDP (96) DependencyGraphProof [EQUIVALENT, 0 ms] (97) AND (98) QDP (99) MNOCProof [EQUIVALENT, 0 ms] (100) QDP (101) UsableRulesProof [EQUIVALENT, 0 ms] (102) QDP (103) QReductionProof [EQUIVALENT, 0 ms] (104) QDP (105) QDPSizeChangeProof [EQUIVALENT, 0 ms] (106) YES (107) QDP (108) MNOCProof [EQUIVALENT, 0 ms] (109) QDP (110) UsableRulesProof [EQUIVALENT, 0 ms] (111) QDP (112) QReductionProof [EQUIVALENT, 0 ms] (113) QDP (114) QDPOrderProof [EQUIVALENT, 76 ms] (115) QDP (116) PisEmptyProof [EQUIVALENT, 0 ms] (117) YES (118) QDP (119) MNOCProof [EQUIVALENT, 0 ms] (120) QDP (121) UsableRulesProof [EQUIVALENT, 0 ms] (122) QDP (123) QReductionProof [EQUIVALENT, 0 ms] (124) QDP (125) NonTerminationLoopProof [COMPLETE, 0 ms] (126) NO (127) QDP (128) MNOCProof [EQUIVALENT, 0 ms] (129) QDP (130) UsableRulesProof [EQUIVALENT, 0 ms] (131) QDP (132) QReductionProof [EQUIVALENT, 0 ms] (133) QDP (134) QDPSizeChangeProof [EQUIVALENT, 0 ms] (135) YES (136) PrologToIRSwTTransformerProof [SOUND, 33 ms] (137) AND (138) IRSwT (139) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (140) TRUE (141) IRSwT (142) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (143) IRSwT (144) IntTRSCompressionProof [EQUIVALENT, 28 ms] (145) IRSwT (146) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (147) IRSwT (148) IRSwTTerminationDigraphProof [EQUIVALENT, 1 ms] (149) IRSwT (150) FilterProof [EQUIVALENT, 0 ms] (151) IntTRS (152) IntTRSPeriodicNontermProof [COMPLETE, 0 ms] (153) NO (154) IRSwT (155) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (156) TRUE (157) IRSwT (158) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (159) IRSwT ---------------------------------------- (0) Obligation: Clauses: slowsort(X, Y) :- ','(perm(X, Y), sorted(Y)). sorted([]). sorted(.(X, [])). sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z))). perm([], []). perm(.(X, .(Y, [])), .(U, .(V, []))) :- ','(delete(U, .(X, Y), Z), perm(Z, V)). delete(X, .(X, Y), Y). delete(X, .(Y, Z), W) :- delete(X, Z, W). le(s(X), s(Y)) :- le(X, Y). le(0, s(X)). le(0, 0). Query: slowsort(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: slowsort_in_2: (f,b) perm_in_2: (f,b) delete_in_3: (b,f,f) sorted_in_1: (b) le_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag ---------------------------------------- (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: SLOWSORT_IN_AG(X, Y) -> U1_AG(X, Y, perm_in_ag(X, Y)) SLOWSORT_IN_AG(X, Y) -> PERM_IN_AG(X, Y) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_GAA(U, .(X, Y), Z) DELETE_IN_GAA(X, .(Y, Z), W) -> U7_GAA(X, Y, Z, W, delete_in_gaa(X, Z, W)) DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_AG(X, Y, U, V, perm_in_ag(Z, V)) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) U1_AG(X, Y, perm_out_ag(X, Y)) -> U2_AG(X, Y, sorted_in_g(Y)) U1_AG(X, Y, perm_out_ag(X, Y)) -> SORTED_IN_G(Y) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z))) U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag SLOWSORT_IN_AG(x1, x2) = SLOWSORT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) U7_GAA(x1, x2, x3, x4, x5) = U7_GAA(x5) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x5) U2_AG(x1, x2, x3) = U2_AG(x3) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, x3, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x3) U4_G(x1, x2, x3, x4) = U4_G(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: SLOWSORT_IN_AG(X, Y) -> U1_AG(X, Y, perm_in_ag(X, Y)) SLOWSORT_IN_AG(X, Y) -> PERM_IN_AG(X, Y) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_GAA(U, .(X, Y), Z) DELETE_IN_GAA(X, .(Y, Z), W) -> U7_GAA(X, Y, Z, W, delete_in_gaa(X, Z, W)) DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_AG(X, Y, U, V, perm_in_ag(Z, V)) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) U1_AG(X, Y, perm_out_ag(X, Y)) -> U2_AG(X, Y, sorted_in_g(Y)) U1_AG(X, Y, perm_out_ag(X, Y)) -> SORTED_IN_G(Y) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z))) U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag SLOWSORT_IN_AG(x1, x2) = SLOWSORT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) U7_GAA(x1, x2, x3, x4, x5) = U7_GAA(x5) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x5) U2_AG(x1, x2, x3) = U2_AG(x3) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, x3, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x3) U4_G(x1, x2, x3, x4) = U4_G(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: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag LE_IN_GG(x1, x2) = LE_IN_GG(x1, 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: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) 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: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 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: *LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, 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: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, 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: U3_G(Y, Z, le_out_gg) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg U8_gg(le_out_gg) -> le_out_gg The set Q consists of the following terms: le_in_gg(x0, x1) U8_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: le_in_gg(s(X), s(Y)) -> U8_gg(le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + 2*x_2 POL(0) = 0 POL(SORTED_IN_G(x_1)) = x_1 POL(U3_G(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U8_gg(x_1)) = 2*x_1 POL(le_in_gg(x_1, x_2)) = x_1 + x_2 POL(le_out_gg) = 0 POL(s(x_1)) = 2 + 2*x_1 ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U3_G(Y, Z, le_out_gg) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: U8_gg(le_out_gg) -> le_out_gg The set Q consists of the following terms: le_in_gg(x0, x1) U8_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (22) TRUE ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X) -> DELETE_IN_GAA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = DELETE_IN_GAA(X) evaluates to t =DELETE_IN_GAA(X) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from DELETE_IN_GAA(X) to DELETE_IN_GAA(X). ---------------------------------------- (29) NO ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) The TRS R consists of the following rules: delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: slowsort_in_2: (f,b) perm_in_2: (f,b) delete_in_3: (b,f,f) sorted_in_1: (b) le_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (34) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) ---------------------------------------- (35) 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: SLOWSORT_IN_AG(X, Y) -> U1_AG(X, Y, perm_in_ag(X, Y)) SLOWSORT_IN_AG(X, Y) -> PERM_IN_AG(X, Y) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_GAA(U, .(X, Y), Z) DELETE_IN_GAA(X, .(Y, Z), W) -> U7_GAA(X, Y, Z, W, delete_in_gaa(X, Z, W)) DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_AG(X, Y, U, V, perm_in_ag(Z, V)) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) U1_AG(X, Y, perm_out_ag(X, Y)) -> U2_AG(X, Y, sorted_in_g(Y)) U1_AG(X, Y, perm_out_ag(X, Y)) -> SORTED_IN_G(Y) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z))) U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) SLOWSORT_IN_AG(x1, x2) = SLOWSORT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x3, x4, x5) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) U7_GAA(x1, x2, x3, x4, x5) = U7_GAA(x1, x5) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x3, x4, x5) U2_AG(x1, x2, x3) = U2_AG(x2, x3) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x1, x2, x3, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x1, x2, x3) U4_G(x1, x2, x3, x4) = U4_G(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) Obligation: Pi DP problem: The TRS P consists of the following rules: SLOWSORT_IN_AG(X, Y) -> U1_AG(X, Y, perm_in_ag(X, Y)) SLOWSORT_IN_AG(X, Y) -> PERM_IN_AG(X, Y) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_GAA(U, .(X, Y), Z) DELETE_IN_GAA(X, .(Y, Z), W) -> U7_GAA(X, Y, Z, W, delete_in_gaa(X, Z, W)) DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_AG(X, Y, U, V, perm_in_ag(Z, V)) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) U1_AG(X, Y, perm_out_ag(X, Y)) -> U2_AG(X, Y, sorted_in_g(Y)) U1_AG(X, Y, perm_out_ag(X, Y)) -> SORTED_IN_G(Y) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z))) U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) SLOWSORT_IN_AG(x1, x2) = SLOWSORT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x3, x4, x5) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) U7_GAA(x1, x2, x3, x4, x5) = U7_GAA(x1, x5) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x3, x4, x5) U2_AG(x1, x2, x3) = U2_AG(x2, x3) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x1, x2, x3, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x1, x2, x3) U4_G(x1, x2, x3, x4) = U4_G(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (37) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes. ---------------------------------------- (38) Complex Obligation (AND) ---------------------------------------- (39) Obligation: Pi DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (40) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (41) Obligation: Pi DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (42) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (44) 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: *LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (45) YES ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (49) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) The set Q consists of the following terms: le_in_gg(x0, x1) U8_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) Strictly oriented rules of the TRS R: le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + x_2 POL(0) = 2 POL(SORTED_IN_G(x_1)) = 2 + 2*x_1 POL(U3_G(x_1, x_2, x_3, x_4)) = 1 + x_1 + 2*x_2 + 2*x_3 + x_4 POL(U8_gg(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(le_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 POL(le_out_gg(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(s(x_1)) = 2*x_1 ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) The set Q consists of the following terms: le_in_gg(x0, x1) U8_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (54) TRUE ---------------------------------------- (55) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (56) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (57) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (58) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X) -> DELETE_IN_GAA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (60) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = DELETE_IN_GAA(X) evaluates to t =DELETE_IN_GAA(X) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from DELETE_IN_GAA(X) to DELETE_IN_GAA(X). ---------------------------------------- (61) NO ---------------------------------------- (62) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x3, x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x3, x4, x5) U2_ag(x1, x2, x3) = U2_ag(x2, x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g(x1) U3_g(x1, x2, x3, x4) = U3_g(x1, x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x1, x2, x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg(x1, x2) U4_g(x1, x2, x3, x4) = U4_g(x1, x2, x3, x4) slowsort_out_ag(x1, x2) = slowsort_out_ag(x2) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x3, x4, x5) 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: U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) The TRS R consists of the following rules: delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa(x1) U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x1, x5) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (65) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AG(U, V, delete_out_gaa(U)) -> PERM_IN_AG(V) PERM_IN_AG(.(U, .(V, []))) -> U5_AG(U, V, delete_in_gaa(U)) The TRS R consists of the following rules: delete_in_gaa(X) -> delete_out_gaa(X) delete_in_gaa(X) -> U7_gaa(X, delete_in_gaa(X)) U7_gaa(X, delete_out_gaa(X)) -> delete_out_gaa(X) The set Q consists of the following terms: delete_in_gaa(x0) U7_gaa(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (67) 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: *PERM_IN_AG(.(U, .(V, []))) -> U5_AG(U, V, delete_in_gaa(U)) The graph contains the following edges 1 > 1, 1 > 2 *U5_AG(U, V, delete_out_gaa(U)) -> PERM_IN_AG(V) The graph contains the following edges 2 >= 1 ---------------------------------------- (68) YES ---------------------------------------- (69) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(slowsort X Y)", "(',' (perm X Y) (sorted Y))" ], [ "(sorted ([]))", null ], [ "(sorted (. X ([])))", null ], [ "(sorted (. X (. Y Z)))", "(',' (le X Y) (sorted (. Y Z)))" ], [ "(perm ([]) ([]))", null ], [ "(perm (. X (. Y ([]))) (. U (. V ([]))))", "(',' (delete U (. X Y) Z) (perm Z V))" ], [ "(delete X (. X Y) Y)", null ], [ "(delete X (. Y Z) W)", "(delete X Z W)" ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (0) (s X))", null ], [ "(le (0) (0))", null ] ] }, "graph": { "nodes": { "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "48": { "goal": [ { "clause": 4, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }, { "clause": 5, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "390": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T18 (. T19 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "272": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "470": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T94 (. T96 T97) X106)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": ["X106"], "exprvars": [] } }, "273": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "471": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T102 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T95"], "free": [], "exprvars": [] } }, "153": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (delete T18 (. T20 T21) X22) (perm X22 T19)) (sorted (. T18 (. T19 ([])))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": ["X22"], "exprvars": [] } }, "472": { "goal": [ { "clause": 1, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" }, { "clause": 2, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" }, { "clause": 3, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "473": { "goal": [ { "clause": 2, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" }, { "clause": 3, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "397": { "goal": [ { "clause": 4, "scope": 6, "term": "(perm T26 T19)" }, { "clause": 5, "scope": 6, "term": "(perm T26 T19)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "474": { "goal": [{ "clause": 3, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "511": { "goal": [{ "clause": 2, "scope": 9, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "512": { "goal": [{ "clause": 3, "scope": 9, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": 5, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "483": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T114 T115) (sorted (. T115 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "487": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "400": { "goal": [{ "clause": 4, "scope": 6, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "488": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "401": { "goal": [{ "clause": 5, "scope": 6, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "525": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "526": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "406": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "527": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "61": { "goal": [ { "clause": 1, "scope": 3, "term": "(sorted ([]))" }, { "clause": 2, "scope": 3, "term": "(sorted ([]))" }, { "clause": 3, "scope": 3, "term": "(sorted ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "407": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "62": { "goal": [{ "clause": 1, "scope": 3, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "63": { "goal": [ { "clause": 2, "scope": 3, "term": "(sorted ([]))" }, { "clause": 3, "scope": 3, "term": "(sorted ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "409": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "490": { "goal": [ { "clause": 8, "scope": 8, "term": "(le T114 T115)" }, { "clause": 9, "scope": 8, "term": "(le T114 T115)" }, { "clause": 10, "scope": 8, "term": "(le T114 T115)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "492": { "goal": [{ "clause": 8, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "493": { "goal": [ { "clause": 9, "scope": 8, "term": "(le T114 T115)" }, { "clause": 10, "scope": 8, "term": "(le T114 T115)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "132": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": 3, "scope": 3, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "135": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "498": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T128 T129)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T129" ], "free": [], "exprvars": [] } }, "499": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "260": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "261": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T26 T19) (sorted (. T18 (. T19 ([])))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "340": { "goal": [ { "clause": 6, "scope": 5, "term": "(delete T52 T55 X59)" }, { "clause": 7, "scope": 5, "term": "(delete T52 T55 X59)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "341": { "goal": [{ "clause": 6, "scope": 5, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "265": { "goal": [ { "clause": 6, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" }, { "clause": 7, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "342": { "goal": [{ "clause": 7, "scope": 5, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "343": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "267": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "344": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "345": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "389": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T76 T79 X88)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T76"], "free": ["X88"], "exprvars": [] } }, "500": { "goal": [{ "clause": 9, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "347": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "468": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (delete T94 (. T96 T97) X106) (perm X106 T95))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T94", "T95" ], "free": ["X106"], "exprvars": [] } }, "501": { "goal": [{ "clause": 10, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "469": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "502": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "503": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "504": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "505": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "506": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "507": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "508": { "goal": [ { "clause": 1, "scope": 9, "term": "(sorted (. T115 ([])))" }, { "clause": 2, "scope": 9, "term": "(sorted (. T115 ([])))" }, { "clause": 3, "scope": 9, "term": "(sorted (. T115 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "509": { "goal": [ { "clause": 2, "scope": 9, "term": "(sorted (. T115 ([])))" }, { "clause": 3, "scope": 9, "term": "(sorted (. T115 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 47, "label": "ONLY EVAL with clause\nslowsort(X3, X4) :- ','(perm(X3, X4), sorted(X4)).\nand substitutionT1 -> T7,\nX3 -> T7,\nT2 -> T6,\nX4 -> T6,\nT5 -> T7" }, { "from": 47, "to": 48, "label": "CASE" }, { "from": 48, "to": 49, "label": "PARALLEL" }, { "from": 48, "to": 50, "label": "PARALLEL" }, { "from": 49, "to": 54, "label": "EVAL with clause\nperm([], []).\nand substitutionT7 -> [],\nT6 -> []" }, { "from": 49, "to": 55, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 153, "label": "EVAL with clause\nperm(.(X18, .(X19, [])), .(X20, .(X21, []))) :- ','(delete(X20, .(X18, X19), X22), perm(X22, X21)).\nand substitutionX18 -> T20,\nX19 -> T21,\nT7 -> .(T20, .(T21, [])),\nX20 -> T18,\nX21 -> T19,\nT6 -> .(T18, .(T19, [])),\nT16 -> T20,\nT17 -> T21" }, { "from": 50, "to": 259, "label": "EVAL-BACKTRACK" }, { "from": 54, "to": 61, "label": "CASE" }, { "from": 61, "to": 62, "label": "PARALLEL" }, { "from": 61, "to": 63, "label": "PARALLEL" }, { "from": 62, "to": 132, "label": "ONLY EVAL with clause\nsorted([]).\nand substitution" }, { "from": 63, "to": 134, "label": "BACKTRACK\nfor clause: sorted(.(X, []))because of non-unification" }, { "from": 132, "to": 133, "label": "SUCCESS" }, { "from": 134, "to": 135, "label": "BACKTRACK\nfor clause: sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z)))because of non-unification" }, { "from": 153, "to": 260, "label": "SPLIT 1" }, { "from": 153, "to": 261, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nreplacements:X22 -> T26" }, { "from": 260, "to": 265, "label": "CASE" }, { "from": 261, "to": 389, "label": "SPLIT 1" }, { "from": 261, "to": 390, "label": "SPLIT 2\nnew knowledge:\nT19 is ground" }, { "from": 265, "to": 267, "label": "PARALLEL" }, { "from": 265, "to": 268, "label": "PARALLEL" }, { "from": 267, "to": 271, "label": "EVAL with clause\ndelete(X39, .(X39, X40), X40).\nand substitutionT18 -> T39,\nX39 -> T39,\nT20 -> T39,\nT21 -> T40,\nX40 -> T40,\nX22 -> T40" }, { "from": 267, "to": 272, "label": "EVAL-BACKTRACK" }, { "from": 268, "to": 339, "label": "ONLY EVAL with clause\ndelete(X55, .(X56, X57), X58) :- delete(X55, X57, X58).\nand substitutionT18 -> T52,\nX55 -> T52,\nT20 -> T53,\nX56 -> T53,\nT21 -> T55,\nX57 -> T55,\nX22 -> X59,\nX58 -> X59,\nT54 -> T55" }, { "from": 271, "to": 273, "label": "SUCCESS" }, { "from": 339, "to": 340, "label": "CASE" }, { "from": 340, "to": 341, "label": "PARALLEL" }, { "from": 340, "to": 342, "label": "PARALLEL" }, { "from": 341, "to": 343, "label": "EVAL with clause\ndelete(X72, .(X72, X73), X73).\nand substitutionT52 -> T68,\nX72 -> T68,\nX73 -> T69,\nT55 -> .(T68, T69),\nX59 -> T69" }, { "from": 341, "to": 344, "label": "EVAL-BACKTRACK" }, { "from": 342, "to": 346, "label": "EVAL with clause\ndelete(X84, .(X85, X86), X87) :- delete(X84, X86, X87).\nand substitutionT52 -> T76,\nX84 -> T76,\nX85 -> T77,\nX86 -> T79,\nT55 -> .(T77, T79),\nX59 -> X88,\nX87 -> X88,\nT78 -> T79" }, { "from": 342, "to": 347, "label": "EVAL-BACKTRACK" }, { "from": 343, "to": 345, "label": "SUCCESS" }, { "from": 346, "to": 339, "label": "INSTANCE with matching:\nT52 -> T76\nT55 -> T79\nX59 -> X88" }, { "from": 389, "to": 397, "label": "CASE" }, { "from": 390, "to": 472, "label": "CASE" }, { "from": 397, "to": 400, "label": "PARALLEL" }, { "from": 397, "to": 401, "label": "PARALLEL" }, { "from": 400, "to": 406, "label": "EVAL with clause\nperm([], []).\nand substitutionT26 -> [],\nT19 -> []" }, { "from": 400, "to": 407, "label": "EVAL-BACKTRACK" }, { "from": 401, "to": 468, "label": "EVAL with clause\nperm(.(X102, .(X103, [])), .(X104, .(X105, []))) :- ','(delete(X104, .(X102, X103), X106), perm(X106, X105)).\nand substitutionX102 -> T96,\nX103 -> T97,\nT26 -> .(T96, .(T97, [])),\nX104 -> T94,\nX105 -> T95,\nT19 -> .(T94, .(T95, [])),\nT92 -> T96,\nT93 -> T97" }, { "from": 401, "to": 469, "label": "EVAL-BACKTRACK" }, { "from": 406, "to": 409, "label": "SUCCESS" }, { "from": 468, "to": 470, "label": "SPLIT 1" }, { "from": 468, "to": 471, "label": "SPLIT 2\nnew knowledge:\nT94 is ground\nreplacements:X106 -> T102" }, { "from": 470, "to": 260, "label": "INSTANCE with matching:\nT18 -> T94\nT20 -> T96\nT21 -> T97\nX22 -> X106" }, { "from": 471, "to": 389, "label": "INSTANCE with matching:\nT26 -> T102\nT19 -> T95" }, { "from": 472, "to": 473, "label": "BACKTRACK\nfor clause: sorted([])because of non-unification" }, { "from": 473, "to": 474, "label": "BACKTRACK\nfor clause: sorted(.(X, []))because of non-unification" }, { "from": 474, "to": 483, "label": "ONLY EVAL with clause\nsorted(.(X124, .(X125, X126))) :- ','(le(X124, X125), sorted(.(X125, X126))).\nand substitutionT18 -> T114,\nX124 -> T114,\nT19 -> T115,\nX125 -> T115,\nX126 -> []" }, { "from": 483, "to": 487, "label": "SPLIT 1" }, { "from": 483, "to": 488, "label": "SPLIT 2\nnew knowledge:\nT114 is ground\nT115 is ground" }, { "from": 487, "to": 490, "label": "CASE" }, { "from": 488, "to": 508, "label": "CASE" }, { "from": 490, "to": 492, "label": "PARALLEL" }, { "from": 490, "to": 493, "label": "PARALLEL" }, { "from": 492, "to": 498, "label": "EVAL with clause\nle(s(X139), s(X140)) :- le(X139, X140).\nand substitutionX139 -> T128,\nT114 -> s(T128),\nX140 -> T129,\nT115 -> s(T129)" }, { "from": 492, "to": 499, "label": "EVAL-BACKTRACK" }, { "from": 493, "to": 500, "label": "PARALLEL" }, { "from": 493, "to": 501, "label": "PARALLEL" }, { "from": 498, "to": 487, "label": "INSTANCE with matching:\nT114 -> T128\nT115 -> T129" }, { "from": 500, "to": 502, "label": "EVAL with clause\nle(0, s(X147)).\nand substitutionT114 -> 0,\nX147 -> T136,\nT115 -> s(T136)" }, { "from": 500, "to": 503, "label": "EVAL-BACKTRACK" }, { "from": 501, "to": 505, "label": "EVAL with clause\nle(0, 0).\nand substitutionT114 -> 0,\nT115 -> 0" }, { "from": 501, "to": 506, "label": "EVAL-BACKTRACK" }, { "from": 502, "to": 504, "label": "SUCCESS" }, { "from": 505, "to": 507, "label": "SUCCESS" }, { "from": 508, "to": 509, "label": "BACKTRACK\nfor clause: sorted([])because of non-unification" }, { "from": 509, "to": 511, "label": "PARALLEL" }, { "from": 509, "to": 512, "label": "PARALLEL" }, { "from": 511, "to": 525, "label": "ONLY EVAL with clause\nsorted(.(X152, [])).\nand substitutionT115 -> T141,\nX152 -> T141" }, { "from": 512, "to": 527, "label": "BACKTRACK\nfor clause: sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z)))because of non-unification" }, { "from": 525, "to": 526, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (70) Obligation: Triples: deleteA(X1, .(X2, X3), X4) :- deleteA(X1, X3, X4). deleteB(X1, X2, X3, X4) :- deleteA(X1, X3, X4). permC(.(X1, .(X2, [])), .(X3, .(X4, []))) :- deleteB(X3, X1, X2, X5). permC(.(X1, .(X2, [])), .(X3, .(X4, []))) :- ','(deletecB(X3, X1, X2, X5), permC(X5, X4)). leD(s(X1), s(X2)) :- leD(X1, X2). slowsortE(.(X1, .(X2, [])), .(X3, .(X4, []))) :- deleteB(X3, X1, X2, X5). slowsortE(.(X1, .(X2, [])), .(X3, .(X4, []))) :- ','(deletecB(X3, X1, X2, X5), permC(X5, X4)). slowsortE(.(X1, .(X2, [])), .(X3, .(X4, []))) :- ','(deletecB(X3, X1, X2, X5), ','(permcC(X5, X4), leD(X3, X4))). Clauses: deletecA(X1, .(X1, X2), X2). deletecA(X1, .(X2, X3), X4) :- deletecA(X1, X3, X4). deletecB(X1, X1, X2, X2). deletecB(X1, X2, X3, X4) :- deletecA(X1, X3, X4). permcC([], []). permcC(.(X1, .(X2, [])), .(X3, .(X4, []))) :- ','(deletecB(X3, X1, X2, X5), permcC(X5, X4)). lecD(s(X1), s(X2)) :- lecD(X1, X2). lecD(0, s(X1)). lecD(0, 0). Afs: slowsortE(x1, x2) = slowsortE(x2) ---------------------------------------- (71) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: slowsortE_in_2: (f,b) deleteB_in_4: (b,f,f,f) deleteA_in_3: (b,f,f) deletecB_in_4: (b,f,f,f) deletecA_in_3: (b,f,f) permC_in_2: (f,b) permcC_in_2: (f,b) leD_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SLOWSORTE_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U7_AG(X1, X2, X3, X4, deleteB_in_gaaa(X3, X1, X2, X5)) SLOWSORTE_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> DELETEB_IN_GAAA(X3, X1, X2, X5) DELETEB_IN_GAAA(X1, X2, X3, X4) -> U2_GAAA(X1, X2, X3, X4, deleteA_in_gaa(X1, X3, X4)) DELETEB_IN_GAAA(X1, X2, X3, X4) -> DELETEA_IN_GAA(X1, X3, X4) DELETEA_IN_GAA(X1, .(X2, X3), X4) -> U1_GAA(X1, X2, X3, X4, deleteA_in_gaa(X1, X3, X4)) DELETEA_IN_GAA(X1, .(X2, X3), X4) -> DELETEA_IN_GAA(X1, X3, X4) SLOWSORTE_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U8_AG(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U8_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U9_AG(X1, X2, X3, X4, permC_in_ag(X5, X4)) U8_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> PERMC_IN_AG(X5, X4) PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U3_AG(X1, X2, X3, X4, deleteB_in_gaaa(X3, X1, X2, X5)) PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> DELETEB_IN_GAAA(X3, X1, X2, X5) PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U4_AG(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U4_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U5_AG(X1, X2, X3, X4, permC_in_ag(X5, X4)) U4_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> PERMC_IN_AG(X5, X4) U8_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U10_AG(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U10_AG(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> U11_AG(X1, X2, X3, X4, leD_in_gg(X3, X4)) U10_AG(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> LED_IN_GG(X3, X4) LED_IN_GG(s(X1), s(X2)) -> U6_GG(X1, X2, leD_in_gg(X1, X2)) LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) The TRS R consists of the following rules: deletecB_in_gaaa(X1, X1, X2, X2) -> deletecB_out_gaaa(X1, X1, X2, X2) deletecB_in_gaaa(X1, X2, X3, X4) -> U14_gaaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) deletecA_in_gaa(X1, .(X1, X2), X2) -> deletecA_out_gaa(X1, .(X1, X2), X2) deletecA_in_gaa(X1, .(X2, X3), X4) -> U13_gaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U13_gaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecA_out_gaa(X1, .(X2, X3), X4) U14_gaaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecB_out_gaaa(X1, X2, X3, X4) permcC_in_ag([], []) -> permcC_out_ag([], []) permcC_in_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U15_ag(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U15_ag(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U16_ag(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U16_ag(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> permcC_out_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] deleteB_in_gaaa(x1, x2, x3, x4) = deleteB_in_gaaa(x1) deleteA_in_gaa(x1, x2, x3) = deleteA_in_gaa(x1) deletecB_in_gaaa(x1, x2, x3, x4) = deletecB_in_gaaa(x1) deletecB_out_gaaa(x1, x2, x3, x4) = deletecB_out_gaaa(x1) U14_gaaa(x1, x2, x3, x4, x5) = U14_gaaa(x1, x5) deletecA_in_gaa(x1, x2, x3) = deletecA_in_gaa(x1) deletecA_out_gaa(x1, x2, x3) = deletecA_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x5) permC_in_ag(x1, x2) = permC_in_ag(x2) permcC_in_ag(x1, x2) = permcC_in_ag(x2) permcC_out_ag(x1, x2) = permcC_out_ag(x2) U15_ag(x1, x2, x3, x4, x5) = U15_ag(x3, x4, x5) U16_ag(x1, x2, x3, x4, x5) = U16_ag(x3, x4, x5) leD_in_gg(x1, x2) = leD_in_gg(x1, x2) s(x1) = s(x1) SLOWSORTE_IN_AG(x1, x2) = SLOWSORTE_IN_AG(x2) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x3, x4, x5) DELETEB_IN_GAAA(x1, x2, x3, x4) = DELETEB_IN_GAAA(x1) U2_GAAA(x1, x2, x3, x4, x5) = U2_GAAA(x1, x5) DELETEA_IN_GAA(x1, x2, x3) = DELETEA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x3, x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x3, x4, x5) PERMC_IN_AG(x1, x2) = PERMC_IN_AG(x2) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x3, x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x3, x4, x5) U11_AG(x1, x2, x3, x4, x5) = U11_AG(x3, x4, x5) LED_IN_GG(x1, x2) = LED_IN_GG(x1, x2) U6_GG(x1, x2, x3) = U6_GG(x1, x2, x3) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (72) Obligation: Pi DP problem: The TRS P consists of the following rules: SLOWSORTE_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U7_AG(X1, X2, X3, X4, deleteB_in_gaaa(X3, X1, X2, X5)) SLOWSORTE_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> DELETEB_IN_GAAA(X3, X1, X2, X5) DELETEB_IN_GAAA(X1, X2, X3, X4) -> U2_GAAA(X1, X2, X3, X4, deleteA_in_gaa(X1, X3, X4)) DELETEB_IN_GAAA(X1, X2, X3, X4) -> DELETEA_IN_GAA(X1, X3, X4) DELETEA_IN_GAA(X1, .(X2, X3), X4) -> U1_GAA(X1, X2, X3, X4, deleteA_in_gaa(X1, X3, X4)) DELETEA_IN_GAA(X1, .(X2, X3), X4) -> DELETEA_IN_GAA(X1, X3, X4) SLOWSORTE_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U8_AG(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U8_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U9_AG(X1, X2, X3, X4, permC_in_ag(X5, X4)) U8_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> PERMC_IN_AG(X5, X4) PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U3_AG(X1, X2, X3, X4, deleteB_in_gaaa(X3, X1, X2, X5)) PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> DELETEB_IN_GAAA(X3, X1, X2, X5) PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U4_AG(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U4_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U5_AG(X1, X2, X3, X4, permC_in_ag(X5, X4)) U4_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> PERMC_IN_AG(X5, X4) U8_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U10_AG(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U10_AG(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> U11_AG(X1, X2, X3, X4, leD_in_gg(X3, X4)) U10_AG(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> LED_IN_GG(X3, X4) LED_IN_GG(s(X1), s(X2)) -> U6_GG(X1, X2, leD_in_gg(X1, X2)) LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) The TRS R consists of the following rules: deletecB_in_gaaa(X1, X1, X2, X2) -> deletecB_out_gaaa(X1, X1, X2, X2) deletecB_in_gaaa(X1, X2, X3, X4) -> U14_gaaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) deletecA_in_gaa(X1, .(X1, X2), X2) -> deletecA_out_gaa(X1, .(X1, X2), X2) deletecA_in_gaa(X1, .(X2, X3), X4) -> U13_gaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U13_gaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecA_out_gaa(X1, .(X2, X3), X4) U14_gaaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecB_out_gaaa(X1, X2, X3, X4) permcC_in_ag([], []) -> permcC_out_ag([], []) permcC_in_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U15_ag(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U15_ag(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U16_ag(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U16_ag(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> permcC_out_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] deleteB_in_gaaa(x1, x2, x3, x4) = deleteB_in_gaaa(x1) deleteA_in_gaa(x1, x2, x3) = deleteA_in_gaa(x1) deletecB_in_gaaa(x1, x2, x3, x4) = deletecB_in_gaaa(x1) deletecB_out_gaaa(x1, x2, x3, x4) = deletecB_out_gaaa(x1) U14_gaaa(x1, x2, x3, x4, x5) = U14_gaaa(x1, x5) deletecA_in_gaa(x1, x2, x3) = deletecA_in_gaa(x1) deletecA_out_gaa(x1, x2, x3) = deletecA_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x5) permC_in_ag(x1, x2) = permC_in_ag(x2) permcC_in_ag(x1, x2) = permcC_in_ag(x2) permcC_out_ag(x1, x2) = permcC_out_ag(x2) U15_ag(x1, x2, x3, x4, x5) = U15_ag(x3, x4, x5) U16_ag(x1, x2, x3, x4, x5) = U16_ag(x3, x4, x5) leD_in_gg(x1, x2) = leD_in_gg(x1, x2) s(x1) = s(x1) SLOWSORTE_IN_AG(x1, x2) = SLOWSORTE_IN_AG(x2) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x3, x4, x5) DELETEB_IN_GAAA(x1, x2, x3, x4) = DELETEB_IN_GAAA(x1) U2_GAAA(x1, x2, x3, x4, x5) = U2_GAAA(x1, x5) DELETEA_IN_GAA(x1, x2, x3) = DELETEA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x3, x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x3, x4, x5) PERMC_IN_AG(x1, x2) = PERMC_IN_AG(x2) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x3, x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x3, x4, x5) U11_AG(x1, x2, x3, x4, x5) = U11_AG(x3, x4, x5) LED_IN_GG(x1, x2) = LED_IN_GG(x1, x2) U6_GG(x1, x2, x3) = U6_GG(x1, x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (73) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 15 less nodes. ---------------------------------------- (74) Complex Obligation (AND) ---------------------------------------- (75) Obligation: Pi DP problem: The TRS P consists of the following rules: LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) The TRS R consists of the following rules: deletecB_in_gaaa(X1, X1, X2, X2) -> deletecB_out_gaaa(X1, X1, X2, X2) deletecB_in_gaaa(X1, X2, X3, X4) -> U14_gaaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) deletecA_in_gaa(X1, .(X1, X2), X2) -> deletecA_out_gaa(X1, .(X1, X2), X2) deletecA_in_gaa(X1, .(X2, X3), X4) -> U13_gaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U13_gaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecA_out_gaa(X1, .(X2, X3), X4) U14_gaaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecB_out_gaaa(X1, X2, X3, X4) permcC_in_ag([], []) -> permcC_out_ag([], []) permcC_in_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U15_ag(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U15_ag(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U16_ag(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U16_ag(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> permcC_out_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] deletecB_in_gaaa(x1, x2, x3, x4) = deletecB_in_gaaa(x1) deletecB_out_gaaa(x1, x2, x3, x4) = deletecB_out_gaaa(x1) U14_gaaa(x1, x2, x3, x4, x5) = U14_gaaa(x1, x5) deletecA_in_gaa(x1, x2, x3) = deletecA_in_gaa(x1) deletecA_out_gaa(x1, x2, x3) = deletecA_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x5) permcC_in_ag(x1, x2) = permcC_in_ag(x2) permcC_out_ag(x1, x2) = permcC_out_ag(x2) U15_ag(x1, x2, x3, x4, x5) = U15_ag(x3, x4, x5) U16_ag(x1, x2, x3, x4, x5) = U16_ag(x3, x4, x5) s(x1) = s(x1) LED_IN_GG(x1, x2) = LED_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (76) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (77) Obligation: Pi DP problem: The TRS P consists of the following rules: LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (78) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (80) 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: *LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (81) YES ---------------------------------------- (82) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETEA_IN_GAA(X1, .(X2, X3), X4) -> DELETEA_IN_GAA(X1, X3, X4) The TRS R consists of the following rules: deletecB_in_gaaa(X1, X1, X2, X2) -> deletecB_out_gaaa(X1, X1, X2, X2) deletecB_in_gaaa(X1, X2, X3, X4) -> U14_gaaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) deletecA_in_gaa(X1, .(X1, X2), X2) -> deletecA_out_gaa(X1, .(X1, X2), X2) deletecA_in_gaa(X1, .(X2, X3), X4) -> U13_gaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U13_gaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecA_out_gaa(X1, .(X2, X3), X4) U14_gaaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecB_out_gaaa(X1, X2, X3, X4) permcC_in_ag([], []) -> permcC_out_ag([], []) permcC_in_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U15_ag(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U15_ag(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U16_ag(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U16_ag(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> permcC_out_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] deletecB_in_gaaa(x1, x2, x3, x4) = deletecB_in_gaaa(x1) deletecB_out_gaaa(x1, x2, x3, x4) = deletecB_out_gaaa(x1) U14_gaaa(x1, x2, x3, x4, x5) = U14_gaaa(x1, x5) deletecA_in_gaa(x1, x2, x3) = deletecA_in_gaa(x1) deletecA_out_gaa(x1, x2, x3) = deletecA_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x5) permcC_in_ag(x1, x2) = permcC_in_ag(x2) permcC_out_ag(x1, x2) = permcC_out_ag(x2) U15_ag(x1, x2, x3, x4, x5) = U15_ag(x3, x4, x5) U16_ag(x1, x2, x3, x4, x5) = U16_ag(x3, x4, x5) DELETEA_IN_GAA(x1, x2, x3) = DELETEA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (83) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (84) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETEA_IN_GAA(X1, .(X2, X3), X4) -> DELETEA_IN_GAA(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) DELETEA_IN_GAA(x1, x2, x3) = DELETEA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (85) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: DELETEA_IN_GAA(X1) -> DELETEA_IN_GAA(X1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (87) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = DELETEA_IN_GAA(X1) evaluates to t =DELETEA_IN_GAA(X1) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from DELETEA_IN_GAA(X1) to DELETEA_IN_GAA(X1). ---------------------------------------- (88) NO ---------------------------------------- (89) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U4_AG(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U4_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> PERMC_IN_AG(X5, X4) The TRS R consists of the following rules: deletecB_in_gaaa(X1, X1, X2, X2) -> deletecB_out_gaaa(X1, X1, X2, X2) deletecB_in_gaaa(X1, X2, X3, X4) -> U14_gaaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) deletecA_in_gaa(X1, .(X1, X2), X2) -> deletecA_out_gaa(X1, .(X1, X2), X2) deletecA_in_gaa(X1, .(X2, X3), X4) -> U13_gaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U13_gaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecA_out_gaa(X1, .(X2, X3), X4) U14_gaaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecB_out_gaaa(X1, X2, X3, X4) permcC_in_ag([], []) -> permcC_out_ag([], []) permcC_in_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U15_ag(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U15_ag(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> U16_ag(X1, X2, X3, X4, permcC_in_ag(X5, X4)) U16_ag(X1, X2, X3, X4, permcC_out_ag(X5, X4)) -> permcC_out_ag(.(X1, .(X2, [])), .(X3, .(X4, []))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] deletecB_in_gaaa(x1, x2, x3, x4) = deletecB_in_gaaa(x1) deletecB_out_gaaa(x1, x2, x3, x4) = deletecB_out_gaaa(x1) U14_gaaa(x1, x2, x3, x4, x5) = U14_gaaa(x1, x5) deletecA_in_gaa(x1, x2, x3) = deletecA_in_gaa(x1) deletecA_out_gaa(x1, x2, x3) = deletecA_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x5) permcC_in_ag(x1, x2) = permcC_in_ag(x2) permcC_out_ag(x1, x2) = permcC_out_ag(x2) U15_ag(x1, x2, x3, x4, x5) = U15_ag(x3, x4, x5) U16_ag(x1, x2, x3, x4, x5) = U16_ag(x3, x4, x5) PERMC_IN_AG(x1, x2) = PERMC_IN_AG(x2) U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (90) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (91) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMC_IN_AG(.(X1, .(X2, [])), .(X3, .(X4, []))) -> U4_AG(X1, X2, X3, X4, deletecB_in_gaaa(X3, X1, X2, X5)) U4_AG(X1, X2, X3, X4, deletecB_out_gaaa(X3, X1, X2, X5)) -> PERMC_IN_AG(X5, X4) The TRS R consists of the following rules: deletecB_in_gaaa(X1, X1, X2, X2) -> deletecB_out_gaaa(X1, X1, X2, X2) deletecB_in_gaaa(X1, X2, X3, X4) -> U14_gaaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U14_gaaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecB_out_gaaa(X1, X2, X3, X4) deletecA_in_gaa(X1, .(X1, X2), X2) -> deletecA_out_gaa(X1, .(X1, X2), X2) deletecA_in_gaa(X1, .(X2, X3), X4) -> U13_gaa(X1, X2, X3, X4, deletecA_in_gaa(X1, X3, X4)) U13_gaa(X1, X2, X3, X4, deletecA_out_gaa(X1, X3, X4)) -> deletecA_out_gaa(X1, .(X2, X3), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] deletecB_in_gaaa(x1, x2, x3, x4) = deletecB_in_gaaa(x1) deletecB_out_gaaa(x1, x2, x3, x4) = deletecB_out_gaaa(x1) U14_gaaa(x1, x2, x3, x4, x5) = U14_gaaa(x1, x5) deletecA_in_gaa(x1, x2, x3) = deletecA_in_gaa(x1) deletecA_out_gaa(x1, x2, x3) = deletecA_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x5) PERMC_IN_AG(x1, x2) = PERMC_IN_AG(x2) U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (92) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(slowsort X Y)", "(',' (perm X Y) (sorted Y))" ], [ "(sorted ([]))", null ], [ "(sorted (. X ([])))", null ], [ "(sorted (. X (. Y Z)))", "(',' (le X Y) (sorted (. Y Z)))" ], [ "(perm ([]) ([]))", null ], [ "(perm (. X (. Y ([]))) (. U (. V ([]))))", "(',' (delete U (. X Y) Z) (perm Z V))" ], [ "(delete X (. X Y) Y)", null ], [ "(delete X (. Y Z) W)", "(delete X Z W)" ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (0) (s X))", null ], [ "(le (0) (0))", null ] ] }, "graph": { "nodes": { "type": "Nodes", "154": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "155": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T29 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } }, "199": { "goal": [{ "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "278": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "433": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T98 T99) (sorted (. T99 T100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99", "T100" ], "free": [], "exprvars": [] } }, "434": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "437": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "119": { "goal": [{ "clause": 4, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "438": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T99 T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T100" ], "free": [], "exprvars": [] } }, "439": { "goal": [ { "clause": 8, "scope": 6, "term": "(le T98 T99)" }, { "clause": 9, "scope": 6, "term": "(le T98 T99)" }, { "clause": 10, "scope": 6, "term": "(le T98 T99)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": 5, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "440": { "goal": [{ "clause": 8, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "441": { "goal": [ { "clause": 9, "scope": 6, "term": "(le T98 T99)" }, { "clause": 10, "scope": 6, "term": "(le T98 T99)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "445": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "447": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "129": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T10 T9) (sorted T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "250": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "130": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (delete T21 (. T23 T24) X20) (perm X20 T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": ["X20"], "exprvars": [] } }, "174": { "goal": [ { "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }, { "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "372": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "131": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "373": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "374": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "375": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "496": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "255": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "497": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "256": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "377": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T79 T82 X86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T79"], "free": ["X86"], "exprvars": [] } }, "378": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "338": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "416": { "goal": [ { "clause": 1, "scope": 5, "term": "(sorted T9)" }, { "clause": 2, "scope": 5, "term": "(sorted T9)" }, { "clause": 3, "scope": 5, "term": "(sorted T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "417": { "goal": [{ "clause": 1, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "418": { "goal": [ { "clause": 2, "scope": 5, "term": "(sorted T9)" }, { "clause": 3, "scope": 5, "term": "(sorted T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "419": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "78": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "460": { "goal": [{ "clause": 9, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "461": { "goal": [{ "clause": 10, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "420": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "464": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "421": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "465": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "466": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "104": { "goal": [ { "clause": 4, "scope": 2, "term": "(perm T10 T9)" }, { "clause": 5, "scope": 2, "term": "(perm T10 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "423": { "goal": [{ "clause": 2, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "467": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "424": { "goal": [{ "clause": 3, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "427": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "82": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "428": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "429": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "309": { "goal": [ { "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }, { "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 64, "label": "ONLY EVAL with clause\nslowsort(X5, X6) :- ','(perm(X5, X6), sorted(X6)).\nand substitutionT1 -> T10,\nX5 -> T10,\nT2 -> T9,\nX6 -> T9,\nT8 -> T10" }, { "from": 64, "to": 78, "label": "SPLIT 1" }, { "from": 64, "to": 82, "label": "SPLIT 2\nnew knowledge:\nT9 is ground" }, { "from": 78, "to": 104, "label": "CASE" }, { "from": 82, "to": 416, "label": "CASE" }, { "from": 104, "to": 119, "label": "PARALLEL" }, { "from": 104, "to": 121, "label": "PARALLEL" }, { "from": 119, "to": 127, "label": "EVAL with clause\nperm([], []).\nand substitutionT10 -> [],\nT9 -> []" }, { "from": 119, "to": 128, "label": "EVAL-BACKTRACK" }, { "from": 121, "to": 130, "label": "EVAL with clause\nperm(.(X16, .(X17, [])), .(X18, .(X19, []))) :- ','(delete(X18, .(X16, X17), X20), perm(X20, X19)).\nand substitutionX16 -> T23,\nX17 -> T24,\nT10 -> .(T23, .(T24, [])),\nX18 -> T21,\nX19 -> T22,\nT9 -> .(T21, .(T22, [])),\nT19 -> T23,\nT20 -> T24" }, { "from": 121, "to": 131, "label": "EVAL-BACKTRACK" }, { "from": 127, "to": 129, "label": "SUCCESS" }, { "from": 130, "to": 154, "label": "SPLIT 1" }, { "from": 130, "to": 155, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nreplacements:X20 -> T29" }, { "from": 154, "to": 174, "label": "CASE" }, { "from": 155, "to": 78, "label": "INSTANCE with matching:\nT10 -> T29\nT9 -> T22" }, { "from": 174, "to": 199, "label": "PARALLEL" }, { "from": 174, "to": 203, "label": "PARALLEL" }, { "from": 199, "to": 250, "label": "EVAL with clause\ndelete(X37, .(X37, X38), X38).\nand substitutionT21 -> T42,\nX37 -> T42,\nT23 -> T42,\nT24 -> T43,\nX38 -> T43,\nX20 -> T43" }, { "from": 199, "to": 255, "label": "EVAL-BACKTRACK" }, { "from": 203, "to": 278, "label": "ONLY EVAL with clause\ndelete(X53, .(X54, X55), X56) :- delete(X53, X55, X56).\nand substitutionT21 -> T55,\nX53 -> T55,\nT23 -> T56,\nX54 -> T56,\nT24 -> T58,\nX55 -> T58,\nX20 -> X57,\nX56 -> X57,\nT57 -> T58" }, { "from": 250, "to": 256, "label": "SUCCESS" }, { "from": 278, "to": 309, "label": "CASE" }, { "from": 309, "to": 338, "label": "PARALLEL" }, { "from": 309, "to": 372, "label": "PARALLEL" }, { "from": 338, "to": 373, "label": "EVAL with clause\ndelete(X70, .(X70, X71), X71).\nand substitutionT55 -> T71,\nX70 -> T71,\nX71 -> T72,\nT58 -> .(T71, T72),\nX57 -> T72" }, { "from": 338, "to": 374, "label": "EVAL-BACKTRACK" }, { "from": 372, "to": 377, "label": "EVAL with clause\ndelete(X82, .(X83, X84), X85) :- delete(X82, X84, X85).\nand substitutionT55 -> T79,\nX82 -> T79,\nX83 -> T80,\nX84 -> T82,\nT58 -> .(T80, T82),\nX57 -> X86,\nX85 -> X86,\nT81 -> T82" }, { "from": 372, "to": 378, "label": "EVAL-BACKTRACK" }, { "from": 373, "to": 375, "label": "SUCCESS" }, { "from": 377, "to": 278, "label": "INSTANCE with matching:\nT55 -> T79\nT58 -> T82\nX57 -> X86" }, { "from": 416, "to": 417, "label": "PARALLEL" }, { "from": 416, "to": 418, "label": "PARALLEL" }, { "from": 417, "to": 419, "label": "EVAL with clause\nsorted([]).\nand substitutionT9 -> []" }, { "from": 417, "to": 420, "label": "EVAL-BACKTRACK" }, { "from": 418, "to": 423, "label": "PARALLEL" }, { "from": 418, "to": 424, "label": "PARALLEL" }, { "from": 419, "to": 421, "label": "SUCCESS" }, { "from": 423, "to": 427, "label": "EVAL with clause\nsorted(.(X95, [])).\nand substitutionX95 -> T91,\nT9 -> .(T91, [])" }, { "from": 423, "to": 428, "label": "EVAL-BACKTRACK" }, { "from": 424, "to": 433, "label": "EVAL with clause\nsorted(.(X102, .(X103, X104))) :- ','(le(X102, X103), sorted(.(X103, X104))).\nand substitutionX102 -> T98,\nX103 -> T99,\nX104 -> T100,\nT9 -> .(T98, .(T99, T100))" }, { "from": 424, "to": 434, "label": "EVAL-BACKTRACK" }, { "from": 427, "to": 429, "label": "SUCCESS" }, { "from": 433, "to": 437, "label": "SPLIT 1" }, { "from": 433, "to": 438, "label": "SPLIT 2\nnew knowledge:\nT98 is ground\nT99 is ground" }, { "from": 437, "to": 439, "label": "CASE" }, { "from": 438, "to": 82, "label": "INSTANCE with matching:\nT9 -> .(T99, T100)" }, { "from": 439, "to": 440, "label": "PARALLEL" }, { "from": 439, "to": 441, "label": "PARALLEL" }, { "from": 440, "to": 445, "label": "EVAL with clause\nle(s(X117), s(X118)) :- le(X117, X118).\nand substitutionX117 -> T113,\nT98 -> s(T113),\nX118 -> T114,\nT99 -> s(T114)" }, { "from": 440, "to": 447, "label": "EVAL-BACKTRACK" }, { "from": 441, "to": 460, "label": "PARALLEL" }, { "from": 441, "to": 461, "label": "PARALLEL" }, { "from": 445, "to": 437, "label": "INSTANCE with matching:\nT98 -> T113\nT99 -> T114" }, { "from": 460, "to": 464, "label": "EVAL with clause\nle(0, s(X125)).\nand substitutionT98 -> 0,\nX125 -> T121,\nT99 -> s(T121)" }, { "from": 460, "to": 465, "label": "EVAL-BACKTRACK" }, { "from": 461, "to": 467, "label": "EVAL with clause\nle(0, 0).\nand substitutionT98 -> 0,\nT99 -> 0" }, { "from": 461, "to": 496, "label": "EVAL-BACKTRACK" }, { "from": 464, "to": 466, "label": "SUCCESS" }, { "from": 467, "to": 497, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (93) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 Q is empty. ---------------------------------------- (94) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (95) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T9) -> U1^1(f64_in(T9), T9) F1_IN(T9) -> F64_IN(T9) F78_IN(.(T21, .(T22, []))) -> U2^1(f130_in(T21, T22), .(T21, .(T22, []))) F78_IN(.(T21, .(T22, []))) -> F130_IN(T21, T22) F278_IN(T79) -> U3^1(f278_in(T79), T79) F278_IN(T79) -> F278_IN(T79) F82_IN(.(T98, .(T99, T100))) -> U4^1(f433_in(T98, T99, T100), .(T98, .(T99, T100))) F82_IN(.(T98, .(T99, T100))) -> F433_IN(T98, T99, T100) F437_IN(s(T113), s(T114)) -> U5^1(f437_in(T113, T114), s(T113), s(T114)) F437_IN(s(T113), s(T114)) -> F437_IN(T113, T114) F154_IN(T55) -> U6^1(f278_in(T55), T55) F154_IN(T55) -> F278_IN(T55) F64_IN(T9) -> U7^1(f78_in(T9), T9) F64_IN(T9) -> F78_IN(T9) U7^1(f78_out1, T9) -> U8^1(f82_in(T9), T9) U7^1(f78_out1, T9) -> F82_IN(T9) F130_IN(T21, T22) -> U9^1(f154_in(T21), T21, T22) F130_IN(T21, T22) -> F154_IN(T21) U9^1(f154_out1, T21, T22) -> U10^1(f78_in(T22), T21, T22) U9^1(f154_out1, T21, T22) -> F78_IN(T22) F433_IN(T98, T99, T100) -> U11^1(f437_in(T98, T99), T98, T99, T100) F433_IN(T98, T99, T100) -> F437_IN(T98, T99) U11^1(f437_out1, T98, T99, T100) -> U12^1(f82_in(.(T99, T100)), T98, T99, T100) U11^1(f437_out1, T98, T99, T100) -> F82_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (96) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 16 less nodes. ---------------------------------------- (97) Complex Obligation (AND) ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: F437_IN(s(T113), s(T114)) -> F437_IN(T113, T114) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (99) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: F437_IN(s(T113), s(T114)) -> F437_IN(T113, T114) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (101) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: F437_IN(s(T113), s(T114)) -> F437_IN(T113, T114) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (103) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: F437_IN(s(T113), s(T114)) -> F437_IN(T113, T114) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (105) 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: *F437_IN(s(T113), s(T114)) -> F437_IN(T113, T114) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (106) YES ---------------------------------------- (107) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(.(T98, .(T99, T100))) -> F433_IN(T98, T99, T100) F433_IN(T98, T99, T100) -> U11^1(f437_in(T98, T99), T98, T99, T100) U11^1(f437_out1, T98, T99, T100) -> F82_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (108) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (109) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(.(T98, .(T99, T100))) -> F433_IN(T98, T99, T100) F433_IN(T98, T99, T100) -> U11^1(f437_in(T98, T99), T98, T99, T100) U11^1(f437_out1, T98, T99, T100) -> F82_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (110) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (111) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(.(T98, .(T99, T100))) -> F433_IN(T98, T99, T100) F433_IN(T98, T99, T100) -> U11^1(f437_in(T98, T99), T98, T99, T100) U11^1(f437_out1, T98, T99, T100) -> F82_IN(.(T99, T100)) The TRS R consists of the following rules: f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 U5(f437_out1, s(T113), s(T114)) -> f437_out1 The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (112) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) ---------------------------------------- (113) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(.(T98, .(T99, T100))) -> F433_IN(T98, T99, T100) F433_IN(T98, T99, T100) -> U11^1(f437_in(T98, T99), T98, T99, T100) U11^1(f437_out1, T98, T99, T100) -> F82_IN(.(T99, T100)) The TRS R consists of the following rules: f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 U5(f437_out1, s(T113), s(T114)) -> f437_out1 The set Q consists of the following terms: f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (114) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F82_IN(.(T98, .(T99, T100))) -> F433_IN(T98, T99, T100) F433_IN(T98, T99, T100) -> U11^1(f437_in(T98, T99), T98, T99, T100) U11^1(f437_out1, T98, T99, T100) -> F82_IN(.(T99, T100)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. F82_IN(x1) = x1 .(x1, x2) = .(x2) F433_IN(x1, x2, x3) = F433_IN(x3) U11^1(x1, x2, x3, x4) = U11^1(x4) Knuth-Bendix order [KBO] with precedence:trivial and weight map: dummyConstant=1 ._1=5 U11^1_1=6 F433_IN_1=8 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (115) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 U5(f437_out1, s(T113), s(T114)) -> f437_out1 The set Q consists of the following terms: f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (116) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (117) YES ---------------------------------------- (118) Obligation: Q DP problem: The TRS P consists of the following rules: F278_IN(T79) -> F278_IN(T79) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (119) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (120) Obligation: Q DP problem: The TRS P consists of the following rules: F278_IN(T79) -> F278_IN(T79) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (121) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (122) Obligation: Q DP problem: The TRS P consists of the following rules: F278_IN(T79) -> F278_IN(T79) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (123) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: F278_IN(T79) -> F278_IN(T79) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (125) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = F278_IN(T79) evaluates to t =F278_IN(T79) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from F278_IN(T79) to F278_IN(T79). ---------------------------------------- (126) NO ---------------------------------------- (127) Obligation: Q DP problem: The TRS P consists of the following rules: F78_IN(.(T21, .(T22, []))) -> F130_IN(T21, T22) F130_IN(T21, T22) -> U9^1(f154_in(T21), T21, T22) U9^1(f154_out1, T21, T22) -> F78_IN(T22) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (128) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (129) Obligation: Q DP problem: The TRS P consists of the following rules: F78_IN(.(T21, .(T22, []))) -> F130_IN(T21, T22) F130_IN(T21, T22) -> U9^1(f154_in(T21), T21, T22) U9^1(f154_out1, T21, T22) -> F78_IN(T22) The TRS R consists of the following rules: f1_in(T9) -> U1(f64_in(T9), T9) U1(f64_out1, T9) -> f1_out1 f78_in([]) -> f78_out1 f78_in(.(T21, .(T22, []))) -> U2(f130_in(T21, T22), .(T21, .(T22, []))) U2(f130_out1, .(T21, .(T22, []))) -> f78_out1 f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U3(f278_out1, T79) -> f278_out1 f82_in([]) -> f82_out1 f82_in(.(T91, [])) -> f82_out1 f82_in(.(T98, .(T99, T100))) -> U4(f433_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f433_out1, .(T98, .(T99, T100))) -> f82_out1 f437_in(s(T113), s(T114)) -> U5(f437_in(T113, T114), s(T113), s(T114)) U5(f437_out1, s(T113), s(T114)) -> f437_out1 f437_in(0, s(T121)) -> f437_out1 f437_in(0, 0) -> f437_out1 f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) U6(f278_out1, T55) -> f154_out1 f64_in(T9) -> U7(f78_in(T9), T9) U7(f78_out1, T9) -> U8(f82_in(T9), T9) U8(f82_out1, T9) -> f64_out1 f130_in(T21, T22) -> U9(f154_in(T21), T21, T22) U9(f154_out1, T21, T22) -> U10(f78_in(T22), T21, T22) U10(f78_out1, T21, T22) -> f130_out1 f433_in(T98, T99, T100) -> U11(f437_in(T98, T99), T98, T99, T100) U11(f437_out1, T98, T99, T100) -> U12(f82_in(.(T99, T100)), T98, T99, T100) U12(f82_out1, T98, T99, T100) -> f433_out1 The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (130) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (131) Obligation: Q DP problem: The TRS P consists of the following rules: F78_IN(.(T21, .(T22, []))) -> F130_IN(T21, T22) F130_IN(T21, T22) -> U9^1(f154_in(T21), T21, T22) U9^1(f154_out1, T21, T22) -> F78_IN(T22) The TRS R consists of the following rules: f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U6(f278_out1, T55) -> f154_out1 U3(f278_out1, T79) -> f278_out1 The set Q consists of the following terms: f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f278_in(x0) U3(f278_out1, x0) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f154_in(x0) U6(f278_out1, x0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (132) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(x0) U1(f64_out1, x0) f78_in([]) f78_in(.(x0, .(x1, []))) U2(f130_out1, .(x0, .(x1, []))) f82_in([]) f82_in(.(x0, [])) f82_in(.(x0, .(x1, x2))) U4(f433_out1, .(x0, .(x1, x2))) f437_in(s(x0), s(x1)) U5(f437_out1, s(x0), s(x1)) f437_in(0, s(x0)) f437_in(0, 0) f64_in(x0) U7(f78_out1, x0) U8(f82_out1, x0) f130_in(x0, x1) U9(f154_out1, x0, x1) U10(f78_out1, x0, x1) f433_in(x0, x1, x2) U11(f437_out1, x0, x1, x2) U12(f82_out1, x0, x1, x2) ---------------------------------------- (133) Obligation: Q DP problem: The TRS P consists of the following rules: F78_IN(.(T21, .(T22, []))) -> F130_IN(T21, T22) F130_IN(T21, T22) -> U9^1(f154_in(T21), T21, T22) U9^1(f154_out1, T21, T22) -> F78_IN(T22) The TRS R consists of the following rules: f154_in(T42) -> f154_out1 f154_in(T55) -> U6(f278_in(T55), T55) f278_in(T71) -> f278_out1 f278_in(T79) -> U3(f278_in(T79), T79) U6(f278_out1, T55) -> f154_out1 U3(f278_out1, T79) -> f278_out1 The set Q consists of the following terms: f278_in(x0) U3(f278_out1, x0) f154_in(x0) U6(f278_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (134) 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: *F130_IN(T21, T22) -> U9^1(f154_in(T21), T21, T22) The graph contains the following edges 1 >= 2, 2 >= 3 *U9^1(f154_out1, T21, T22) -> F78_IN(T22) The graph contains the following edges 3 >= 1 *F78_IN(.(T21, .(T22, []))) -> F130_IN(T21, T22) The graph contains the following edges 1 > 1, 1 > 2 ---------------------------------------- (135) YES ---------------------------------------- (136) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(slowsort X Y)", "(',' (perm X Y) (sorted Y))" ], [ "(sorted ([]))", null ], [ "(sorted (. X ([])))", null ], [ "(sorted (. X (. Y Z)))", "(',' (le X Y) (sorted (. Y Z)))" ], [ "(perm ([]) ([]))", null ], [ "(perm (. X (. Y ([]))) (. U (. V ([]))))", "(',' (delete U (. X Y) Z) (perm Z V))" ], [ "(delete X (. X Y) Y)", null ], [ "(delete X (. Y Z) W)", "(delete X Z W)" ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (0) (s X))", null ], [ "(le (0) (0))", null ] ] }, "graph": { "nodes": { "270": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "274": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "275": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T29 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } }, "276": { "goal": [ { "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }, { "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "430": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "277": { "goal": [{ "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "431": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "475": { "goal": [ { "clause": 1, "scope": 5, "term": "(sorted T9)" }, { "clause": 2, "scope": 5, "term": "(sorted T9)" }, { "clause": 3, "scope": 5, "term": "(sorted T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "432": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "476": { "goal": [{ "clause": 1, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "279": { "goal": [{ "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "477": { "goal": [ { "clause": 2, "scope": 5, "term": "(sorted T9)" }, { "clause": 3, "scope": 5, "term": "(sorted T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "510": { "goal": [ { "clause": 8, "scope": 6, "term": "(le T98 T99)" }, { "clause": 9, "scope": 6, "term": "(le T98 T99)" }, { "clause": 10, "scope": 6, "term": "(le T98 T99)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "478": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "435": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T79 T82 X86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T79"], "free": ["X86"], "exprvars": [] } }, "479": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "436": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "513": { "goal": [{ "clause": 8, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "514": { "goal": [ { "clause": 9, "scope": 6, "term": "(le T98 T99)" }, { "clause": 10, "scope": 6, "term": "(le T98 T99)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "515": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "516": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "517": { "goal": [{ "clause": 9, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T10 T9) (sorted T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "518": { "goal": [{ "clause": 10, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "52": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "519": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "56": { "goal": [ { "clause": 4, "scope": 2, "term": "(perm T10 T9)" }, { "clause": 5, "scope": 2, "term": "(perm T10 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "57": { "goal": [{ "clause": 4, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "58": { "goal": [{ "clause": 5, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "59": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "480": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "481": { "goal": [{ "clause": 2, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "482": { "goal": [{ "clause": 3, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "484": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "485": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "486": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "520": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "521": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "489": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T98 T99) (sorted (. T99 T100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99", "T100" ], "free": [], "exprvars": [] } }, "522": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "523": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 0, "scope": 1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "524": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "491": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "494": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "495": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T99 T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T100" ], "free": [], "exprvars": [] } }, "412": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "413": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "414": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "415": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "266": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "422": { "goal": [ { "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }, { "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (delete T21 (. T23 T24) X20) (perm X20 T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": ["X20"], "exprvars": [] } }, "425": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "426": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 7, "label": "CASE" }, { "from": 7, "to": 51, "label": "ONLY EVAL with clause\nslowsort(X5, X6) :- ','(perm(X5, X6), sorted(X6)).\nand substitutionT1 -> T10,\nX5 -> T10,\nT2 -> T9,\nX6 -> T9,\nT8 -> T10" }, { "from": 51, "to": 52, "label": "SPLIT 1" }, { "from": 51, "to": 53, "label": "SPLIT 2\nnew knowledge:\nT9 is ground" }, { "from": 52, "to": 56, "label": "CASE" }, { "from": 53, "to": 475, "label": "CASE" }, { "from": 56, "to": 57, "label": "PARALLEL" }, { "from": 56, "to": 58, "label": "PARALLEL" }, { "from": 57, "to": 59, "label": "EVAL with clause\nperm([], []).\nand substitutionT10 -> [],\nT9 -> []" }, { "from": 57, "to": 60, "label": "EVAL-BACKTRACK" }, { "from": 58, "to": 269, "label": "EVAL with clause\nperm(.(X16, .(X17, [])), .(X18, .(X19, []))) :- ','(delete(X18, .(X16, X17), X20), perm(X20, X19)).\nand substitutionX16 -> T23,\nX17 -> T24,\nT10 -> .(T23, .(T24, [])),\nX18 -> T21,\nX19 -> T22,\nT9 -> .(T21, .(T22, [])),\nT19 -> T23,\nT20 -> T24" }, { "from": 58, "to": 270, "label": "EVAL-BACKTRACK" }, { "from": 59, "to": 266, "label": "SUCCESS" }, { "from": 269, "to": 274, "label": "SPLIT 1" }, { "from": 269, "to": 275, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nreplacements:X20 -> T29" }, { "from": 274, "to": 276, "label": "CASE" }, { "from": 275, "to": 52, "label": "INSTANCE with matching:\nT10 -> T29\nT9 -> T22" }, { "from": 276, "to": 277, "label": "PARALLEL" }, { "from": 276, "to": 279, "label": "PARALLEL" }, { "from": 277, "to": 412, "label": "EVAL with clause\ndelete(X37, .(X37, X38), X38).\nand substitutionT21 -> T42,\nX37 -> T42,\nT23 -> T42,\nT24 -> T43,\nX38 -> T43,\nX20 -> T43" }, { "from": 277, "to": 413, "label": "EVAL-BACKTRACK" }, { "from": 279, "to": 415, "label": "ONLY EVAL with clause\ndelete(X53, .(X54, X55), X56) :- delete(X53, X55, X56).\nand substitutionT21 -> T55,\nX53 -> T55,\nT23 -> T56,\nX54 -> T56,\nT24 -> T58,\nX55 -> T58,\nX20 -> X57,\nX56 -> X57,\nT57 -> T58" }, { "from": 412, "to": 414, "label": "SUCCESS" }, { "from": 415, "to": 422, "label": "CASE" }, { "from": 422, "to": 425, "label": "PARALLEL" }, { "from": 422, "to": 426, "label": "PARALLEL" }, { "from": 425, "to": 430, "label": "EVAL with clause\ndelete(X70, .(X70, X71), X71).\nand substitutionT55 -> T71,\nX70 -> T71,\nX71 -> T72,\nT58 -> .(T71, T72),\nX57 -> T72" }, { "from": 425, "to": 431, "label": "EVAL-BACKTRACK" }, { "from": 426, "to": 435, "label": "EVAL with clause\ndelete(X82, .(X83, X84), X85) :- delete(X82, X84, X85).\nand substitutionT55 -> T79,\nX82 -> T79,\nX83 -> T80,\nX84 -> T82,\nT58 -> .(T80, T82),\nX57 -> X86,\nX85 -> X86,\nT81 -> T82" }, { "from": 426, "to": 436, "label": "EVAL-BACKTRACK" }, { "from": 430, "to": 432, "label": "SUCCESS" }, { "from": 435, "to": 415, "label": "INSTANCE with matching:\nT55 -> T79\nT58 -> T82\nX57 -> X86" }, { "from": 475, "to": 476, "label": "PARALLEL" }, { "from": 475, "to": 477, "label": "PARALLEL" }, { "from": 476, "to": 478, "label": "EVAL with clause\nsorted([]).\nand substitutionT9 -> []" }, { "from": 476, "to": 479, "label": "EVAL-BACKTRACK" }, { "from": 477, "to": 481, "label": "PARALLEL" }, { "from": 477, "to": 482, "label": "PARALLEL" }, { "from": 478, "to": 480, "label": "SUCCESS" }, { "from": 481, "to": 484, "label": "EVAL with clause\nsorted(.(X95, [])).\nand substitutionX95 -> T91,\nT9 -> .(T91, [])" }, { "from": 481, "to": 485, "label": "EVAL-BACKTRACK" }, { "from": 482, "to": 489, "label": "EVAL with clause\nsorted(.(X102, .(X103, X104))) :- ','(le(X102, X103), sorted(.(X103, X104))).\nand substitutionX102 -> T98,\nX103 -> T99,\nX104 -> T100,\nT9 -> .(T98, .(T99, T100))" }, { "from": 482, "to": 491, "label": "EVAL-BACKTRACK" }, { "from": 484, "to": 486, "label": "SUCCESS" }, { "from": 489, "to": 494, "label": "SPLIT 1" }, { "from": 489, "to": 495, "label": "SPLIT 2\nnew knowledge:\nT98 is ground\nT99 is ground" }, { "from": 494, "to": 510, "label": "CASE" }, { "from": 495, "to": 53, "label": "INSTANCE with matching:\nT9 -> .(T99, T100)" }, { "from": 510, "to": 513, "label": "PARALLEL" }, { "from": 510, "to": 514, "label": "PARALLEL" }, { "from": 513, "to": 515, "label": "EVAL with clause\nle(s(X117), s(X118)) :- le(X117, X118).\nand substitutionX117 -> T113,\nT98 -> s(T113),\nX118 -> T114,\nT99 -> s(T114)" }, { "from": 513, "to": 516, "label": "EVAL-BACKTRACK" }, { "from": 514, "to": 517, "label": "PARALLEL" }, { "from": 514, "to": 518, "label": "PARALLEL" }, { "from": 515, "to": 494, "label": "INSTANCE with matching:\nT98 -> T113\nT99 -> T114" }, { "from": 517, "to": 519, "label": "EVAL with clause\nle(0, s(X125)).\nand substitutionT98 -> 0,\nX125 -> T121,\nT99 -> s(T121)" }, { "from": 517, "to": 520, "label": "EVAL-BACKTRACK" }, { "from": 518, "to": 522, "label": "EVAL with clause\nle(0, 0).\nand substitutionT98 -> 0,\nT99 -> 0" }, { "from": 518, "to": 523, "label": "EVAL-BACKTRACK" }, { "from": 519, "to": 521, "label": "SUCCESS" }, { "from": 522, "to": 524, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (137) Complex Obligation (AND) ---------------------------------------- (138) Obligation: Rules: f513_in(T98, T99) -> f516_in :|: TRUE f515_out(T113, T114) -> f513_out(s(T113), s(T114)) :|: TRUE f516_out -> f513_out(x, x1) :|: TRUE f513_in(s(x2), s(x3)) -> f515_in(x2, x3) :|: TRUE f494_out(x4, x5) -> f515_out(x4, x5) :|: TRUE f515_in(x6, x7) -> f494_in(x6, x7) :|: TRUE f510_in(x8, x9) -> f514_in(x8, x9) :|: TRUE f514_out(x10, x11) -> f510_out(x10, x11) :|: TRUE f510_in(x12, x13) -> f513_in(x12, x13) :|: TRUE f513_out(x14, x15) -> f510_out(x14, x15) :|: TRUE f510_out(x16, x17) -> f494_out(x16, x17) :|: TRUE f494_in(x18, x19) -> f510_in(x18, x19) :|: TRUE f3_in(T2) -> f7_in(T2) :|: TRUE f7_out(x20) -> f3_out(x20) :|: TRUE f51_out(T9) -> f7_out(T9) :|: TRUE f7_in(x21) -> f51_in(x21) :|: TRUE f52_out(x22) -> f53_in(x22) :|: TRUE f53_out(x23) -> f51_out(x23) :|: TRUE f51_in(x24) -> f52_in(x24) :|: TRUE f53_in(x25) -> f475_in(x25) :|: TRUE f475_out(x26) -> f53_out(x26) :|: TRUE f475_in(x27) -> f477_in(x27) :|: TRUE f475_in(x28) -> f476_in(x28) :|: TRUE f476_out(x29) -> f475_out(x29) :|: TRUE f477_out(x30) -> f475_out(x30) :|: TRUE f477_in(x31) -> f481_in(x31) :|: TRUE f477_in(x32) -> f482_in(x32) :|: TRUE f481_out(x33) -> f477_out(x33) :|: TRUE f482_out(x34) -> f477_out(x34) :|: TRUE f489_out(x35, x36, x37) -> f482_out(.(x35, .(x36, x37))) :|: TRUE f482_in(.(x38, .(x39, x40))) -> f489_in(x38, x39, x40) :|: TRUE f491_out -> f482_out(x41) :|: TRUE f482_in(x42) -> f491_in :|: TRUE f495_out(x43, x44) -> f489_out(x45, x43, x44) :|: TRUE f494_out(x46, x47) -> f495_in(x47, x48) :|: TRUE f489_in(x49, x50, x51) -> f494_in(x49, x50) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (139) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (140) TRUE ---------------------------------------- (141) Obligation: Rules: f422_in(T55) -> f425_in(T55) :|: TRUE f426_out(x) -> f422_out(x) :|: TRUE f425_out(x1) -> f422_out(x1) :|: TRUE f422_in(x2) -> f426_in(x2) :|: TRUE f426_in(x3) -> f436_in :|: TRUE f426_in(T79) -> f435_in(T79) :|: TRUE f435_out(x4) -> f426_out(x4) :|: TRUE f436_out -> f426_out(x5) :|: TRUE f415_out(x6) -> f435_out(x6) :|: TRUE f435_in(x7) -> f415_in(x7) :|: TRUE f415_in(x8) -> f422_in(x8) :|: TRUE f422_out(x9) -> f415_out(x9) :|: TRUE f3_in(T2) -> f7_in(T2) :|: TRUE f7_out(x10) -> f3_out(x10) :|: TRUE f51_out(T9) -> f7_out(T9) :|: TRUE f7_in(x11) -> f51_in(x11) :|: TRUE f52_out(x12) -> f53_in(x12) :|: TRUE f53_out(x13) -> f51_out(x13) :|: TRUE f51_in(x14) -> f52_in(x14) :|: TRUE f52_in(x15) -> f56_in(x15) :|: TRUE f56_out(x16) -> f52_out(x16) :|: TRUE f56_in(x17) -> f58_in(x17) :|: TRUE f56_in(x18) -> f57_in(x18) :|: TRUE f58_out(x19) -> f56_out(x19) :|: TRUE f57_out(x20) -> f56_out(x20) :|: TRUE f58_in(x21) -> f270_in :|: TRUE f269_out(T21, T22) -> f58_out(.(T21, .(T22, []))) :|: TRUE f270_out -> f58_out(x22) :|: TRUE f58_in(.(x23, .(x24, []))) -> f269_in(x23, x24) :|: TRUE f274_out(x25) -> f275_in(x26) :|: TRUE f275_out(x27) -> f269_out(x28, x27) :|: TRUE f269_in(x29, x30) -> f274_in(x29) :|: TRUE f274_in(x31) -> f276_in(x31) :|: TRUE f276_out(x32) -> f274_out(x32) :|: TRUE f277_out(x33) -> f276_out(x33) :|: TRUE f276_in(x34) -> f279_in(x34) :|: TRUE f276_in(x35) -> f277_in(x35) :|: TRUE f279_out(x36) -> f276_out(x36) :|: TRUE f279_in(x37) -> f415_in(x37) :|: TRUE f415_out(x38) -> f279_out(x38) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (142) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f422_in(x2) -> f426_in(x2) :|: TRUE f426_in(T79) -> f435_in(T79) :|: TRUE f435_in(x7) -> f415_in(x7) :|: TRUE f415_in(x8) -> f422_in(x8) :|: TRUE ---------------------------------------- (143) Obligation: Rules: f422_in(x2) -> f426_in(x2) :|: TRUE f426_in(T79) -> f435_in(T79) :|: TRUE f435_in(x7) -> f415_in(x7) :|: TRUE f415_in(x8) -> f422_in(x8) :|: TRUE ---------------------------------------- (144) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (145) Obligation: Rules: f422_in(x2:0) -> f422_in(x2:0) :|: TRUE ---------------------------------------- (146) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (147) Obligation: Rules: f422_in(x2:0) -> f422_in(x2:0) :|: TRUE ---------------------------------------- (148) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f422_in(x2:0) -> f422_in(x2:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (149) Obligation: Termination digraph: Nodes: (1) f422_in(x2:0) -> f422_in(x2:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (150) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f422_in(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (151) Obligation: Rules: f422_in(x2:0) -> f422_in(x2:0) :|: TRUE ---------------------------------------- (152) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, x2:0) -> f(1, x2:0) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1, -8) ---------------------------------------- (153) NO ---------------------------------------- (154) Obligation: Rules: f495_in(T99, T100) -> f53_in(.(T99, T100)) :|: TRUE f53_out(.(x, x1)) -> f495_out(x, x1) :|: TRUE f53_in(T9) -> f475_in(T9) :|: TRUE f475_out(x2) -> f53_out(x2) :|: TRUE f489_out(x3, x4, x5) -> f482_out(.(x3, .(x4, x5))) :|: TRUE f482_in(.(x6, .(x7, x8))) -> f489_in(x6, x7, x8) :|: TRUE f491_out -> f482_out(x9) :|: TRUE f482_in(x10) -> f491_in :|: TRUE f510_in(x11, x12) -> f514_in(x11, x12) :|: TRUE f514_out(x13, x14) -> f510_out(x13, x14) :|: TRUE f510_in(x15, x16) -> f513_in(x15, x16) :|: TRUE f513_out(x17, x18) -> f510_out(x17, x18) :|: TRUE f517_in(0, s(T121)) -> f519_in :|: TRUE f519_out -> f517_out(0, s(x19)) :|: TRUE f520_out -> f517_out(x20, x21) :|: TRUE f517_in(x22, x23) -> f520_in :|: TRUE f477_in(x24) -> f481_in(x24) :|: TRUE f477_in(x25) -> f482_in(x25) :|: TRUE f481_out(x26) -> f477_out(x26) :|: TRUE f482_out(x27) -> f477_out(x27) :|: TRUE f522_in -> f522_out :|: TRUE f495_out(x28, x29) -> f489_out(x30, x28, x29) :|: TRUE f494_out(x31, x32) -> f495_in(x32, x33) :|: TRUE f489_in(x34, x35, x36) -> f494_in(x34, x35) :|: TRUE f518_in(0, 0) -> f522_in :|: TRUE f523_out -> f518_out(x37, x38) :|: TRUE f522_out -> f518_out(0, 0) :|: TRUE f518_in(x39, x40) -> f523_in :|: TRUE f475_in(x41) -> f477_in(x41) :|: TRUE f475_in(x42) -> f476_in(x42) :|: TRUE f476_out(x43) -> f475_out(x43) :|: TRUE f477_out(x44) -> f475_out(x44) :|: TRUE f514_in(x45, x46) -> f518_in(x45, x46) :|: TRUE f514_in(x47, x48) -> f517_in(x47, x48) :|: TRUE f518_out(x49, x50) -> f514_out(x49, x50) :|: TRUE f517_out(x51, x52) -> f514_out(x51, x52) :|: TRUE f513_in(x53, x54) -> f516_in :|: TRUE f515_out(T113, T114) -> f513_out(s(T113), s(T114)) :|: TRUE f516_out -> f513_out(x55, x56) :|: TRUE f513_in(s(x57), s(x58)) -> f515_in(x57, x58) :|: TRUE f494_out(x59, x60) -> f515_out(x59, x60) :|: TRUE f515_in(x61, x62) -> f494_in(x61, x62) :|: TRUE f510_out(x63, x64) -> f494_out(x63, x64) :|: TRUE f494_in(x65, x66) -> f510_in(x65, x66) :|: TRUE f519_in -> f519_out :|: TRUE f3_in(T2) -> f7_in(T2) :|: TRUE f7_out(x67) -> f3_out(x67) :|: TRUE f51_out(x68) -> f7_out(x68) :|: TRUE f7_in(x69) -> f51_in(x69) :|: TRUE f52_out(x70) -> f53_in(x70) :|: TRUE f53_out(x71) -> f51_out(x71) :|: TRUE f51_in(x72) -> f52_in(x72) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (155) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (156) TRUE ---------------------------------------- (157) Obligation: Rules: f415_in(T55) -> f422_in(T55) :|: TRUE f422_out(x) -> f415_out(x) :|: TRUE f52_in(T9) -> f56_in(T9) :|: TRUE f56_out(x1) -> f52_out(x1) :|: TRUE f275_in(T22) -> f52_in(T22) :|: TRUE f52_out(x2) -> f275_out(x2) :|: TRUE f422_in(x3) -> f425_in(x3) :|: TRUE f426_out(x4) -> f422_out(x4) :|: TRUE f425_out(x5) -> f422_out(x5) :|: TRUE f422_in(x6) -> f426_in(x6) :|: TRUE f274_out(x7) -> f275_in(x8) :|: TRUE f275_out(x9) -> f269_out(x10, x9) :|: TRUE f269_in(x11, x12) -> f274_in(x11) :|: TRUE f279_in(x13) -> f415_in(x13) :|: TRUE f415_out(x14) -> f279_out(x14) :|: TRUE f426_in(x15) -> f436_in :|: TRUE f426_in(T79) -> f435_in(T79) :|: TRUE f435_out(x16) -> f426_out(x16) :|: TRUE f436_out -> f426_out(x17) :|: TRUE f56_in(x18) -> f58_in(x18) :|: TRUE f56_in(x19) -> f57_in(x19) :|: TRUE f58_out(x20) -> f56_out(x20) :|: TRUE f57_out(x21) -> f56_out(x21) :|: TRUE f415_out(x22) -> f435_out(x22) :|: TRUE f435_in(x23) -> f415_in(x23) :|: TRUE f425_in(T71) -> f430_in :|: TRUE f425_in(x24) -> f431_in :|: TRUE f431_out -> f425_out(x25) :|: TRUE f430_out -> f425_out(x26) :|: TRUE f277_in(T42) -> f412_in :|: TRUE f277_in(T21) -> f413_in :|: TRUE f413_out -> f277_out(x27) :|: TRUE f412_out -> f277_out(x28) :|: TRUE f277_out(x29) -> f276_out(x29) :|: TRUE f276_in(x30) -> f279_in(x30) :|: TRUE f276_in(x31) -> f277_in(x31) :|: TRUE f279_out(x32) -> f276_out(x32) :|: TRUE f412_in -> f412_out :|: TRUE f58_in(x33) -> f270_in :|: TRUE f269_out(x34, x35) -> f58_out(.(x34, .(x35, []))) :|: TRUE f270_out -> f58_out(x36) :|: TRUE f58_in(.(x37, .(x38, []))) -> f269_in(x37, x38) :|: TRUE f430_in -> f430_out :|: TRUE f274_in(x39) -> f276_in(x39) :|: TRUE f276_out(x40) -> f274_out(x40) :|: TRUE f3_in(T2) -> f7_in(T2) :|: TRUE f7_out(x41) -> f3_out(x41) :|: TRUE f51_out(x42) -> f7_out(x42) :|: TRUE f7_in(x43) -> f51_in(x43) :|: TRUE f52_out(x44) -> f53_in(x44) :|: TRUE f53_out(x45) -> f51_out(x45) :|: TRUE f51_in(x46) -> f52_in(x46) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (158) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f415_in(T55) -> f422_in(T55) :|: TRUE f422_out(x) -> f415_out(x) :|: TRUE f52_in(T9) -> f56_in(T9) :|: TRUE f275_in(T22) -> f52_in(T22) :|: TRUE f422_in(x3) -> f425_in(x3) :|: TRUE f426_out(x4) -> f422_out(x4) :|: TRUE f425_out(x5) -> f422_out(x5) :|: TRUE f422_in(x6) -> f426_in(x6) :|: TRUE f274_out(x7) -> f275_in(x8) :|: TRUE f269_in(x11, x12) -> f274_in(x11) :|: TRUE f279_in(x13) -> f415_in(x13) :|: TRUE f415_out(x14) -> f279_out(x14) :|: TRUE f426_in(T79) -> f435_in(T79) :|: TRUE f435_out(x16) -> f426_out(x16) :|: TRUE f56_in(x18) -> f58_in(x18) :|: TRUE f415_out(x22) -> f435_out(x22) :|: TRUE f435_in(x23) -> f415_in(x23) :|: TRUE f425_in(T71) -> f430_in :|: TRUE f430_out -> f425_out(x26) :|: TRUE f277_in(T42) -> f412_in :|: TRUE f412_out -> f277_out(x28) :|: TRUE f277_out(x29) -> f276_out(x29) :|: TRUE f276_in(x30) -> f279_in(x30) :|: TRUE f276_in(x31) -> f277_in(x31) :|: TRUE f279_out(x32) -> f276_out(x32) :|: TRUE f412_in -> f412_out :|: TRUE f58_in(.(x37, .(x38, []))) -> f269_in(x37, x38) :|: TRUE f430_in -> f430_out :|: TRUE f274_in(x39) -> f276_in(x39) :|: TRUE f276_out(x40) -> f274_out(x40) :|: TRUE ---------------------------------------- (159) Obligation: Rules: f415_in(T55) -> f422_in(T55) :|: TRUE f422_out(x) -> f415_out(x) :|: TRUE f52_in(T9) -> f56_in(T9) :|: TRUE f275_in(T22) -> f52_in(T22) :|: TRUE f422_in(x3) -> f425_in(x3) :|: TRUE f426_out(x4) -> f422_out(x4) :|: TRUE f425_out(x5) -> f422_out(x5) :|: TRUE f422_in(x6) -> f426_in(x6) :|: TRUE f274_out(x7) -> f275_in(x8) :|: TRUE f269_in(x11, x12) -> f274_in(x11) :|: TRUE f279_in(x13) -> f415_in(x13) :|: TRUE f415_out(x14) -> f279_out(x14) :|: TRUE f426_in(T79) -> f435_in(T79) :|: TRUE f435_out(x16) -> f426_out(x16) :|: TRUE f56_in(x18) -> f58_in(x18) :|: TRUE f415_out(x22) -> f435_out(x22) :|: TRUE f435_in(x23) -> f415_in(x23) :|: TRUE f425_in(T71) -> f430_in :|: TRUE f430_out -> f425_out(x26) :|: TRUE f277_in(T42) -> f412_in :|: TRUE f412_out -> f277_out(x28) :|: TRUE f277_out(x29) -> f276_out(x29) :|: TRUE f276_in(x30) -> f279_in(x30) :|: TRUE f276_in(x31) -> f277_in(x31) :|: TRUE f279_out(x32) -> f276_out(x32) :|: TRUE f412_in -> f412_out :|: TRUE f58_in(.(x37, .(x38, []))) -> f269_in(x37, x38) :|: TRUE f430_in -> f430_out :|: TRUE f274_in(x39) -> f276_in(x39) :|: TRUE f276_out(x40) -> f274_out(x40) :|: TRUE