MAYBE proof of /export/starexec/sandbox/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, 13 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, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) MRRProof [EQUIVALENT, 20 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 1 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) PiDPToQDPProof [SOUND, 0 ms] (34) QDP (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] (36) YES (37) PrologToPiTRSProof [SOUND, 0 ms] (38) PiTRS (39) DependencyPairsProof [EQUIVALENT, 6 ms] (40) PiDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) AND (43) PiDP (44) UsableRulesProof [EQUIVALENT, 0 ms] (45) PiDP (46) PiDPToQDPProof [EQUIVALENT, 0 ms] (47) QDP (48) QDPSizeChangeProof [EQUIVALENT, 0 ms] (49) YES (50) PiDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) PiDP (53) PiDPToQDPProof [SOUND, 0 ms] (54) QDP (55) UsableRulesReductionPairsProof [EQUIVALENT, 16 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) TRUE (59) PiDP (60) UsableRulesProof [EQUIVALENT, 0 ms] (61) PiDP (62) PiDPToQDPProof [SOUND, 0 ms] (63) QDP (64) NonTerminationLoopProof [COMPLETE, 0 ms] (65) NO (66) PiDP (67) UsableRulesProof [EQUIVALENT, 0 ms] (68) PiDP (69) PiDPToQDPProof [SOUND, 0 ms] (70) QDP (71) QDPSizeChangeProof [EQUIVALENT, 0 ms] (72) YES (73) PrologToTRSTransformerProof [SOUND, 45 ms] (74) QTRS (75) DependencyPairsProof [EQUIVALENT, 0 ms] (76) QDP (77) DependencyGraphProof [EQUIVALENT, 0 ms] (78) AND (79) QDP (80) MNOCProof [EQUIVALENT, 0 ms] (81) QDP (82) UsableRulesProof [EQUIVALENT, 0 ms] (83) QDP (84) QReductionProof [EQUIVALENT, 0 ms] (85) QDP (86) QDPSizeChangeProof [EQUIVALENT, 0 ms] (87) YES (88) QDP (89) MNOCProof [EQUIVALENT, 0 ms] (90) QDP (91) UsableRulesProof [EQUIVALENT, 0 ms] (92) QDP (93) QReductionProof [EQUIVALENT, 0 ms] (94) QDP (95) QDPOrderProof [EQUIVALENT, 23 ms] (96) QDP (97) DependencyGraphProof [EQUIVALENT, 0 ms] (98) TRUE (99) QDP (100) MNOCProof [EQUIVALENT, 0 ms] (101) QDP (102) UsableRulesProof [EQUIVALENT, 0 ms] (103) QDP (104) QReductionProof [EQUIVALENT, 0 ms] (105) QDP (106) NonTerminationLoopProof [COMPLETE, 0 ms] (107) NO (108) QDP (109) MNOCProof [EQUIVALENT, 0 ms] (110) QDP (111) UsableRulesProof [EQUIVALENT, 0 ms] (112) QDP (113) QReductionProof [EQUIVALENT, 0 ms] (114) QDP (115) QDPSizeChangeProof [EQUIVALENT, 0 ms] (116) YES (117) PrologToDTProblemTransformerProof [SOUND, 33 ms] (118) TRIPLES (119) TriplesToPiDPProof [SOUND, 22 ms] (120) PiDP (121) DependencyGraphProof [EQUIVALENT, 0 ms] (122) AND (123) PiDP (124) UsableRulesProof [EQUIVALENT, 0 ms] (125) PiDP (126) PiDPToQDPProof [EQUIVALENT, 0 ms] (127) QDP (128) QDPSizeChangeProof [EQUIVALENT, 0 ms] (129) YES (130) PiDP (131) UsableRulesProof [EQUIVALENT, 0 ms] (132) PiDP (133) PiDPToQDPProof [SOUND, 0 ms] (134) QDP (135) NonTerminationLoopProof [COMPLETE, 0 ms] (136) NO (137) PiDP (138) UsableRulesProof [EQUIVALENT, 0 ms] (139) PiDP (140) PiDPToQDPProof [SOUND, 0 ms] (141) QDP (142) QDPSizeChangeProof [EQUIVALENT, 0 ms] (143) YES (144) PrologToIRSwTTransformerProof [SOUND, 32 ms] (145) AND (146) IRSwT (147) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (148) TRUE (149) IRSwT (150) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 1 ms] (151) IRSwT (152) IntTRSCompressionProof [EQUIVALENT, 27 ms] (153) IRSwT (154) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (155) IRSwT (156) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (157) IRSwT (158) FilterProof [EQUIVALENT, 0 ms] (159) IntTRS (160) IntTRSPeriodicNontermProof [COMPLETE, 0 ms] (161) NO (162) IRSwT (163) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (164) TRUE (165) IRSwT (166) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (167) IRSwT (168) IntTRSCompressionProof [EQUIVALENT, 10 ms] (169) IRSwT (170) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (171) 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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: 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. ---------------------------------------- (19) 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 ---------------------------------------- (20) 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. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (33) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (34) 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. ---------------------------------------- (35) 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 ---------------------------------------- (36) YES ---------------------------------------- (37) 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 ---------------------------------------- (38) 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 ---------------------------------------- (39) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (40) 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 ---------------------------------------- (41) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes. ---------------------------------------- (42) Complex Obligation (AND) ---------------------------------------- (43) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (44) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (45) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (46) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: 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. ---------------------------------------- (48) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (49) YES ---------------------------------------- (50) 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 ---------------------------------------- (51) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (53) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: 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. ---------------------------------------- (55) 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 ---------------------------------------- (56) 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. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (58) TRUE ---------------------------------------- (59) 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 ---------------------------------------- (60) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (61) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (62) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (63) 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. ---------------------------------------- (64) 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). ---------------------------------------- (65) NO ---------------------------------------- (66) 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 ---------------------------------------- (67) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (68) 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 ---------------------------------------- (69) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AG(V, delete_out_gaa) -> PERM_IN_AG(V) PERM_IN_AG(.(U, .(V, []))) -> U5_AG(V, delete_in_gaa(U)) The TRS R consists of the following rules: delete_in_gaa(X) -> delete_out_gaa delete_in_gaa(X) -> U7_gaa(delete_in_gaa(X)) U7_gaa(delete_out_gaa) -> delete_out_gaa The set Q consists of the following terms: delete_in_gaa(x0) U7_gaa(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (71) 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(V, delete_in_gaa(U)) The graph contains the following edges 1 > 1 *U5_AG(V, delete_out_gaa) -> PERM_IN_AG(V) The graph contains the following edges 1 >= 1 ---------------------------------------- (72) YES ---------------------------------------- (73) 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", "470": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "350": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "471": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "351": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "472": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "354": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "355": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "432": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "356": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "434": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T99 T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T100" ], "free": [], "exprvars": [] } }, "435": { "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": [] } }, "436": { "goal": [{ "clause": 8, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "437": { "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": [] } }, "317": { "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": [] } }, "439": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "360": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T79 T82 X86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T79"], "free": ["X86"], "exprvars": [] } }, "284": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T10 T9) (sorted T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "363": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "440": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "288": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "321": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "289": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "444": { "goal": [{ "clause": 9, "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": [] } }, "445": { "goal": [{ "clause": 10, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "290": { "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": [] } }, "291": { "goal": [{ "clause": 4, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "292": { "goal": [{ "clause": 5, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "294": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "371": { "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": [] } }, "295": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "372": { "goal": [{ "clause": 1, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "373": { "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": [] } }, "374": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "298": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "331": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "375": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "332": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T29 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } }, "376": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "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": [] } }, "336": { "goal": [{ "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "337": { "goal": [{ "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "338": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "340": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "341": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "342": { "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": [] } }, "420": { "goal": [{ "clause": 2, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "421": { "goal": [{ "clause": 3, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "422": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "466": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "423": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "424": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "468": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "469": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "426": { "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": [] } }, "427": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 284, "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": 284, "to": 288, "label": "SPLIT 1" }, { "from": 284, "to": 289, "label": "SPLIT 2\nnew knowledge:\nT9 is ground" }, { "from": 288, "to": 290, "label": "CASE" }, { "from": 289, "to": 371, "label": "CASE" }, { "from": 290, "to": 291, "label": "PARALLEL" }, { "from": 290, "to": 292, "label": "PARALLEL" }, { "from": 291, "to": 294, "label": "EVAL with clause\nperm([], []).\nand substitutionT10 -> [],\nT9 -> []" }, { "from": 291, "to": 295, "label": "EVAL-BACKTRACK" }, { "from": 292, "to": 317, "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": 292, "to": 321, "label": "EVAL-BACKTRACK" }, { "from": 294, "to": 298, "label": "SUCCESS" }, { "from": 317, "to": 331, "label": "SPLIT 1" }, { "from": 317, "to": 332, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nreplacements:X20 -> T29" }, { "from": 331, "to": 335, "label": "CASE" }, { "from": 332, "to": 288, "label": "INSTANCE with matching:\nT10 -> T29\nT9 -> T22" }, { "from": 335, "to": 336, "label": "PARALLEL" }, { "from": 335, "to": 337, "label": "PARALLEL" }, { "from": 336, "to": 338, "label": "EVAL with clause\ndelete(X37, .(X37, X38), X38).\nand substitutionT21 -> T42,\nX37 -> T42,\nT23 -> T42,\nT24 -> T43,\nX38 -> T43,\nX20 -> T43" }, { "from": 336, "to": 339, "label": "EVAL-BACKTRACK" }, { "from": 337, "to": 341, "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": 338, "to": 340, "label": "SUCCESS" }, { "from": 341, "to": 342, "label": "CASE" }, { "from": 342, "to": 350, "label": "PARALLEL" }, { "from": 342, "to": 351, "label": "PARALLEL" }, { "from": 350, "to": 354, "label": "EVAL with clause\ndelete(X70, .(X70, X71), X71).\nand substitutionT55 -> T71,\nX70 -> T71,\nX71 -> T72,\nT58 -> .(T71, T72),\nX57 -> T72" }, { "from": 350, "to": 355, "label": "EVAL-BACKTRACK" }, { "from": 351, "to": 360, "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": 351, "to": 363, "label": "EVAL-BACKTRACK" }, { "from": 354, "to": 356, "label": "SUCCESS" }, { "from": 360, "to": 341, "label": "INSTANCE with matching:\nT55 -> T79\nT58 -> T82\nX57 -> X86" }, { "from": 371, "to": 372, "label": "PARALLEL" }, { "from": 371, "to": 373, "label": "PARALLEL" }, { "from": 372, "to": 374, "label": "EVAL with clause\nsorted([]).\nand substitutionT9 -> []" }, { "from": 372, "to": 375, "label": "EVAL-BACKTRACK" }, { "from": 373, "to": 420, "label": "PARALLEL" }, { "from": 373, "to": 421, "label": "PARALLEL" }, { "from": 374, "to": 376, "label": "SUCCESS" }, { "from": 420, "to": 422, "label": "EVAL with clause\nsorted(.(X95, [])).\nand substitutionX95 -> T91,\nT9 -> .(T91, [])" }, { "from": 420, "to": 423, "label": "EVAL-BACKTRACK" }, { "from": 421, "to": 426, "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": 421, "to": 427, "label": "EVAL-BACKTRACK" }, { "from": 422, "to": 424, "label": "SUCCESS" }, { "from": 426, "to": 432, "label": "SPLIT 1" }, { "from": 426, "to": 434, "label": "SPLIT 2\nnew knowledge:\nT98 is ground\nT99 is ground" }, { "from": 432, "to": 435, "label": "CASE" }, { "from": 434, "to": 289, "label": "INSTANCE with matching:\nT9 -> .(T99, T100)" }, { "from": 435, "to": 436, "label": "PARALLEL" }, { "from": 435, "to": 437, "label": "PARALLEL" }, { "from": 436, "to": 439, "label": "EVAL with clause\nle(s(X117), s(X118)) :- le(X117, X118).\nand substitutionX117 -> T113,\nT98 -> s(T113),\nX118 -> T114,\nT99 -> s(T114)" }, { "from": 436, "to": 440, "label": "EVAL-BACKTRACK" }, { "from": 437, "to": 444, "label": "PARALLEL" }, { "from": 437, "to": 445, "label": "PARALLEL" }, { "from": 439, "to": 432, "label": "INSTANCE with matching:\nT98 -> T113\nT99 -> T114" }, { "from": 444, "to": 466, "label": "EVAL with clause\nle(0, s(X125)).\nand substitutionT98 -> 0,\nX125 -> T121,\nT99 -> s(T121)" }, { "from": 444, "to": 468, "label": "EVAL-BACKTRACK" }, { "from": 445, "to": 470, "label": "EVAL with clause\nle(0, 0).\nand substitutionT98 -> 0,\nT99 -> 0" }, { "from": 445, "to": 471, "label": "EVAL-BACKTRACK" }, { "from": 466, "to": 469, "label": "SUCCESS" }, { "from": 470, "to": 472, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (74) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 Q is empty. ---------------------------------------- (75) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T9) -> U1^1(f284_in(T9), T9) F1_IN(T9) -> F284_IN(T9) F288_IN(.(T21, .(T22, []))) -> U2^1(f317_in(T21, T22), .(T21, .(T22, []))) F288_IN(.(T21, .(T22, []))) -> F317_IN(T21, T22) F341_IN(T79) -> U3^1(f341_in(T79), T79) F341_IN(T79) -> F341_IN(T79) F289_IN(.(T98, .(T99, T100))) -> U4^1(f426_in(T98, T99, T100), .(T98, .(T99, T100))) F289_IN(.(T98, .(T99, T100))) -> F426_IN(T98, T99, T100) F432_IN(s(T113), s(T114)) -> U5^1(f432_in(T113, T114), s(T113), s(T114)) F432_IN(s(T113), s(T114)) -> F432_IN(T113, T114) F331_IN(T55) -> U6^1(f341_in(T55), T55) F331_IN(T55) -> F341_IN(T55) F284_IN(T9) -> U7^1(f288_in(T9), T9) F284_IN(T9) -> F288_IN(T9) U7^1(f288_out1, T9) -> U8^1(f289_in(T9), T9) U7^1(f288_out1, T9) -> F289_IN(T9) F317_IN(T21, T22) -> U9^1(f331_in(T21), T21, T22) F317_IN(T21, T22) -> F331_IN(T21) U9^1(f331_out1, T21, T22) -> U10^1(f288_in(T22), T21, T22) U9^1(f331_out1, T21, T22) -> F288_IN(T22) F426_IN(T98, T99, T100) -> U11^1(f432_in(T98, T99), T98, T99, T100) F426_IN(T98, T99, T100) -> F432_IN(T98, T99) U11^1(f432_out1, T98, T99, T100) -> U12^1(f289_in(.(T99, T100)), T98, T99, T100) U11^1(f432_out1, T98, T99, T100) -> F289_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 16 less nodes. ---------------------------------------- (78) Complex Obligation (AND) ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: F432_IN(s(T113), s(T114)) -> F432_IN(T113, T114) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: F432_IN(s(T113), s(T114)) -> F432_IN(T113, T114) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) 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. ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: F432_IN(s(T113), s(T114)) -> F432_IN(T113, T114) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) 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(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: F432_IN(s(T113), s(T114)) -> F432_IN(T113, T114) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) 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: *F432_IN(s(T113), s(T114)) -> F432_IN(T113, T114) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (87) YES ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(.(T98, .(T99, T100))) -> F426_IN(T98, T99, T100) F426_IN(T98, T99, T100) -> U11^1(f432_in(T98, T99), T98, T99, T100) U11^1(f432_out1, T98, T99, T100) -> F289_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (89) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(.(T98, .(T99, T100))) -> F426_IN(T98, T99, T100) F426_IN(T98, T99, T100) -> U11^1(f432_in(T98, T99), T98, T99, T100) U11^1(f432_out1, T98, T99, T100) -> F289_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (91) 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. ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(.(T98, .(T99, T100))) -> F426_IN(T98, T99, T100) F426_IN(T98, T99, T100) -> U11^1(f432_in(T98, T99), T98, T99, T100) U11^1(f432_out1, T98, T99, T100) -> F289_IN(.(T99, T100)) The TRS R consists of the following rules: f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 U5(f432_out1, s(T113), s(T114)) -> f432_out1 The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) 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(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(.(T98, .(T99, T100))) -> F426_IN(T98, T99, T100) F426_IN(T98, T99, T100) -> U11^1(f432_in(T98, T99), T98, T99, T100) U11^1(f432_out1, T98, T99, T100) -> F289_IN(.(T99, T100)) The TRS R consists of the following rules: f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 U5(f432_out1, s(T113), s(T114)) -> f432_out1 The set Q consists of the following terms: f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U11^1(f432_out1, T98, T99, T100) -> F289_IN(.(T99, T100)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U11^1_4(x_1, ..., x_4) ) = 2x_1 + 2x_3 + 2x_4 + 2 POL( f432_in_2(x_1, x_2) ) = x_1 POL( s_1(x_1) ) = 2x_1 POL( U5_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( 0 ) = 2 POL( f432_out1 ) = 2 POL( F289_IN_1(x_1) ) = x_1 + 2 POL( ._2(x_1, x_2) ) = 2x_1 + 2x_2 POL( F426_IN_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + 2x_3 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 U5(f432_out1, s(T113), s(T114)) -> f432_out1 ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(.(T98, .(T99, T100))) -> F426_IN(T98, T99, T100) F426_IN(T98, T99, T100) -> U11^1(f432_in(T98, T99), T98, T99, T100) The TRS R consists of the following rules: f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 U5(f432_out1, s(T113), s(T114)) -> f432_out1 The set Q consists of the following terms: f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (98) TRUE ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: F341_IN(T79) -> F341_IN(T79) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: F341_IN(T79) -> F341_IN(T79) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) 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. ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: F341_IN(T79) -> F341_IN(T79) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (104) 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(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: F341_IN(T79) -> F341_IN(T79) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (106) 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 = F341_IN(T79) evaluates to t =F341_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 F341_IN(T79) to F341_IN(T79). ---------------------------------------- (107) NO ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: F288_IN(.(T21, .(T22, []))) -> F317_IN(T21, T22) F317_IN(T21, T22) -> U9^1(f331_in(T21), T21, T22) U9^1(f331_out1, T21, T22) -> F288_IN(T22) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (110) Obligation: Q DP problem: The TRS P consists of the following rules: F288_IN(.(T21, .(T22, []))) -> F317_IN(T21, T22) F317_IN(T21, T22) -> U9^1(f331_in(T21), T21, T22) U9^1(f331_out1, T21, T22) -> F288_IN(T22) The TRS R consists of the following rules: f1_in(T9) -> U1(f284_in(T9), T9) U1(f284_out1, T9) -> f1_out1 f288_in([]) -> f288_out1 f288_in(.(T21, .(T22, []))) -> U2(f317_in(T21, T22), .(T21, .(T22, []))) U2(f317_out1, .(T21, .(T22, []))) -> f288_out1 f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U3(f341_out1, T79) -> f341_out1 f289_in([]) -> f289_out1 f289_in(.(T91, [])) -> f289_out1 f289_in(.(T98, .(T99, T100))) -> U4(f426_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f426_out1, .(T98, .(T99, T100))) -> f289_out1 f432_in(s(T113), s(T114)) -> U5(f432_in(T113, T114), s(T113), s(T114)) U5(f432_out1, s(T113), s(T114)) -> f432_out1 f432_in(0, s(T121)) -> f432_out1 f432_in(0, 0) -> f432_out1 f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) U6(f341_out1, T55) -> f331_out1 f284_in(T9) -> U7(f288_in(T9), T9) U7(f288_out1, T9) -> U8(f289_in(T9), T9) U8(f289_out1, T9) -> f284_out1 f317_in(T21, T22) -> U9(f331_in(T21), T21, T22) U9(f331_out1, T21, T22) -> U10(f288_in(T22), T21, T22) U10(f288_out1, T21, T22) -> f317_out1 f426_in(T98, T99, T100) -> U11(f432_in(T98, T99), T98, T99, T100) U11(f432_out1, T98, T99, T100) -> U12(f289_in(.(T99, T100)), T98, T99, T100) U12(f289_out1, T98, T99, T100) -> f426_out1 The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (111) 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. ---------------------------------------- (112) Obligation: Q DP problem: The TRS P consists of the following rules: F288_IN(.(T21, .(T22, []))) -> F317_IN(T21, T22) F317_IN(T21, T22) -> U9^1(f331_in(T21), T21, T22) U9^1(f331_out1, T21, T22) -> F288_IN(T22) The TRS R consists of the following rules: f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U6(f341_out1, T55) -> f331_out1 U3(f341_out1, T79) -> f341_out1 The set Q consists of the following terms: f1_in(x0) U1(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f341_in(x0) U3(f341_out1, x0) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f331_in(x0) U6(f341_out1, x0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (113) 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(f284_out1, x0) f288_in([]) f288_in(.(x0, .(x1, []))) U2(f317_out1, .(x0, .(x1, []))) f289_in([]) f289_in(.(x0, [])) f289_in(.(x0, .(x1, x2))) U4(f426_out1, .(x0, .(x1, x2))) f432_in(s(x0), s(x1)) U5(f432_out1, s(x0), s(x1)) f432_in(0, s(x0)) f432_in(0, 0) f284_in(x0) U7(f288_out1, x0) U8(f289_out1, x0) f317_in(x0, x1) U9(f331_out1, x0, x1) U10(f288_out1, x0, x1) f426_in(x0, x1, x2) U11(f432_out1, x0, x1, x2) U12(f289_out1, x0, x1, x2) ---------------------------------------- (114) Obligation: Q DP problem: The TRS P consists of the following rules: F288_IN(.(T21, .(T22, []))) -> F317_IN(T21, T22) F317_IN(T21, T22) -> U9^1(f331_in(T21), T21, T22) U9^1(f331_out1, T21, T22) -> F288_IN(T22) The TRS R consists of the following rules: f331_in(T42) -> f331_out1 f331_in(T55) -> U6(f341_in(T55), T55) f341_in(T71) -> f341_out1 f341_in(T79) -> U3(f341_in(T79), T79) U6(f341_out1, T55) -> f331_out1 U3(f341_out1, T79) -> f341_out1 The set Q consists of the following terms: f341_in(x0) U3(f341_out1, x0) f331_in(x0) U6(f341_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (115) 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: *F317_IN(T21, T22) -> U9^1(f331_in(T21), T21, T22) The graph contains the following edges 1 >= 2, 2 >= 3 *U9^1(f331_out1, T21, T22) -> F288_IN(T22) The graph contains the following edges 3 >= 1 *F288_IN(.(T21, .(T22, []))) -> F317_IN(T21, T22) The graph contains the following edges 1 > 1, 1 > 2 ---------------------------------------- (116) YES ---------------------------------------- (117) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "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": { "type": "Nodes", "473": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "550": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "430": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "474": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T18 (. T19 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "551": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "277": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "310": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "431": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "552": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "278": { "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": [] } }, "553": { "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": [] } }, "433": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "554": { "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": [] } }, "555": { "goal": [{ "clause": 2, "scope": 9, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "556": { "goal": [{ "clause": 3, "scope": 9, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "557": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "558": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "438": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "559": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "281": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "282": { "goal": [{ "clause": 5, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "287": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "441": { "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": [] } }, "442": { "goal": [{ "clause": 6, "scope": 5, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "443": { "goal": [{ "clause": 7, "scope": 5, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "446": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "447": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "327": { "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": [] } }, "448": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "527": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "528": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "529": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "293": { "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": [] } }, "491": { "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": [] } }, "492": { "goal": [{ "clause": 4, "scope": 6, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "493": { "goal": [{ "clause": 5, "scope": 6, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "296": { "goal": [{ "clause": 1, "scope": 3, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "297": { "goal": [ { "clause": 2, "scope": 3, "term": "(sorted ([]))" }, { "clause": 3, "scope": 3, "term": "(sorted ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "330": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "530": { "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": [] } }, "333": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "531": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "334": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T26 T19) (sorted (. T18 (. T19 ([])))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "532": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T94 (. T96 T97) X106)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": ["X106"], "exprvars": [] } }, "533": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T102 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T95"], "free": [], "exprvars": [] } }, "534": { "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": [] } }, "535": { "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": [] } }, "536": { "goal": [{ "clause": 3, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "537": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T114 T115) (sorted (. T115 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "538": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "539": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "540": { "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": [] } }, "541": { "goal": [{ "clause": 8, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "465": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T76 T79 X88)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T76"], "free": ["X88"], "exprvars": [] } }, "542": { "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": [] } }, "301": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "543": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T128 T129)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T129" ], "free": [], "exprvars": [] } }, "302": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "467": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "544": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "545": { "goal": [{ "clause": 9, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "425": { "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": [] } }, "546": { "goal": [{ "clause": 10, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "305": { "goal": [{ "clause": 3, "scope": 3, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "547": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "548": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "428": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "549": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "429": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 277, "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": 277, "to": 278, "label": "CASE" }, { "from": 278, "to": 281, "label": "PARALLEL" }, { "from": 278, "to": 282, "label": "PARALLEL" }, { "from": 281, "to": 286, "label": "EVAL with clause\nperm([], []).\nand substitutionT7 -> [],\nT6 -> []" }, { "from": 281, "to": 287, "label": "EVAL-BACKTRACK" }, { "from": 282, "to": 327, "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": 282, "to": 330, "label": "EVAL-BACKTRACK" }, { "from": 286, "to": 293, "label": "CASE" }, { "from": 293, "to": 296, "label": "PARALLEL" }, { "from": 293, "to": 297, "label": "PARALLEL" }, { "from": 296, "to": 301, "label": "ONLY EVAL with clause\nsorted([]).\nand substitution" }, { "from": 297, "to": 305, "label": "BACKTRACK\nfor clause: sorted(.(X, []))because of non-unification" }, { "from": 301, "to": 302, "label": "SUCCESS" }, { "from": 305, "to": 310, "label": "BACKTRACK\nfor clause: sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z)))because of non-unification" }, { "from": 327, "to": 333, "label": "SPLIT 1" }, { "from": 327, "to": 334, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nreplacements:X22 -> T26" }, { "from": 333, "to": 425, "label": "CASE" }, { "from": 334, "to": 473, "label": "SPLIT 1" }, { "from": 334, "to": 474, "label": "SPLIT 2\nnew knowledge:\nT19 is ground" }, { "from": 425, "to": 428, "label": "PARALLEL" }, { "from": 425, "to": 429, "label": "PARALLEL" }, { "from": 428, "to": 430, "label": "EVAL with clause\ndelete(X39, .(X39, X40), X40).\nand substitutionT18 -> T39,\nX39 -> T39,\nT20 -> T39,\nT21 -> T40,\nX40 -> T40,\nX22 -> T40" }, { "from": 428, "to": 431, "label": "EVAL-BACKTRACK" }, { "from": 429, "to": 438, "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": 430, "to": 433, "label": "SUCCESS" }, { "from": 438, "to": 441, "label": "CASE" }, { "from": 441, "to": 442, "label": "PARALLEL" }, { "from": 441, "to": 443, "label": "PARALLEL" }, { "from": 442, "to": 446, "label": "EVAL with clause\ndelete(X72, .(X72, X73), X73).\nand substitutionT52 -> T68,\nX72 -> T68,\nX73 -> T69,\nT55 -> .(T68, T69),\nX59 -> T69" }, { "from": 442, "to": 447, "label": "EVAL-BACKTRACK" }, { "from": 443, "to": 465, "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": 443, "to": 467, "label": "EVAL-BACKTRACK" }, { "from": 446, "to": 448, "label": "SUCCESS" }, { "from": 465, "to": 438, "label": "INSTANCE with matching:\nT52 -> T76\nT55 -> T79\nX59 -> X88" }, { "from": 473, "to": 491, "label": "CASE" }, { "from": 474, "to": 534, "label": "CASE" }, { "from": 491, "to": 492, "label": "PARALLEL" }, { "from": 491, "to": 493, "label": "PARALLEL" }, { "from": 492, "to": 527, "label": "EVAL with clause\nperm([], []).\nand substitutionT26 -> [],\nT19 -> []" }, { "from": 492, "to": 528, "label": "EVAL-BACKTRACK" }, { "from": 493, "to": 530, "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": 493, "to": 531, "label": "EVAL-BACKTRACK" }, { "from": 527, "to": 529, "label": "SUCCESS" }, { "from": 530, "to": 532, "label": "SPLIT 1" }, { "from": 530, "to": 533, "label": "SPLIT 2\nnew knowledge:\nT94 is ground\nreplacements:X106 -> T102" }, { "from": 532, "to": 333, "label": "INSTANCE with matching:\nT18 -> T94\nT20 -> T96\nT21 -> T97\nX22 -> X106" }, { "from": 533, "to": 473, "label": "INSTANCE with matching:\nT26 -> T102\nT19 -> T95" }, { "from": 534, "to": 535, "label": "BACKTRACK\nfor clause: sorted([])because of non-unification" }, { "from": 535, "to": 536, "label": "BACKTRACK\nfor clause: sorted(.(X, []))because of non-unification" }, { "from": 536, "to": 537, "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": 537, "to": 538, "label": "SPLIT 1" }, { "from": 537, "to": 539, "label": "SPLIT 2\nnew knowledge:\nT114 is ground\nT115 is ground" }, { "from": 538, "to": 540, "label": "CASE" }, { "from": 539, "to": 553, "label": "CASE" }, { "from": 540, "to": 541, "label": "PARALLEL" }, { "from": 540, "to": 542, "label": "PARALLEL" }, { "from": 541, "to": 543, "label": "EVAL with clause\nle(s(X139), s(X140)) :- le(X139, X140).\nand substitutionX139 -> T128,\nT114 -> s(T128),\nX140 -> T129,\nT115 -> s(T129)" }, { "from": 541, "to": 544, "label": "EVAL-BACKTRACK" }, { "from": 542, "to": 545, "label": "PARALLEL" }, { "from": 542, "to": 546, "label": "PARALLEL" }, { "from": 543, "to": 538, "label": "INSTANCE with matching:\nT114 -> T128\nT115 -> T129" }, { "from": 545, "to": 547, "label": "EVAL with clause\nle(0, s(X147)).\nand substitutionT114 -> 0,\nX147 -> T136,\nT115 -> s(T136)" }, { "from": 545, "to": 548, "label": "EVAL-BACKTRACK" }, { "from": 546, "to": 550, "label": "EVAL with clause\nle(0, 0).\nand substitutionT114 -> 0,\nT115 -> 0" }, { "from": 546, "to": 551, "label": "EVAL-BACKTRACK" }, { "from": 547, "to": 549, "label": "SUCCESS" }, { "from": 550, "to": 552, "label": "SUCCESS" }, { "from": 553, "to": 554, "label": "BACKTRACK\nfor clause: sorted([])because of non-unification" }, { "from": 554, "to": 555, "label": "PARALLEL" }, { "from": 554, "to": 556, "label": "PARALLEL" }, { "from": 555, "to": 557, "label": "ONLY EVAL with clause\nsorted(.(X152, [])).\nand substitutionT115 -> T141,\nX152 -> T141" }, { "from": 556, "to": 559, "label": "BACKTRACK\nfor clause: sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z)))because of non-unification" }, { "from": 557, "to": 558, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (118) 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) ---------------------------------------- (119) 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 ---------------------------------------- (120) 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 ---------------------------------------- (121) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 15 less nodes. ---------------------------------------- (122) Complex Obligation (AND) ---------------------------------------- (123) 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 ---------------------------------------- (124) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (125) 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 ---------------------------------------- (126) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (127) 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. ---------------------------------------- (128) 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 ---------------------------------------- (129) YES ---------------------------------------- (130) 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 ---------------------------------------- (131) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (132) 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 ---------------------------------------- (133) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (134) 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. ---------------------------------------- (135) 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). ---------------------------------------- (136) NO ---------------------------------------- (137) 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 ---------------------------------------- (138) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (139) 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 ---------------------------------------- (140) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (141) Obligation: Q DP problem: The TRS P consists of the following rules: PERMC_IN_AG(.(X3, .(X4, []))) -> U4_AG(X3, X4, deletecB_in_gaaa(X3)) U4_AG(X3, X4, deletecB_out_gaaa(X3)) -> PERMC_IN_AG(X4) The TRS R consists of the following rules: deletecB_in_gaaa(X1) -> deletecB_out_gaaa(X1) deletecB_in_gaaa(X1) -> U14_gaaa(X1, deletecA_in_gaa(X1)) U14_gaaa(X1, deletecA_out_gaa(X1)) -> deletecB_out_gaaa(X1) deletecA_in_gaa(X1) -> deletecA_out_gaa(X1) deletecA_in_gaa(X1) -> U13_gaa(X1, deletecA_in_gaa(X1)) U13_gaa(X1, deletecA_out_gaa(X1)) -> deletecA_out_gaa(X1) The set Q consists of the following terms: deletecB_in_gaaa(x0) U14_gaaa(x0, x1) deletecA_in_gaa(x0) U13_gaa(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (142) 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: *U4_AG(X3, X4, deletecB_out_gaaa(X3)) -> PERMC_IN_AG(X4) The graph contains the following edges 2 >= 1 *PERMC_IN_AG(.(X3, .(X4, []))) -> U4_AG(X3, X4, deletecB_in_gaaa(X3)) The graph contains the following edges 1 > 1, 1 > 2 ---------------------------------------- (143) YES ---------------------------------------- (144) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "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": { "48": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "type": "Nodes", "352": { "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": [] } }, "353": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "475": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "476": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "477": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "357": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "478": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T79 T82 X86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T79"], "free": ["X86"], "exprvars": [] } }, "358": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T29 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } }, "479": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "359": { "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": [] } }, "50": { "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": [] } }, "518": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "519": { "goal": [{ "clause": 9, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "480": { "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": [] } }, "481": { "goal": [{ "clause": 1, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "361": { "goal": [{ "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "482": { "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": [] } }, "362": { "goal": [{ "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "483": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "484": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "364": { "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": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "365": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "486": { "goal": [{ "clause": 2, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "366": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "487": { "goal": [{ "clause": 3, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "520": { "goal": [{ "clause": 10, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "367": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "488": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "521": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "368": { "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": [] } }, "489": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "522": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "369": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "523": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "524": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "525": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "526": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T10 T9) (sorted T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "490": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "370": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "494": { "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": [] } }, "495": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "496": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "497": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T99 T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T100" ], "free": [], "exprvars": [] } }, "498": { "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": [] } }, "499": { "goal": [{ "clause": 8, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "343": { "goal": [{ "clause": 4, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": 5, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "500": { "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": [] } }, "347": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "501": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "348": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "349": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 28, "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": 28, "to": 48, "label": "SPLIT 1" }, { "from": 28, "to": 49, "label": "SPLIT 2\nnew knowledge:\nT9 is ground" }, { "from": 48, "to": 50, "label": "CASE" }, { "from": 49, "to": 480, "label": "CASE" }, { "from": 50, "to": 343, "label": "PARALLEL" }, { "from": 50, "to": 346, "label": "PARALLEL" }, { "from": 343, "to": 347, "label": "EVAL with clause\nperm([], []).\nand substitutionT10 -> [],\nT9 -> []" }, { "from": 343, "to": 348, "label": "EVAL-BACKTRACK" }, { "from": 346, "to": 352, "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": 346, "to": 353, "label": "EVAL-BACKTRACK" }, { "from": 347, "to": 349, "label": "SUCCESS" }, { "from": 352, "to": 357, "label": "SPLIT 1" }, { "from": 352, "to": 358, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nreplacements:X20 -> T29" }, { "from": 357, "to": 359, "label": "CASE" }, { "from": 358, "to": 48, "label": "INSTANCE with matching:\nT10 -> T29\nT9 -> T22" }, { "from": 359, "to": 361, "label": "PARALLEL" }, { "from": 359, "to": 362, "label": "PARALLEL" }, { "from": 361, "to": 364, "label": "EVAL with clause\ndelete(X37, .(X37, X38), X38).\nand substitutionT21 -> T42,\nX37 -> T42,\nT23 -> T42,\nT24 -> T43,\nX38 -> T43,\nX20 -> T43" }, { "from": 361, "to": 365, "label": "EVAL-BACKTRACK" }, { "from": 362, "to": 367, "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": 364, "to": 366, "label": "SUCCESS" }, { "from": 367, "to": 368, "label": "CASE" }, { "from": 368, "to": 369, "label": "PARALLEL" }, { "from": 368, "to": 370, "label": "PARALLEL" }, { "from": 369, "to": 475, "label": "EVAL with clause\ndelete(X70, .(X70, X71), X71).\nand substitutionT55 -> T71,\nX70 -> T71,\nX71 -> T72,\nT58 -> .(T71, T72),\nX57 -> T72" }, { "from": 369, "to": 476, "label": "EVAL-BACKTRACK" }, { "from": 370, "to": 478, "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": 370, "to": 479, "label": "EVAL-BACKTRACK" }, { "from": 475, "to": 477, "label": "SUCCESS" }, { "from": 478, "to": 367, "label": "INSTANCE with matching:\nT55 -> T79\nT58 -> T82\nX57 -> X86" }, { "from": 480, "to": 481, "label": "PARALLEL" }, { "from": 480, "to": 482, "label": "PARALLEL" }, { "from": 481, "to": 483, "label": "EVAL with clause\nsorted([]).\nand substitutionT9 -> []" }, { "from": 481, "to": 484, "label": "EVAL-BACKTRACK" }, { "from": 482, "to": 486, "label": "PARALLEL" }, { "from": 482, "to": 487, "label": "PARALLEL" }, { "from": 483, "to": 485, "label": "SUCCESS" }, { "from": 486, "to": 488, "label": "EVAL with clause\nsorted(.(X95, [])).\nand substitutionX95 -> T91,\nT9 -> .(T91, [])" }, { "from": 486, "to": 489, "label": "EVAL-BACKTRACK" }, { "from": 487, "to": 494, "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": 487, "to": 495, "label": "EVAL-BACKTRACK" }, { "from": 488, "to": 490, "label": "SUCCESS" }, { "from": 494, "to": 496, "label": "SPLIT 1" }, { "from": 494, "to": 497, "label": "SPLIT 2\nnew knowledge:\nT98 is ground\nT99 is ground" }, { "from": 496, "to": 498, "label": "CASE" }, { "from": 497, "to": 49, "label": "INSTANCE with matching:\nT9 -> .(T99, T100)" }, { "from": 498, "to": 499, "label": "PARALLEL" }, { "from": 498, "to": 500, "label": "PARALLEL" }, { "from": 499, "to": 501, "label": "EVAL with clause\nle(s(X117), s(X118)) :- le(X117, X118).\nand substitutionX117 -> T113,\nT98 -> s(T113),\nX118 -> T114,\nT99 -> s(T114)" }, { "from": 499, "to": 518, "label": "EVAL-BACKTRACK" }, { "from": 500, "to": 519, "label": "PARALLEL" }, { "from": 500, "to": 520, "label": "PARALLEL" }, { "from": 501, "to": 496, "label": "INSTANCE with matching:\nT98 -> T113\nT99 -> T114" }, { "from": 519, "to": 521, "label": "EVAL with clause\nle(0, s(X125)).\nand substitutionT98 -> 0,\nX125 -> T121,\nT99 -> s(T121)" }, { "from": 519, "to": 522, "label": "EVAL-BACKTRACK" }, { "from": 520, "to": 524, "label": "EVAL with clause\nle(0, 0).\nand substitutionT98 -> 0,\nT99 -> 0" }, { "from": 520, "to": 525, "label": "EVAL-BACKTRACK" }, { "from": 521, "to": 523, "label": "SUCCESS" }, { "from": 524, "to": 526, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (145) Complex Obligation (AND) ---------------------------------------- (146) Obligation: Rules: f500_out(T98, T99) -> f498_out(T98, T99) :|: TRUE f498_in(x, x1) -> f499_in(x, x1) :|: TRUE f498_in(x2, x3) -> f500_in(x2, x3) :|: TRUE f499_out(x4, x5) -> f498_out(x4, x5) :|: TRUE f499_in(x6, x7) -> f518_in :|: TRUE f501_out(T113, T114) -> f499_out(s(T113), s(T114)) :|: TRUE f499_in(s(x8), s(x9)) -> f501_in(x8, x9) :|: TRUE f518_out -> f499_out(x10, x11) :|: TRUE f498_out(x12, x13) -> f496_out(x12, x13) :|: TRUE f496_in(x14, x15) -> f498_in(x14, x15) :|: TRUE f501_in(x16, x17) -> f496_in(x16, x17) :|: TRUE f496_out(x18, x19) -> f501_out(x18, x19) :|: TRUE f2_in(T2) -> f6_in(T2) :|: TRUE f6_out(x20) -> f2_out(x20) :|: TRUE f28_out(T9) -> f6_out(T9) :|: TRUE f6_in(x21) -> f28_in(x21) :|: TRUE f28_in(x22) -> f48_in(x22) :|: TRUE f49_out(x23) -> f28_out(x23) :|: TRUE f48_out(x24) -> f49_in(x24) :|: TRUE f49_in(x25) -> f480_in(x25) :|: TRUE f480_out(x26) -> f49_out(x26) :|: TRUE f480_in(x27) -> f481_in(x27) :|: TRUE f480_in(x28) -> f482_in(x28) :|: TRUE f481_out(x29) -> f480_out(x29) :|: TRUE f482_out(x30) -> f480_out(x30) :|: TRUE f487_out(x31) -> f482_out(x31) :|: TRUE f486_out(x32) -> f482_out(x32) :|: TRUE f482_in(x33) -> f487_in(x33) :|: TRUE f482_in(x34) -> f486_in(x34) :|: TRUE f487_in(.(x35, .(x36, x37))) -> f494_in(x35, x36, x37) :|: TRUE f494_out(x38, x39, x40) -> f487_out(.(x38, .(x39, x40))) :|: TRUE f495_out -> f487_out(x41) :|: TRUE f487_in(x42) -> f495_in :|: TRUE f494_in(x43, x44, x45) -> f496_in(x43, x44) :|: TRUE f496_out(x46, x47) -> f497_in(x47, x48) :|: TRUE f497_out(x49, x50) -> f494_out(x51, x49, x50) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (147) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (148) TRUE ---------------------------------------- (149) Obligation: Rules: f368_out(T55) -> f367_out(T55) :|: TRUE f367_in(x) -> f368_in(x) :|: TRUE f478_in(T79) -> f367_in(T79) :|: TRUE f367_out(x1) -> f478_out(x1) :|: TRUE f368_in(x2) -> f370_in(x2) :|: TRUE f369_out(x3) -> f368_out(x3) :|: TRUE f370_out(x4) -> f368_out(x4) :|: TRUE f368_in(x5) -> f369_in(x5) :|: TRUE f370_in(x6) -> f479_in :|: TRUE f479_out -> f370_out(x7) :|: TRUE f370_in(x8) -> f478_in(x8) :|: TRUE f478_out(x9) -> f370_out(x9) :|: TRUE f2_in(T2) -> f6_in(T2) :|: TRUE f6_out(x10) -> f2_out(x10) :|: TRUE f28_out(T9) -> f6_out(T9) :|: TRUE f6_in(x11) -> f28_in(x11) :|: TRUE f28_in(x12) -> f48_in(x12) :|: TRUE f49_out(x13) -> f28_out(x13) :|: TRUE f48_out(x14) -> f49_in(x14) :|: TRUE f48_in(x15) -> f50_in(x15) :|: TRUE f50_out(x16) -> f48_out(x16) :|: TRUE f346_out(x17) -> f50_out(x17) :|: TRUE f343_out(x18) -> f50_out(x18) :|: TRUE f50_in(x19) -> f346_in(x19) :|: TRUE f50_in(x20) -> f343_in(x20) :|: TRUE f353_out -> f346_out(x21) :|: TRUE f346_in(x22) -> f353_in :|: TRUE f346_in(.(T21, .(T22, []))) -> f352_in(T21, T22) :|: TRUE f352_out(x23, x24) -> f346_out(.(x23, .(x24, []))) :|: TRUE f352_in(x25, x26) -> f357_in(x25) :|: TRUE f357_out(x27) -> f358_in(x28) :|: TRUE f358_out(x29) -> f352_out(x30, x29) :|: TRUE f359_out(x31) -> f357_out(x31) :|: TRUE f357_in(x32) -> f359_in(x32) :|: TRUE f359_in(x33) -> f362_in(x33) :|: TRUE f361_out(x34) -> f359_out(x34) :|: TRUE f362_out(x35) -> f359_out(x35) :|: TRUE f359_in(x36) -> f361_in(x36) :|: TRUE f367_out(x37) -> f362_out(x37) :|: TRUE f362_in(x38) -> f367_in(x38) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (150) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f367_in(x) -> f368_in(x) :|: TRUE f478_in(T79) -> f367_in(T79) :|: TRUE f368_in(x2) -> f370_in(x2) :|: TRUE f370_in(x8) -> f478_in(x8) :|: TRUE ---------------------------------------- (151) Obligation: Rules: f367_in(x) -> f368_in(x) :|: TRUE f478_in(T79) -> f367_in(T79) :|: TRUE f368_in(x2) -> f370_in(x2) :|: TRUE f370_in(x8) -> f478_in(x8) :|: TRUE ---------------------------------------- (152) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (153) Obligation: Rules: f478_in(T79:0) -> f478_in(T79:0) :|: TRUE ---------------------------------------- (154) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (155) Obligation: Rules: f478_in(T79:0) -> f478_in(T79:0) :|: TRUE ---------------------------------------- (156) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f478_in(T79:0) -> f478_in(T79:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (157) Obligation: Termination digraph: Nodes: (1) f478_in(T79:0) -> f478_in(T79:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (158) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f478_in(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (159) Obligation: Rules: f478_in(T79:0) -> f478_in(T79:0) :|: TRUE ---------------------------------------- (160) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, T79:0) -> f(1, T79:0) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1, -8) ---------------------------------------- (161) NO ---------------------------------------- (162) Obligation: Rules: f500_out(T98, T99) -> f498_out(T98, T99) :|: TRUE f498_in(x, x1) -> f499_in(x, x1) :|: TRUE f498_in(x2, x3) -> f500_in(x2, x3) :|: TRUE f499_out(x4, x5) -> f498_out(x4, x5) :|: TRUE f487_out(T9) -> f482_out(T9) :|: TRUE f486_out(x6) -> f482_out(x6) :|: TRUE f482_in(x7) -> f487_in(x7) :|: TRUE f482_in(x8) -> f486_in(x8) :|: TRUE f49_out(.(x9, x10)) -> f497_out(x9, x10) :|: TRUE f497_in(x11, x12) -> f49_in(.(x11, x12)) :|: TRUE f499_in(x13, x14) -> f518_in :|: TRUE f501_out(T113, T114) -> f499_out(s(T113), s(T114)) :|: TRUE f499_in(s(x15), s(x16)) -> f501_in(x15, x16) :|: TRUE f518_out -> f499_out(x17, x18) :|: TRUE f524_in -> f524_out :|: TRUE f494_in(x19, x20, x21) -> f496_in(x19, x20) :|: TRUE f496_out(x22, x23) -> f497_in(x23, x24) :|: TRUE f497_out(x25, x26) -> f494_out(x27, x25, x26) :|: TRUE f525_out -> f520_out(x28, x29) :|: TRUE f520_in(0, 0) -> f524_in :|: TRUE f520_in(x30, x31) -> f525_in :|: TRUE f524_out -> f520_out(0, 0) :|: TRUE f521_in -> f521_out :|: TRUE f487_in(.(x32, .(x33, x34))) -> f494_in(x32, x33, x34) :|: TRUE f494_out(x35, x36, x37) -> f487_out(.(x35, .(x36, x37))) :|: TRUE f495_out -> f487_out(x38) :|: TRUE f487_in(x39) -> f495_in :|: TRUE f500_in(x40, x41) -> f519_in(x40, x41) :|: TRUE f519_out(x42, x43) -> f500_out(x42, x43) :|: TRUE f520_out(x44, x45) -> f500_out(x44, x45) :|: TRUE f500_in(x46, x47) -> f520_in(x46, x47) :|: TRUE f480_in(x48) -> f481_in(x48) :|: TRUE f480_in(x49) -> f482_in(x49) :|: TRUE f481_out(x50) -> f480_out(x50) :|: TRUE f482_out(x51) -> f480_out(x51) :|: TRUE f498_out(x52, x53) -> f496_out(x52, x53) :|: TRUE f496_in(x54, x55) -> f498_in(x54, x55) :|: TRUE f501_in(x56, x57) -> f496_in(x56, x57) :|: TRUE f496_out(x58, x59) -> f501_out(x58, x59) :|: TRUE f49_in(x60) -> f480_in(x60) :|: TRUE f480_out(x61) -> f49_out(x61) :|: TRUE f519_in(0, s(T121)) -> f521_in :|: TRUE f521_out -> f519_out(0, s(x62)) :|: TRUE f519_in(x63, x64) -> f522_in :|: TRUE f522_out -> f519_out(x65, x66) :|: TRUE f2_in(T2) -> f6_in(T2) :|: TRUE f6_out(x67) -> f2_out(x67) :|: TRUE f28_out(x68) -> f6_out(x68) :|: TRUE f6_in(x69) -> f28_in(x69) :|: TRUE f28_in(x70) -> f48_in(x70) :|: TRUE f49_out(x71) -> f28_out(x71) :|: TRUE f48_out(x72) -> f49_in(x72) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (163) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (164) TRUE ---------------------------------------- (165) Obligation: Rules: f48_out(T22) -> f358_out(T22) :|: TRUE f358_in(x) -> f48_in(x) :|: TRUE f368_out(T55) -> f367_out(T55) :|: TRUE f367_in(x1) -> f368_in(x1) :|: TRUE f353_out -> f346_out(T9) :|: TRUE f346_in(x2) -> f353_in :|: TRUE f346_in(.(x3, .(x4, []))) -> f352_in(x3, x4) :|: TRUE f352_out(x5, x6) -> f346_out(.(x5, .(x6, []))) :|: TRUE f364_out -> f361_out(T42) :|: TRUE f361_in(T21) -> f365_in :|: TRUE f361_in(x7) -> f364_in :|: TRUE f365_out -> f361_out(x8) :|: TRUE f346_out(x9) -> f50_out(x9) :|: TRUE f343_out(x10) -> f50_out(x10) :|: TRUE f50_in(x11) -> f346_in(x11) :|: TRUE f50_in(x12) -> f343_in(x12) :|: TRUE f367_out(x13) -> f362_out(x13) :|: TRUE f362_in(x14) -> f367_in(x14) :|: TRUE f475_out -> f369_out(T71) :|: TRUE f369_in(x15) -> f476_in :|: TRUE f369_in(x16) -> f475_in :|: TRUE f476_out -> f369_out(x17) :|: TRUE f352_in(x18, x19) -> f357_in(x18) :|: TRUE f357_out(x20) -> f358_in(x21) :|: TRUE f358_out(x22) -> f352_out(x23, x22) :|: TRUE f359_in(x24) -> f362_in(x24) :|: TRUE f361_out(x25) -> f359_out(x25) :|: TRUE f362_out(x26) -> f359_out(x26) :|: TRUE f359_in(x27) -> f361_in(x27) :|: TRUE f48_in(x28) -> f50_in(x28) :|: TRUE f50_out(x29) -> f48_out(x29) :|: TRUE f478_in(T79) -> f367_in(T79) :|: TRUE f367_out(x30) -> f478_out(x30) :|: TRUE f359_out(x31) -> f357_out(x31) :|: TRUE f357_in(x32) -> f359_in(x32) :|: TRUE f368_in(x33) -> f370_in(x33) :|: TRUE f369_out(x34) -> f368_out(x34) :|: TRUE f370_out(x35) -> f368_out(x35) :|: TRUE f368_in(x36) -> f369_in(x36) :|: TRUE f370_in(x37) -> f479_in :|: TRUE f479_out -> f370_out(x38) :|: TRUE f370_in(x39) -> f478_in(x39) :|: TRUE f478_out(x40) -> f370_out(x40) :|: TRUE f364_in -> f364_out :|: TRUE f475_in -> f475_out :|: TRUE f2_in(T2) -> f6_in(T2) :|: TRUE f6_out(x41) -> f2_out(x41) :|: TRUE f28_out(x42) -> f6_out(x42) :|: TRUE f6_in(x43) -> f28_in(x43) :|: TRUE f28_in(x44) -> f48_in(x44) :|: TRUE f49_out(x45) -> f28_out(x45) :|: TRUE f48_out(x46) -> f49_in(x46) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (166) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f358_in(x) -> f48_in(x) :|: TRUE f368_out(T55) -> f367_out(T55) :|: TRUE f367_in(x1) -> f368_in(x1) :|: TRUE f346_in(.(x3, .(x4, []))) -> f352_in(x3, x4) :|: TRUE f364_out -> f361_out(T42) :|: TRUE f361_in(x7) -> f364_in :|: TRUE f50_in(x11) -> f346_in(x11) :|: TRUE f367_out(x13) -> f362_out(x13) :|: TRUE f362_in(x14) -> f367_in(x14) :|: TRUE f475_out -> f369_out(T71) :|: TRUE f369_in(x16) -> f475_in :|: TRUE f352_in(x18, x19) -> f357_in(x18) :|: TRUE f357_out(x20) -> f358_in(x21) :|: TRUE f359_in(x24) -> f362_in(x24) :|: TRUE f361_out(x25) -> f359_out(x25) :|: TRUE f362_out(x26) -> f359_out(x26) :|: TRUE f359_in(x27) -> f361_in(x27) :|: TRUE f48_in(x28) -> f50_in(x28) :|: TRUE f478_in(T79) -> f367_in(T79) :|: TRUE f367_out(x30) -> f478_out(x30) :|: TRUE f359_out(x31) -> f357_out(x31) :|: TRUE f357_in(x32) -> f359_in(x32) :|: TRUE f368_in(x33) -> f370_in(x33) :|: TRUE f369_out(x34) -> f368_out(x34) :|: TRUE f370_out(x35) -> f368_out(x35) :|: TRUE f368_in(x36) -> f369_in(x36) :|: TRUE f370_in(x39) -> f478_in(x39) :|: TRUE f478_out(x40) -> f370_out(x40) :|: TRUE f364_in -> f364_out :|: TRUE f475_in -> f475_out :|: TRUE ---------------------------------------- (167) Obligation: Rules: f358_in(x) -> f48_in(x) :|: TRUE f368_out(T55) -> f367_out(T55) :|: TRUE f367_in(x1) -> f368_in(x1) :|: TRUE f346_in(.(x3, .(x4, []))) -> f352_in(x3, x4) :|: TRUE f364_out -> f361_out(T42) :|: TRUE f361_in(x7) -> f364_in :|: TRUE f50_in(x11) -> f346_in(x11) :|: TRUE f367_out(x13) -> f362_out(x13) :|: TRUE f362_in(x14) -> f367_in(x14) :|: TRUE f475_out -> f369_out(T71) :|: TRUE f369_in(x16) -> f475_in :|: TRUE f352_in(x18, x19) -> f357_in(x18) :|: TRUE f357_out(x20) -> f358_in(x21) :|: TRUE f359_in(x24) -> f362_in(x24) :|: TRUE f361_out(x25) -> f359_out(x25) :|: TRUE f362_out(x26) -> f359_out(x26) :|: TRUE f359_in(x27) -> f361_in(x27) :|: TRUE f48_in(x28) -> f50_in(x28) :|: TRUE f478_in(T79) -> f367_in(T79) :|: TRUE f367_out(x30) -> f478_out(x30) :|: TRUE f359_out(x31) -> f357_out(x31) :|: TRUE f357_in(x32) -> f359_in(x32) :|: TRUE f368_in(x33) -> f370_in(x33) :|: TRUE f369_out(x34) -> f368_out(x34) :|: TRUE f370_out(x35) -> f368_out(x35) :|: TRUE f368_in(x36) -> f369_in(x36) :|: TRUE f370_in(x39) -> f478_in(x39) :|: TRUE f478_out(x40) -> f370_out(x40) :|: TRUE f364_in -> f364_out :|: TRUE f475_in -> f475_out :|: TRUE ---------------------------------------- (168) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (169) Obligation: Rules: f359_in(x24:0) -> f367_in(x24:0) :|: TRUE f368_out(T55:0) -> f359_in(x3:0) :|: TRUE f359_in(x) -> f359_in(x1) :|: TRUE f368_out(x2) -> f368_out(x2) :|: TRUE f367_in(x1:0) -> f367_in(x1:0) :|: TRUE f367_in(x3) -> f368_out(x4) :|: TRUE ---------------------------------------- (170) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (171) Obligation: Rules: f359_in(x24:0) -> f367_in(x24:0) :|: TRUE f368_out(T55:0) -> f359_in(x3:0) :|: TRUE f359_in(x) -> f359_in(x1) :|: TRUE f368_out(x2) -> f368_out(x2) :|: TRUE f367_in(x1:0) -> f367_in(x1:0) :|: TRUE f367_in(x3) -> f368_out(x4) :|: TRUE