/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern slowsort(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) UsableRulesReductionPairsProof [EQUIVALENT, 24 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) TRUE (23) PiDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) PiDP (26) PiDPToQDPProof [SOUND, 0 ms] (27) QDP (28) NonTerminationLoopProof [COMPLETE, 0 ms] (29) NO (30) PiDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) PiDP (33) PiDPToQDPProof [SOUND, 0 ms] (34) QDP (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] (36) YES (37) PrologToPiTRSProof [SOUND, 0 ms] (38) PiTRS (39) DependencyPairsProof [EQUIVALENT, 0 ms] (40) PiDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) AND (43) PiDP (44) UsableRulesProof [EQUIVALENT, 0 ms] (45) PiDP (46) PiDPToQDPProof [EQUIVALENT, 0 ms] (47) QDP (48) QDPSizeChangeProof [EQUIVALENT, 0 ms] (49) YES (50) PiDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) PiDP (53) PiDPToQDPProof [EQUIVALENT, 0 ms] (54) QDP (55) MRRProof [EQUIVALENT, 22 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) PrologToDTProblemTransformerProof [SOUND, 0 ms] (74) TRIPLES (75) TriplesToPiDPProof [SOUND, 0 ms] (76) PiDP (77) DependencyGraphProof [EQUIVALENT, 0 ms] (78) AND (79) PiDP (80) UsableRulesProof [EQUIVALENT, 0 ms] (81) PiDP (82) PiDPToQDPProof [EQUIVALENT, 0 ms] (83) QDP (84) QDPSizeChangeProof [EQUIVALENT, 0 ms] (85) YES (86) PiDP (87) UsableRulesProof [EQUIVALENT, 0 ms] (88) PiDP (89) PiDPToQDPProof [SOUND, 0 ms] (90) QDP (91) NonTerminationLoopProof [COMPLETE, 0 ms] (92) NO (93) PiDP (94) UsableRulesProof [EQUIVALENT, 0 ms] (95) PiDP (96) PiDPToQDPProof [SOUND, 0 ms] (97) QDP (98) QDPSizeChangeProof [EQUIVALENT, 0 ms] (99) YES (100) PrologToTRSTransformerProof [SOUND, 45 ms] (101) QTRS (102) DependencyPairsProof [EQUIVALENT, 0 ms] (103) QDP (104) DependencyGraphProof [EQUIVALENT, 0 ms] (105) AND (106) QDP (107) MNOCProof [EQUIVALENT, 0 ms] (108) QDP (109) UsableRulesProof [EQUIVALENT, 0 ms] (110) QDP (111) QReductionProof [EQUIVALENT, 0 ms] (112) QDP (113) QDPSizeChangeProof [EQUIVALENT, 0 ms] (114) YES (115) QDP (116) MNOCProof [EQUIVALENT, 0 ms] (117) QDP (118) UsableRulesProof [EQUIVALENT, 0 ms] (119) QDP (120) QReductionProof [EQUIVALENT, 1 ms] (121) QDP (122) QDPOrderProof [EQUIVALENT, 6 ms] (123) QDP (124) DependencyGraphProof [EQUIVALENT, 0 ms] (125) TRUE (126) QDP (127) MNOCProof [EQUIVALENT, 0 ms] (128) QDP (129) UsableRulesProof [EQUIVALENT, 0 ms] (130) QDP (131) QReductionProof [EQUIVALENT, 1 ms] (132) QDP (133) NonTerminationLoopProof [COMPLETE, 0 ms] (134) NO (135) QDP (136) MNOCProof [EQUIVALENT, 0 ms] (137) QDP (138) UsableRulesProof [EQUIVALENT, 0 ms] (139) QDP (140) QReductionProof [EQUIVALENT, 0 ms] (141) QDP (142) QDPSizeChangeProof [EQUIVALENT, 0 ms] (143) YES (144) PrologToIRSwTTransformerProof [SOUND, 42 ms] (145) AND (146) IRSwT (147) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (148) TRUE (149) IRSwT (150) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (151) IRSwT (152) IntTRSCompressionProof [EQUIVALENT, 24 ms] (153) IRSwT (154) IRSFormatTransformerProof [EQUIVALENT, 2 ms] (155) IRSwT (156) IRSwTTerminationDigraphProof [EQUIVALENT, 7 ms] (157) IRSwT (158) FilterProof [EQUIVALENT, 0 ms] (159) IntTRS (160) IntTRSPeriodicNontermProof [COMPLETE, 6 ms] (161) NO (162) IRSwT (163) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (164) TRUE (165) IRSwT (166) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (167) IRSwT (168) IntTRSCompressionProof [EQUIVALENT, 12 ms] (169) IRSwT (170) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (171) IRSwT (172) IRSwTTerminationDigraphProof [EQUIVALENT, 12 ms] (173) IRSwT (174) FilterProof [EQUIVALENT, 0 ms] (175) IntTRS ---------------------------------------- (0) Obligation: Clauses: slowsort(X, Y) :- ','(perm(X, Y), sorted(Y)). sorted([]). sorted(.(X, [])). sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z))). perm([], []). perm(.(X, .(Y, [])), .(U, .(V, []))) :- ','(delete(U, .(X, Y), Z), perm(Z, V)). delete(X, .(X, Y), Y). delete(X, .(Y, Z), W) :- delete(X, Z, W). le(s(X), s(Y)) :- le(X, Y). le(0, s(X)). le(0, 0). Query: slowsort(a,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: slowsort_in_2: (f,b) perm_in_2: (f,b) delete_in_3: (b,f,f) sorted_in_1: (b) le_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: SLOWSORT_IN_AG(X, Y) -> U1_AG(X, Y, perm_in_ag(X, Y)) SLOWSORT_IN_AG(X, Y) -> PERM_IN_AG(X, Y) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_GAA(U, .(X, Y), Z) DELETE_IN_GAA(X, .(Y, Z), W) -> U7_GAA(X, Y, Z, W, delete_in_gaa(X, Z, W)) DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_AG(X, Y, U, V, perm_in_ag(Z, V)) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) U1_AG(X, Y, perm_out_ag(X, Y)) -> U2_AG(X, Y, sorted_in_g(Y)) U1_AG(X, Y, perm_out_ag(X, Y)) -> SORTED_IN_G(Y) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z))) U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag SLOWSORT_IN_AG(x1, x2) = SLOWSORT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) U7_GAA(x1, x2, x3, x4, x5) = U7_GAA(x5) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x5) U2_AG(x1, x2, x3) = U2_AG(x3) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, x3, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x3) U4_G(x1, x2, x3, x4) = U4_G(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: SLOWSORT_IN_AG(X, Y) -> U1_AG(X, Y, perm_in_ag(X, Y)) SLOWSORT_IN_AG(X, Y) -> PERM_IN_AG(X, Y) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_GAA(U, .(X, Y), Z) DELETE_IN_GAA(X, .(Y, Z), W) -> U7_GAA(X, Y, Z, W, delete_in_gaa(X, Z, W)) DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_AG(X, Y, U, V, perm_in_ag(Z, V)) U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) U1_AG(X, Y, perm_out_ag(X, Y)) -> U2_AG(X, Y, sorted_in_g(Y)) U1_AG(X, Y, perm_out_ag(X, Y)) -> SORTED_IN_G(Y) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z))) U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag SLOWSORT_IN_AG(x1, x2) = SLOWSORT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) U7_GAA(x1, x2, x3, x4, x5) = U7_GAA(x5) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x5) U2_AG(x1, x2, x3) = U2_AG(x3) SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, x3, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x3) U4_G(x1, x2, x3, x4) = U4_G(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg SORTED_IN_G(x1) = SORTED_IN_G(x1) U3_G(x1, x2, x3, x4) = U3_G(x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U3_G(Y, Z, le_out_gg) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: le_in_gg(s(X), s(Y)) -> U8_gg(le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg U8_gg(le_out_gg) -> le_out_gg The set Q consists of the following terms: le_in_gg(x0, x1) U8_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: le_in_gg(s(X), s(Y)) -> U8_gg(le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + 2*x_2 POL(0) = 0 POL(SORTED_IN_G(x_1)) = x_1 POL(U3_G(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U8_gg(x_1)) = 2*x_1 POL(le_in_gg(x_1, x_2)) = x_1 + x_2 POL(le_out_gg) = 0 POL(s(x_1)) = 2 + 2*x_1 ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U3_G(Y, Z, le_out_gg) -> SORTED_IN_G(.(Y, Z)) SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(Y, Z, le_in_gg(X, Y)) The TRS R consists of the following rules: U8_gg(le_out_gg) -> le_out_gg The set Q consists of the following terms: le_in_gg(x0, x1) U8_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (22) TRUE ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X, .(Y, Z), W) -> DELETE_IN_GAA(X, Z, W) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) DELETE_IN_GAA(x1, x2, x3) = DELETE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: DELETE_IN_GAA(X) -> DELETE_IN_GAA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = DELETE_IN_GAA(X) evaluates to t =DELETE_IN_GAA(X) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from DELETE_IN_GAA(X) to DELETE_IN_GAA(X). ---------------------------------------- (29) NO ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) The TRS R consists of the following rules: slowsort_in_ag(X, Y) -> U1_ag(X, Y, perm_in_ag(X, Y)) perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ag(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) U5_ag(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> U6_ag(X, Y, U, V, perm_in_ag(Z, V)) U6_ag(X, Y, U, V, perm_out_ag(Z, V)) -> perm_out_ag(.(X, .(Y, [])), .(U, .(V, []))) U1_ag(X, Y, perm_out_ag(X, Y)) -> U2_ag(X, Y, sorted_in_g(Y)) sorted_in_g([]) -> sorted_out_g([]) sorted_in_g(.(X, [])) -> sorted_out_g(.(X, [])) sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(X)) -> le_out_gg(0, s(X)) le_in_gg(0, 0) -> le_out_gg(0, 0) U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z))) U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z))) U2_ag(X, Y, sorted_out_g(Y)) -> slowsort_out_ag(X, Y) The argument filtering Pi contains the following mapping: slowsort_in_ag(x1, x2) = slowsort_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x1, x2) U5_ag(x1, x2, x3, x4, x5) = U5_ag(x4, x5) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) U6_ag(x1, x2, x3, x4, x5) = U6_ag(x5) U2_ag(x1, x2, x3) = U2_ag(x3) sorted_in_g(x1) = sorted_in_g(x1) sorted_out_g(x1) = sorted_out_g U3_g(x1, x2, x3, x4) = U3_g(x2, x3, x4) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U8_gg(x1, x2, x3) = U8_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg U4_g(x1, x2, x3, x4) = U4_g(x4) slowsort_out_ag(x1, x2) = slowsort_out_ag PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AG(X, Y, U, V, delete_out_gaa(U, .(X, Y), Z)) -> PERM_IN_AG(Z, V) PERM_IN_AG(.(X, .(Y, [])), .(U, .(V, []))) -> U5_AG(X, Y, U, V, delete_in_gaa(U, .(X, Y), Z)) The TRS R consists of the following rules: delete_in_gaa(X, .(X, Y), Y) -> delete_out_gaa(X, .(X, Y), Y) delete_in_gaa(X, .(Y, Z), W) -> U7_gaa(X, Y, Z, W, delete_in_gaa(X, Z, W)) U7_gaa(X, Y, Z, W, delete_out_gaa(X, Z, W)) -> delete_out_gaa(X, .(Y, Z), W) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) delete_in_gaa(x1, x2, x3) = delete_in_gaa(x1) delete_out_gaa(x1, x2, x3) = delete_out_gaa U7_gaa(x1, x2, x3, x4, x5) = U7_gaa(x5) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) 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(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. ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (53) PiDPToQDPProof (EQUIVALENT) 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(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. ---------------------------------------- (55) 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 ---------------------------------------- (56) 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. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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. ---------------------------------------- (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(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 ---------------------------------------- (72) YES ---------------------------------------- (73) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 5, "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": { "45": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "152": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T18 (. T19 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "110": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T76 T79 X88)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T76"], "free": ["X88"], "exprvars": [] } }, "111": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "510": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "478": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "511": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "479": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "514": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "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": [] } }, "11": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": 5, "scope": 2, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "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": [] } }, "18": { "goal": [{ "clause": 1, "scope": 3, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [ { "clause": 2, "scope": 3, "term": "(sorted ([]))" }, { "clause": 3, "scope": 3, "term": "(sorted ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "480": { "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": [] } }, "481": { "goal": [{ "clause": 8, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "482": { "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": [] } }, "241": { "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": [] } }, "483": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T128 T129)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T129" ], "free": [], "exprvars": [] } }, "242": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "484": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "485": { "goal": [{ "clause": 9, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "244": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T94 (. T96 T97) X106)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": ["X106"], "exprvars": [] } }, "486": { "goal": [{ "clause": 10, "scope": 8, "term": "(le T114 T115)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "245": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T102 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T95"], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "489": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "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": [] } }, "248": { "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": [] } }, "249": { "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": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T7 T6) (sorted T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "22": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "25": { "goal": [{ "clause": 3, "scope": 3, "term": "(sorted ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "69": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "29": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "491": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "250": { "goal": [{ "clause": 3, "scope": 7, "term": "(sorted (. T18 (. T19 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "492": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "176": { "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": [] } }, "496": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "497": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "498": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "213": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "70": { "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": [] } }, "30": { "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": [] } }, "31": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T26 T19) (sorted (. T18 (. T19 ([])))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "39": { "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": [] } }, "184": { "goal": [{ "clause": 4, "scope": 6, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T114 T115) (sorted (. T115 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T114", "T115" ], "free": [], "exprvars": [] } }, "188": { "goal": [{ "clause": 5, "scope": 6, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": 6, "scope": 5, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "148": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T26 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "105": { "goal": [{ "clause": 7, "scope": 5, "term": "(delete T52 T55 X59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T52"], "free": ["X59"], "exprvars": [] } }, "106": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "107": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "108": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "504": { "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": [] } }, "505": { "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": [] } }, "506": { "goal": [{ "clause": 2, "scope": 9, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "507": { "goal": [{ "clause": 3, "scope": 9, "term": "(sorted (. T115 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T115"], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T18 (. T20 T21) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": ["X22"], "exprvars": [] } }, "43": { "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": 5, "to": 6, "label": "CASE" }, { "from": 6, "to": 9, "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": 9, "to": 10, "label": "CASE" }, { "from": 10, "to": 11, "label": "PARALLEL" }, { "from": 10, "to": 12, "label": "PARALLEL" }, { "from": 11, "to": 13, "label": "EVAL with clause\nperm([], []).\nand substitutionT7 -> [],\nT6 -> []" }, { "from": 11, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 30, "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": 12, "to": 31, "label": "EVAL-BACKTRACK" }, { "from": 13, "to": 17, "label": "CASE" }, { "from": 17, "to": 18, "label": "PARALLEL" }, { "from": 17, "to": 19, "label": "PARALLEL" }, { "from": 18, "to": 20, "label": "ONLY EVAL with clause\nsorted([]).\nand substitution" }, { "from": 19, "to": 25, "label": "BACKTRACK\nfor clause: sorted(.(X, []))because of non-unification" }, { "from": 20, "to": 22, "label": "SUCCESS" }, { "from": 25, "to": 29, "label": "BACKTRACK\nfor clause: sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z)))because of non-unification" }, { "from": 30, "to": 36, "label": "SPLIT 1" }, { "from": 30, "to": 37, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nreplacements:X22 -> T26" }, { "from": 36, "to": 39, "label": "CASE" }, { "from": 37, "to": 148, "label": "SPLIT 1" }, { "from": 37, "to": 152, "label": "SPLIT 2\nnew knowledge:\nT19 is ground" }, { "from": 39, "to": 42, "label": "PARALLEL" }, { "from": 39, "to": 43, "label": "PARALLEL" }, { "from": 42, "to": 45, "label": "EVAL with clause\ndelete(X39, .(X39, X40), X40).\nand substitutionT18 -> T39,\nX39 -> T39,\nT20 -> T39,\nT21 -> T40,\nX40 -> T40,\nX22 -> T40" }, { "from": 42, "to": 47, "label": "EVAL-BACKTRACK" }, { "from": 43, "to": 69, "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": 45, "to": 48, "label": "SUCCESS" }, { "from": 69, "to": 70, "label": "CASE" }, { "from": 70, "to": 103, "label": "PARALLEL" }, { "from": 70, "to": 105, "label": "PARALLEL" }, { "from": 103, "to": 106, "label": "EVAL with clause\ndelete(X72, .(X72, X73), X73).\nand substitutionT52 -> T68,\nX72 -> T68,\nX73 -> T69,\nT55 -> .(T68, T69),\nX59 -> T69" }, { "from": 103, "to": 107, "label": "EVAL-BACKTRACK" }, { "from": 105, "to": 110, "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": 105, "to": 111, "label": "EVAL-BACKTRACK" }, { "from": 106, "to": 108, "label": "SUCCESS" }, { "from": 110, "to": 69, "label": "INSTANCE with matching:\nT52 -> T76\nT55 -> T79\nX59 -> X88" }, { "from": 148, "to": 176, "label": "CASE" }, { "from": 152, "to": 248, "label": "CASE" }, { "from": 176, "to": 184, "label": "PARALLEL" }, { "from": 176, "to": 188, "label": "PARALLEL" }, { "from": 184, "to": 207, "label": "EVAL with clause\nperm([], []).\nand substitutionT26 -> [],\nT19 -> []" }, { "from": 184, "to": 213, "label": "EVAL-BACKTRACK" }, { "from": 188, "to": 241, "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": 188, "to": 242, "label": "EVAL-BACKTRACK" }, { "from": 207, "to": 214, "label": "SUCCESS" }, { "from": 241, "to": 244, "label": "SPLIT 1" }, { "from": 241, "to": 245, "label": "SPLIT 2\nnew knowledge:\nT94 is ground\nreplacements:X106 -> T102" }, { "from": 244, "to": 36, "label": "INSTANCE with matching:\nT18 -> T94\nT20 -> T96\nT21 -> T97\nX22 -> X106" }, { "from": 245, "to": 148, "label": "INSTANCE with matching:\nT26 -> T102\nT19 -> T95" }, { "from": 248, "to": 249, "label": "BACKTRACK\nfor clause: sorted([])because of non-unification" }, { "from": 249, "to": 250, "label": "BACKTRACK\nfor clause: sorted(.(X, []))because of non-unification" }, { "from": 250, "to": 263, "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": 263, "to": 478, "label": "SPLIT 1" }, { "from": 263, "to": 479, "label": "SPLIT 2\nnew knowledge:\nT114 is ground\nT115 is ground" }, { "from": 478, "to": 480, "label": "CASE" }, { "from": 479, "to": 504, "label": "CASE" }, { "from": 480, "to": 481, "label": "PARALLEL" }, { "from": 480, "to": 482, "label": "PARALLEL" }, { "from": 481, "to": 483, "label": "EVAL with clause\nle(s(X139), s(X140)) :- le(X139, X140).\nand substitutionX139 -> T128,\nT114 -> s(T128),\nX140 -> T129,\nT115 -> s(T129)" }, { "from": 481, "to": 484, "label": "EVAL-BACKTRACK" }, { "from": 482, "to": 485, "label": "PARALLEL" }, { "from": 482, "to": 486, "label": "PARALLEL" }, { "from": 483, "to": 478, "label": "INSTANCE with matching:\nT114 -> T128\nT115 -> T129" }, { "from": 485, "to": 489, "label": "EVAL with clause\nle(0, s(X147)).\nand substitutionT114 -> 0,\nX147 -> T136,\nT115 -> s(T136)" }, { "from": 485, "to": 491, "label": "EVAL-BACKTRACK" }, { "from": 486, "to": 496, "label": "EVAL with clause\nle(0, 0).\nand substitutionT114 -> 0,\nT115 -> 0" }, { "from": 486, "to": 497, "label": "EVAL-BACKTRACK" }, { "from": 489, "to": 492, "label": "SUCCESS" }, { "from": 496, "to": 498, "label": "SUCCESS" }, { "from": 504, "to": 505, "label": "BACKTRACK\nfor clause: sorted([])because of non-unification" }, { "from": 505, "to": 506, "label": "PARALLEL" }, { "from": 505, "to": 507, "label": "PARALLEL" }, { "from": 506, "to": 510, "label": "ONLY EVAL with clause\nsorted(.(X152, [])).\nand substitutionT115 -> T141,\nX152 -> T141" }, { "from": 507, "to": 514, "label": "BACKTRACK\nfor clause: sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z)))because of non-unification" }, { "from": 510, "to": 511, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (74) 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) ---------------------------------------- (75) 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 ---------------------------------------- (76) 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 ---------------------------------------- (77) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 15 less nodes. ---------------------------------------- (78) Complex Obligation (AND) ---------------------------------------- (79) 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 ---------------------------------------- (80) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (81) 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 ---------------------------------------- (82) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (83) 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. ---------------------------------------- (84) 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 ---------------------------------------- (85) YES ---------------------------------------- (86) 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 ---------------------------------------- (87) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (88) 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 ---------------------------------------- (89) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (90) 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. ---------------------------------------- (91) 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). ---------------------------------------- (92) NO ---------------------------------------- (93) 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 ---------------------------------------- (94) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (95) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (96) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: 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. ---------------------------------------- (98) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *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 ---------------------------------------- (99) YES ---------------------------------------- (100) 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", "472": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "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": [] } }, "473": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "474": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "310": { "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": [] } }, "475": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "278": { "goal": [{ "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "311": { "goal": [{ "clause": 1, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "476": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "312": { "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": [] } }, "477": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "314": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "315": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "359": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "436": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "437": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T99 T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T100" ], "free": [], "exprvars": [] } }, "280": { "goal": [{ "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "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": [] } }, "441": { "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": [] } }, "2": { "goal": [{ "clause": 0, "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": [] } }, "442": { "goal": [{ "clause": 8, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "289": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "443": { "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": [] } }, "444": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "445": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "402": { "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": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T10 T9) (sorted T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "328": { "goal": [{ "clause": 2, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "408": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "331": { "goal": [{ "clause": 3, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "456": { "goal": [{ "clause": 9, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "457": { "goal": [{ "clause": 10, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "71": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "72": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "73": { "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": [] } }, "74": { "goal": [{ "clause": 4, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "75": { "goal": [{ "clause": 5, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "76": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "77": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "78": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "79": { "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": [] } }, "301": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "302": { "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": [] } }, "303": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "304": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "80": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "305": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "81": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "306": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "82": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T29 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } }, "307": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "308": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T79 T82 X86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T79"], "free": ["X86"], "exprvars": [] } }, "309": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 2, "label": "CASE" }, { "from": 2, "to": 7, "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": 7, "to": 71, "label": "SPLIT 1" }, { "from": 7, "to": 72, "label": "SPLIT 2\nnew knowledge:\nT9 is ground" }, { "from": 71, "to": 73, "label": "CASE" }, { "from": 72, "to": 310, "label": "CASE" }, { "from": 73, "to": 74, "label": "PARALLEL" }, { "from": 73, "to": 75, "label": "PARALLEL" }, { "from": 74, "to": 76, "label": "EVAL with clause\nperm([], []).\nand substitutionT10 -> [],\nT9 -> []" }, { "from": 74, "to": 77, "label": "EVAL-BACKTRACK" }, { "from": 75, "to": 79, "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": 75, "to": 80, "label": "EVAL-BACKTRACK" }, { "from": 76, "to": 78, "label": "SUCCESS" }, { "from": 79, "to": 81, "label": "SPLIT 1" }, { "from": 79, "to": 82, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nreplacements:X20 -> T29" }, { "from": 81, "to": 275, "label": "CASE" }, { "from": 82, "to": 71, "label": "INSTANCE with matching:\nT10 -> T29\nT9 -> T22" }, { "from": 275, "to": 278, "label": "PARALLEL" }, { "from": 275, "to": 280, "label": "PARALLEL" }, { "from": 278, "to": 286, "label": "EVAL with clause\ndelete(X37, .(X37, X38), X38).\nand substitutionT21 -> T42,\nX37 -> T42,\nT23 -> T42,\nT24 -> T43,\nX38 -> T43,\nX20 -> T43" }, { "from": 278, "to": 289, "label": "EVAL-BACKTRACK" }, { "from": 280, "to": 301, "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": 286, "to": 291, "label": "SUCCESS" }, { "from": 301, "to": 302, "label": "CASE" }, { "from": 302, "to": 303, "label": "PARALLEL" }, { "from": 302, "to": 304, "label": "PARALLEL" }, { "from": 303, "to": 305, "label": "EVAL with clause\ndelete(X70, .(X70, X71), X71).\nand substitutionT55 -> T71,\nX70 -> T71,\nX71 -> T72,\nT58 -> .(T71, T72),\nX57 -> T72" }, { "from": 303, "to": 306, "label": "EVAL-BACKTRACK" }, { "from": 304, "to": 308, "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": 304, "to": 309, "label": "EVAL-BACKTRACK" }, { "from": 305, "to": 307, "label": "SUCCESS" }, { "from": 308, "to": 301, "label": "INSTANCE with matching:\nT55 -> T79\nT58 -> T82\nX57 -> X86" }, { "from": 310, "to": 311, "label": "PARALLEL" }, { "from": 310, "to": 312, "label": "PARALLEL" }, { "from": 311, "to": 313, "label": "EVAL with clause\nsorted([]).\nand substitutionT9 -> []" }, { "from": 311, "to": 314, "label": "EVAL-BACKTRACK" }, { "from": 312, "to": 328, "label": "PARALLEL" }, { "from": 312, "to": 331, "label": "PARALLEL" }, { "from": 313, "to": 315, "label": "SUCCESS" }, { "from": 328, "to": 353, "label": "EVAL with clause\nsorted(.(X95, [])).\nand substitutionX95 -> T91,\nT9 -> .(T91, [])" }, { "from": 328, "to": 359, "label": "EVAL-BACKTRACK" }, { "from": 331, "to": 402, "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": 331, "to": 408, "label": "EVAL-BACKTRACK" }, { "from": 353, "to": 365, "label": "SUCCESS" }, { "from": 402, "to": 436, "label": "SPLIT 1" }, { "from": 402, "to": 437, "label": "SPLIT 2\nnew knowledge:\nT98 is ground\nT99 is ground" }, { "from": 436, "to": 441, "label": "CASE" }, { "from": 437, "to": 72, "label": "INSTANCE with matching:\nT9 -> .(T99, T100)" }, { "from": 441, "to": 442, "label": "PARALLEL" }, { "from": 441, "to": 443, "label": "PARALLEL" }, { "from": 442, "to": 444, "label": "EVAL with clause\nle(s(X117), s(X118)) :- le(X117, X118).\nand substitutionX117 -> T113,\nT98 -> s(T113),\nX118 -> T114,\nT99 -> s(T114)" }, { "from": 442, "to": 445, "label": "EVAL-BACKTRACK" }, { "from": 443, "to": 456, "label": "PARALLEL" }, { "from": 443, "to": 457, "label": "PARALLEL" }, { "from": 444, "to": 436, "label": "INSTANCE with matching:\nT98 -> T113\nT99 -> T114" }, { "from": 456, "to": 472, "label": "EVAL with clause\nle(0, s(X125)).\nand substitutionT98 -> 0,\nX125 -> T121,\nT99 -> s(T121)" }, { "from": 456, "to": 473, "label": "EVAL-BACKTRACK" }, { "from": 457, "to": 475, "label": "EVAL with clause\nle(0, 0).\nand substitutionT98 -> 0,\nT99 -> 0" }, { "from": 457, "to": 476, "label": "EVAL-BACKTRACK" }, { "from": 472, "to": 474, "label": "SUCCESS" }, { "from": 475, "to": 477, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (101) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 Q is empty. ---------------------------------------- (102) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T9) -> U1^1(f7_in(T9), T9) F1_IN(T9) -> F7_IN(T9) F71_IN(.(T21, .(T22, []))) -> U2^1(f79_in(T21, T22), .(T21, .(T22, []))) F71_IN(.(T21, .(T22, []))) -> F79_IN(T21, T22) F301_IN(T79) -> U3^1(f301_in(T79), T79) F301_IN(T79) -> F301_IN(T79) F72_IN(.(T98, .(T99, T100))) -> U4^1(f402_in(T98, T99, T100), .(T98, .(T99, T100))) F72_IN(.(T98, .(T99, T100))) -> F402_IN(T98, T99, T100) F436_IN(s(T113), s(T114)) -> U5^1(f436_in(T113, T114), s(T113), s(T114)) F436_IN(s(T113), s(T114)) -> F436_IN(T113, T114) F81_IN(T55) -> U6^1(f301_in(T55), T55) F81_IN(T55) -> F301_IN(T55) F7_IN(T9) -> U7^1(f71_in(T9), T9) F7_IN(T9) -> F71_IN(T9) U7^1(f71_out1, T9) -> U8^1(f72_in(T9), T9) U7^1(f71_out1, T9) -> F72_IN(T9) F79_IN(T21, T22) -> U9^1(f81_in(T21), T21, T22) F79_IN(T21, T22) -> F81_IN(T21) U9^1(f81_out1, T21, T22) -> U10^1(f71_in(T22), T21, T22) U9^1(f81_out1, T21, T22) -> F71_IN(T22) F402_IN(T98, T99, T100) -> U11^1(f436_in(T98, T99), T98, T99, T100) F402_IN(T98, T99, T100) -> F436_IN(T98, T99) U11^1(f436_out1, T98, T99, T100) -> U12^1(f72_in(.(T99, T100)), T98, T99, T100) U11^1(f436_out1, T98, T99, T100) -> F72_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (104) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 16 less nodes. ---------------------------------------- (105) Complex Obligation (AND) ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: F436_IN(s(T113), s(T114)) -> F436_IN(T113, T114) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (107) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: F436_IN(s(T113), s(T114)) -> F436_IN(T113, T114) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) 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. ---------------------------------------- (110) Obligation: Q DP problem: The TRS P consists of the following rules: F436_IN(s(T113), s(T114)) -> F436_IN(T113, T114) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (111) 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(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) ---------------------------------------- (112) Obligation: Q DP problem: The TRS P consists of the following rules: F436_IN(s(T113), s(T114)) -> F436_IN(T113, T114) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (113) 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: *F436_IN(s(T113), s(T114)) -> F436_IN(T113, T114) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (114) YES ---------------------------------------- (115) Obligation: Q DP problem: The TRS P consists of the following rules: F72_IN(.(T98, .(T99, T100))) -> F402_IN(T98, T99, T100) F402_IN(T98, T99, T100) -> U11^1(f436_in(T98, T99), T98, T99, T100) U11^1(f436_out1, T98, T99, T100) -> F72_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (116) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (117) Obligation: Q DP problem: The TRS P consists of the following rules: F72_IN(.(T98, .(T99, T100))) -> F402_IN(T98, T99, T100) F402_IN(T98, T99, T100) -> U11^1(f436_in(T98, T99), T98, T99, T100) U11^1(f436_out1, T98, T99, T100) -> F72_IN(.(T99, T100)) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (118) 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. ---------------------------------------- (119) Obligation: Q DP problem: The TRS P consists of the following rules: F72_IN(.(T98, .(T99, T100))) -> F402_IN(T98, T99, T100) F402_IN(T98, T99, T100) -> U11^1(f436_in(T98, T99), T98, T99, T100) U11^1(f436_out1, T98, T99, T100) -> F72_IN(.(T99, T100)) The TRS R consists of the following rules: f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 U5(f436_out1, s(T113), s(T114)) -> f436_out1 The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (120) 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(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) ---------------------------------------- (121) Obligation: Q DP problem: The TRS P consists of the following rules: F72_IN(.(T98, .(T99, T100))) -> F402_IN(T98, T99, T100) F402_IN(T98, T99, T100) -> U11^1(f436_in(T98, T99), T98, T99, T100) U11^1(f436_out1, T98, T99, T100) -> F72_IN(.(T99, T100)) The TRS R consists of the following rules: f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 U5(f436_out1, s(T113), s(T114)) -> f436_out1 The set Q consists of the following terms: f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (122) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U11^1(f436_out1, T98, T99, T100) -> F72_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( f436_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( f436_out1 ) = 2 POL( F72_IN_1(x_1) ) = x_1 + 2 POL( ._2(x_1, x_2) ) = 2x_1 + 2x_2 POL( F402_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: f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 U5(f436_out1, s(T113), s(T114)) -> f436_out1 ---------------------------------------- (123) Obligation: Q DP problem: The TRS P consists of the following rules: F72_IN(.(T98, .(T99, T100))) -> F402_IN(T98, T99, T100) F402_IN(T98, T99, T100) -> U11^1(f436_in(T98, T99), T98, T99, T100) The TRS R consists of the following rules: f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 U5(f436_out1, s(T113), s(T114)) -> f436_out1 The set Q consists of the following terms: f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (124) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (125) TRUE ---------------------------------------- (126) Obligation: Q DP problem: The TRS P consists of the following rules: F301_IN(T79) -> F301_IN(T79) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (127) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (128) Obligation: Q DP problem: The TRS P consists of the following rules: F301_IN(T79) -> F301_IN(T79) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (129) 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. ---------------------------------------- (130) Obligation: Q DP problem: The TRS P consists of the following rules: F301_IN(T79) -> F301_IN(T79) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (131) 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(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) ---------------------------------------- (132) Obligation: Q DP problem: The TRS P consists of the following rules: F301_IN(T79) -> F301_IN(T79) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (133) 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 = F301_IN(T79) evaluates to t =F301_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 F301_IN(T79) to F301_IN(T79). ---------------------------------------- (134) NO ---------------------------------------- (135) Obligation: Q DP problem: The TRS P consists of the following rules: F71_IN(.(T21, .(T22, []))) -> F79_IN(T21, T22) F79_IN(T21, T22) -> U9^1(f81_in(T21), T21, T22) U9^1(f81_out1, T21, T22) -> F71_IN(T22) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (136) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (137) Obligation: Q DP problem: The TRS P consists of the following rules: F71_IN(.(T21, .(T22, []))) -> F79_IN(T21, T22) F79_IN(T21, T22) -> U9^1(f81_in(T21), T21, T22) U9^1(f81_out1, T21, T22) -> F71_IN(T22) The TRS R consists of the following rules: f1_in(T9) -> U1(f7_in(T9), T9) U1(f7_out1, T9) -> f1_out1 f71_in([]) -> f71_out1 f71_in(.(T21, .(T22, []))) -> U2(f79_in(T21, T22), .(T21, .(T22, []))) U2(f79_out1, .(T21, .(T22, []))) -> f71_out1 f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U3(f301_out1, T79) -> f301_out1 f72_in([]) -> f72_out1 f72_in(.(T91, [])) -> f72_out1 f72_in(.(T98, .(T99, T100))) -> U4(f402_in(T98, T99, T100), .(T98, .(T99, T100))) U4(f402_out1, .(T98, .(T99, T100))) -> f72_out1 f436_in(s(T113), s(T114)) -> U5(f436_in(T113, T114), s(T113), s(T114)) U5(f436_out1, s(T113), s(T114)) -> f436_out1 f436_in(0, s(T121)) -> f436_out1 f436_in(0, 0) -> f436_out1 f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) U6(f301_out1, T55) -> f81_out1 f7_in(T9) -> U7(f71_in(T9), T9) U7(f71_out1, T9) -> U8(f72_in(T9), T9) U8(f72_out1, T9) -> f7_out1 f79_in(T21, T22) -> U9(f81_in(T21), T21, T22) U9(f81_out1, T21, T22) -> U10(f71_in(T22), T21, T22) U10(f71_out1, T21, T22) -> f79_out1 f402_in(T98, T99, T100) -> U11(f436_in(T98, T99), T98, T99, T100) U11(f436_out1, T98, T99, T100) -> U12(f72_in(.(T99, T100)), T98, T99, T100) U12(f72_out1, T98, T99, T100) -> f402_out1 The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (138) 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. ---------------------------------------- (139) Obligation: Q DP problem: The TRS P consists of the following rules: F71_IN(.(T21, .(T22, []))) -> F79_IN(T21, T22) F79_IN(T21, T22) -> U9^1(f81_in(T21), T21, T22) U9^1(f81_out1, T21, T22) -> F71_IN(T22) The TRS R consists of the following rules: f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U6(f301_out1, T55) -> f81_out1 U3(f301_out1, T79) -> f301_out1 The set Q consists of the following terms: f1_in(x0) U1(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f301_in(x0) U3(f301_out1, x0) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f81_in(x0) U6(f301_out1, x0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (140) 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(f7_out1, x0) f71_in([]) f71_in(.(x0, .(x1, []))) U2(f79_out1, .(x0, .(x1, []))) f72_in([]) f72_in(.(x0, [])) f72_in(.(x0, .(x1, x2))) U4(f402_out1, .(x0, .(x1, x2))) f436_in(s(x0), s(x1)) U5(f436_out1, s(x0), s(x1)) f436_in(0, s(x0)) f436_in(0, 0) f7_in(x0) U7(f71_out1, x0) U8(f72_out1, x0) f79_in(x0, x1) U9(f81_out1, x0, x1) U10(f71_out1, x0, x1) f402_in(x0, x1, x2) U11(f436_out1, x0, x1, x2) U12(f72_out1, x0, x1, x2) ---------------------------------------- (141) Obligation: Q DP problem: The TRS P consists of the following rules: F71_IN(.(T21, .(T22, []))) -> F79_IN(T21, T22) F79_IN(T21, T22) -> U9^1(f81_in(T21), T21, T22) U9^1(f81_out1, T21, T22) -> F71_IN(T22) The TRS R consists of the following rules: f81_in(T42) -> f81_out1 f81_in(T55) -> U6(f301_in(T55), T55) f301_in(T71) -> f301_out1 f301_in(T79) -> U3(f301_in(T79), T79) U6(f301_out1, T55) -> f81_out1 U3(f301_out1, T79) -> f301_out1 The set Q consists of the following terms: f301_in(x0) U3(f301_out1, x0) f81_in(x0) U6(f301_out1, x0) We have to consider all minimal (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: *F79_IN(T21, T22) -> U9^1(f81_in(T21), T21, T22) The graph contains the following edges 1 >= 2, 2 >= 3 *U9^1(f81_out1, T21, T22) -> F71_IN(T22) The graph contains the following edges 3 >= 1 *F71_IN(.(T21, .(T22, []))) -> F79_IN(T21, T22) 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": 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": { "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "46": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "112": { "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": [] } }, "113": { "goal": [{ "clause": 6, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "114": { "goal": [{ "clause": 7, "scope": 4, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "115": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "116": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "512": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "117": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "513": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted (. T99 T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T100" ], "free": [], "exprvars": [] } }, "118": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T79 T82 X86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T79"], "free": ["X86"], "exprvars": [] } }, "119": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "515": { "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": [] } }, "516": { "goal": [{ "clause": 8, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "517": { "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": [] } }, "518": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "519": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "487": { "goal": [ { "clause": 1, "scope": 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": [] } }, "520": { "goal": [{ "clause": 9, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(slowsort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "488": { "goal": [{ "clause": 1, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "521": { "goal": [{ "clause": 10, "scope": 6, "term": "(le T98 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T99" ], "free": [], "exprvars": [] } }, "522": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "523": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "524": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T10 T9) (sorted T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "525": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "526": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "527": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "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": [] } }, "23": { "goal": [{ "clause": 4, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "24": { "goal": [{ "clause": 5, "scope": 2, "term": "(perm T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "490": { "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": [] } }, "493": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "494": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "495": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "499": { "goal": [{ "clause": 2, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "32": { "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": [] } }, "33": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "34": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T29 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } }, "38": { "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": [] } }, "104": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "500": { "goal": [{ "clause": 3, "scope": 5, "term": "(sorted T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "501": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "502": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "503": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(delete T55 T58 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": ["X57"], "exprvars": [] } }, "40": { "goal": [{ "clause": 6, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "41": { "goal": [{ "clause": 7, "scope": 3, "term": "(delete T21 (. T23 T24) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X20"], "exprvars": [] } }, "508": { "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": [] } }, "509": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 8, "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": 8, "to": 15, "label": "SPLIT 1" }, { "from": 8, "to": 16, "label": "SPLIT 2\nnew knowledge:\nT9 is ground" }, { "from": 15, "to": 21, "label": "CASE" }, { "from": 16, "to": 487, "label": "CASE" }, { "from": 21, "to": 23, "label": "PARALLEL" }, { "from": 21, "to": 24, "label": "PARALLEL" }, { "from": 23, "to": 26, "label": "EVAL with clause\nperm([], []).\nand substitutionT10 -> [],\nT9 -> []" }, { "from": 23, "to": 27, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 32, "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": 24, "to": 33, "label": "EVAL-BACKTRACK" }, { "from": 26, "to": 28, "label": "SUCCESS" }, { "from": 32, "to": 34, "label": "SPLIT 1" }, { "from": 32, "to": 35, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nreplacements:X20 -> T29" }, { "from": 34, "to": 38, "label": "CASE" }, { "from": 35, "to": 15, "label": "INSTANCE with matching:\nT10 -> T29\nT9 -> T22" }, { "from": 38, "to": 40, "label": "PARALLEL" }, { "from": 38, "to": 41, "label": "PARALLEL" }, { "from": 40, "to": 44, "label": "EVAL with clause\ndelete(X37, .(X37, X38), X38).\nand substitutionT21 -> T42,\nX37 -> T42,\nT23 -> T42,\nT24 -> T43,\nX38 -> T43,\nX20 -> T43" }, { "from": 40, "to": 46, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 109, "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": 44, "to": 104, "label": "SUCCESS" }, { "from": 109, "to": 112, "label": "CASE" }, { "from": 112, "to": 113, "label": "PARALLEL" }, { "from": 112, "to": 114, "label": "PARALLEL" }, { "from": 113, "to": 115, "label": "EVAL with clause\ndelete(X70, .(X70, X71), X71).\nand substitutionT55 -> T71,\nX70 -> T71,\nX71 -> T72,\nT58 -> .(T71, T72),\nX57 -> T72" }, { "from": 113, "to": 116, "label": "EVAL-BACKTRACK" }, { "from": 114, "to": 118, "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": 114, "to": 119, "label": "EVAL-BACKTRACK" }, { "from": 115, "to": 117, "label": "SUCCESS" }, { "from": 118, "to": 109, "label": "INSTANCE with matching:\nT55 -> T79\nT58 -> T82\nX57 -> X86" }, { "from": 487, "to": 488, "label": "PARALLEL" }, { "from": 487, "to": 490, "label": "PARALLEL" }, { "from": 488, "to": 493, "label": "EVAL with clause\nsorted([]).\nand substitutionT9 -> []" }, { "from": 488, "to": 494, "label": "EVAL-BACKTRACK" }, { "from": 490, "to": 499, "label": "PARALLEL" }, { "from": 490, "to": 500, "label": "PARALLEL" }, { "from": 493, "to": 495, "label": "SUCCESS" }, { "from": 499, "to": 501, "label": "EVAL with clause\nsorted(.(X95, [])).\nand substitutionX95 -> T91,\nT9 -> .(T91, [])" }, { "from": 499, "to": 502, "label": "EVAL-BACKTRACK" }, { "from": 500, "to": 508, "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": 500, "to": 509, "label": "EVAL-BACKTRACK" }, { "from": 501, "to": 503, "label": "SUCCESS" }, { "from": 508, "to": 512, "label": "SPLIT 1" }, { "from": 508, "to": 513, "label": "SPLIT 2\nnew knowledge:\nT98 is ground\nT99 is ground" }, { "from": 512, "to": 515, "label": "CASE" }, { "from": 513, "to": 16, "label": "INSTANCE with matching:\nT9 -> .(T99, T100)" }, { "from": 515, "to": 516, "label": "PARALLEL" }, { "from": 515, "to": 517, "label": "PARALLEL" }, { "from": 516, "to": 518, "label": "EVAL with clause\nle(s(X117), s(X118)) :- le(X117, X118).\nand substitutionX117 -> T113,\nT98 -> s(T113),\nX118 -> T114,\nT99 -> s(T114)" }, { "from": 516, "to": 519, "label": "EVAL-BACKTRACK" }, { "from": 517, "to": 520, "label": "PARALLEL" }, { "from": 517, "to": 521, "label": "PARALLEL" }, { "from": 518, "to": 512, "label": "INSTANCE with matching:\nT98 -> T113\nT99 -> T114" }, { "from": 520, "to": 522, "label": "EVAL with clause\nle(0, s(X125)).\nand substitutionT98 -> 0,\nX125 -> T121,\nT99 -> s(T121)" }, { "from": 520, "to": 523, "label": "EVAL-BACKTRACK" }, { "from": 521, "to": 525, "label": "EVAL with clause\nle(0, 0).\nand substitutionT98 -> 0,\nT99 -> 0" }, { "from": 521, "to": 526, "label": "EVAL-BACKTRACK" }, { "from": 522, "to": 524, "label": "SUCCESS" }, { "from": 525, "to": 527, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (145) Complex Obligation (AND) ---------------------------------------- (146) Obligation: Rules: f518_out(T113, T114) -> f516_out(s(T113), s(T114)) :|: TRUE f516_in(T98, T99) -> f519_in :|: TRUE f516_in(s(x), s(x1)) -> f518_in(x, x1) :|: TRUE f519_out -> f516_out(x2, x3) :|: TRUE f512_in(x4, x5) -> f515_in(x4, x5) :|: TRUE f515_out(x6, x7) -> f512_out(x6, x7) :|: TRUE f516_out(x8, x9) -> f515_out(x8, x9) :|: TRUE f515_in(x10, x11) -> f517_in(x10, x11) :|: TRUE f517_out(x12, x13) -> f515_out(x12, x13) :|: TRUE f515_in(x14, x15) -> f516_in(x14, x15) :|: TRUE f512_out(x16, x17) -> f518_out(x16, x17) :|: TRUE f518_in(x18, x19) -> f512_in(x18, x19) :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x20) -> f4_in(x20) :|: TRUE f4_in(T9) -> f8_in(T9) :|: TRUE f8_out(x21) -> f4_out(x21) :|: TRUE f8_in(x22) -> f15_in(x22) :|: TRUE f16_out(x23) -> f8_out(x23) :|: TRUE f15_out(x24) -> f16_in(x24) :|: TRUE f16_in(x25) -> f487_in(x25) :|: TRUE f487_out(x26) -> f16_out(x26) :|: TRUE f488_out(x27) -> f487_out(x27) :|: TRUE f487_in(x28) -> f488_in(x28) :|: TRUE f490_out(x29) -> f487_out(x29) :|: TRUE f487_in(x30) -> f490_in(x30) :|: TRUE f499_out(x31) -> f490_out(x31) :|: TRUE f490_in(x32) -> f499_in(x32) :|: TRUE f490_in(x33) -> f500_in(x33) :|: TRUE f500_out(x34) -> f490_out(x34) :|: TRUE f500_in(.(x35, .(x36, x37))) -> f508_in(x35, x36, x37) :|: TRUE f500_in(x38) -> f509_in :|: TRUE f508_out(x39, x40, x41) -> f500_out(.(x39, .(x40, x41))) :|: TRUE f509_out -> f500_out(x42) :|: TRUE f508_in(x43, x44, x45) -> f512_in(x43, x44) :|: TRUE f512_out(x46, x47) -> f513_in(x47, x48) :|: TRUE f513_out(x49, x50) -> f508_out(x51, x49, x50) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (147) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (148) TRUE ---------------------------------------- (149) Obligation: Rules: f112_in(T55) -> f114_in(T55) :|: TRUE f113_out(x) -> f112_out(x) :|: TRUE f112_in(x1) -> f113_in(x1) :|: TRUE f114_out(x2) -> f112_out(x2) :|: TRUE f109_out(T79) -> f118_out(T79) :|: TRUE f118_in(x3) -> f109_in(x3) :|: TRUE f112_out(x4) -> f109_out(x4) :|: TRUE f109_in(x5) -> f112_in(x5) :|: TRUE f114_in(x6) -> f118_in(x6) :|: TRUE f114_in(x7) -> f119_in :|: TRUE f118_out(x8) -> f114_out(x8) :|: TRUE f119_out -> f114_out(x9) :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x10) -> f4_in(x10) :|: TRUE f4_in(T9) -> f8_in(T9) :|: TRUE f8_out(x11) -> f4_out(x11) :|: TRUE f8_in(x12) -> f15_in(x12) :|: TRUE f16_out(x13) -> f8_out(x13) :|: TRUE f15_out(x14) -> f16_in(x14) :|: TRUE f15_in(x15) -> f21_in(x15) :|: TRUE f21_out(x16) -> f15_out(x16) :|: TRUE f23_out(x17) -> f21_out(x17) :|: TRUE f24_out(x18) -> f21_out(x18) :|: TRUE f21_in(x19) -> f23_in(x19) :|: TRUE f21_in(x20) -> f24_in(x20) :|: TRUE f32_out(T21, T22) -> f24_out(.(T21, .(T22, []))) :|: TRUE f33_out -> f24_out(x21) :|: TRUE f24_in(.(x22, .(x23, []))) -> f32_in(x22, x23) :|: TRUE f24_in(x24) -> f33_in :|: TRUE f32_in(x25, x26) -> f34_in(x25) :|: TRUE f34_out(x27) -> f35_in(x28) :|: TRUE f35_out(x29) -> f32_out(x30, x29) :|: TRUE f38_out(x31) -> f34_out(x31) :|: TRUE f34_in(x32) -> f38_in(x32) :|: TRUE f40_out(x33) -> f38_out(x33) :|: TRUE f38_in(x34) -> f40_in(x34) :|: TRUE f41_out(x35) -> f38_out(x35) :|: TRUE f38_in(x36) -> f41_in(x36) :|: TRUE f109_out(x37) -> f41_out(x37) :|: TRUE f41_in(x38) -> f109_in(x38) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (150) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f112_in(T55) -> f114_in(T55) :|: TRUE f118_in(x3) -> f109_in(x3) :|: TRUE f109_in(x5) -> f112_in(x5) :|: TRUE f114_in(x6) -> f118_in(x6) :|: TRUE ---------------------------------------- (151) Obligation: Rules: f112_in(T55) -> f114_in(T55) :|: TRUE f118_in(x3) -> f109_in(x3) :|: TRUE f109_in(x5) -> f112_in(x5) :|: TRUE f114_in(x6) -> f118_in(x6) :|: TRUE ---------------------------------------- (152) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (153) Obligation: Rules: f118_in(x3:0) -> f118_in(x3:0) :|: TRUE ---------------------------------------- (154) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (155) Obligation: Rules: f118_in(x3:0) -> f118_in(x3:0) :|: TRUE ---------------------------------------- (156) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f118_in(x3:0) -> f118_in(x3:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (157) Obligation: Termination digraph: Nodes: (1) f118_in(x3:0) -> f118_in(x3:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (158) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f118_in(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (159) Obligation: Rules: f118_in(x3:0) -> f118_in(x3:0) :|: TRUE ---------------------------------------- (160) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, x3:0) -> f(1, x3:0) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1, -8) ---------------------------------------- (161) NO ---------------------------------------- (162) Obligation: Rules: f499_out(T9) -> f490_out(T9) :|: TRUE f490_in(x) -> f499_in(x) :|: TRUE f490_in(x1) -> f500_in(x1) :|: TRUE f500_out(x2) -> f490_out(x2) :|: TRUE f488_out(x3) -> f487_out(x3) :|: TRUE f487_in(x4) -> f488_in(x4) :|: TRUE f490_out(x5) -> f487_out(x5) :|: TRUE f487_in(x6) -> f490_in(x6) :|: TRUE f520_in(0, s(T121)) -> f522_in :|: TRUE f523_out -> f520_out(T98, T99) :|: TRUE f522_out -> f520_out(0, s(x7)) :|: TRUE f520_in(x8, x9) -> f523_in :|: TRUE f526_out -> f521_out(x10, x11) :|: TRUE f521_in(x12, x13) -> f526_in :|: TRUE f525_out -> f521_out(0, 0) :|: TRUE f521_in(0, 0) -> f525_in :|: TRUE f500_in(.(x14, .(x15, x16))) -> f508_in(x14, x15, x16) :|: TRUE f500_in(x17) -> f509_in :|: TRUE f508_out(x18, x19, x20) -> f500_out(.(x18, .(x19, x20))) :|: TRUE f509_out -> f500_out(x21) :|: TRUE f512_in(x22, x23) -> f515_in(x22, x23) :|: TRUE f515_out(x24, x25) -> f512_out(x24, x25) :|: TRUE f512_out(T113, T114) -> f518_out(T113, T114) :|: TRUE f518_in(x26, x27) -> f512_in(x26, x27) :|: TRUE f522_in -> f522_out :|: TRUE f525_in -> f525_out :|: TRUE f508_in(x28, x29, x30) -> f512_in(x28, x29) :|: TRUE f512_out(x31, x32) -> f513_in(x32, x33) :|: TRUE f513_out(x34, x35) -> f508_out(x36, x34, x35) :|: TRUE f518_out(x37, x38) -> f516_out(s(x37), s(x38)) :|: TRUE f516_in(x39, x40) -> f519_in :|: TRUE f516_in(s(x41), s(x42)) -> f518_in(x41, x42) :|: TRUE f519_out -> f516_out(x43, x44) :|: TRUE f16_out(.(x45, x46)) -> f513_out(x45, x46) :|: TRUE f513_in(x47, x48) -> f16_in(.(x47, x48)) :|: TRUE f516_out(x49, x50) -> f515_out(x49, x50) :|: TRUE f515_in(x51, x52) -> f517_in(x51, x52) :|: TRUE f517_out(x53, x54) -> f515_out(x53, x54) :|: TRUE f515_in(x55, x56) -> f516_in(x55, x56) :|: TRUE f16_in(x57) -> f487_in(x57) :|: TRUE f487_out(x58) -> f16_out(x58) :|: TRUE f517_in(x59, x60) -> f521_in(x59, x60) :|: TRUE f517_in(x61, x62) -> f520_in(x61, x62) :|: TRUE f521_out(x63, x64) -> f517_out(x63, x64) :|: TRUE f520_out(x65, x66) -> f517_out(x65, x66) :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x67) -> f4_in(x67) :|: TRUE f4_in(x68) -> f8_in(x68) :|: TRUE f8_out(x69) -> f4_out(x69) :|: TRUE f8_in(x70) -> f15_in(x70) :|: TRUE f16_out(x71) -> f8_out(x71) :|: TRUE f15_out(x72) -> f16_in(x72) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (163) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (164) TRUE ---------------------------------------- (165) Obligation: Rules: f23_out(T9) -> f21_out(T9) :|: TRUE f24_out(x) -> f21_out(x) :|: TRUE f21_in(x1) -> f23_in(x1) :|: TRUE f21_in(x2) -> f24_in(x2) :|: TRUE f112_in(T55) -> f114_in(T55) :|: TRUE f113_out(x3) -> f112_out(x3) :|: TRUE f112_in(x4) -> f113_in(x4) :|: TRUE f114_out(x5) -> f112_out(x5) :|: TRUE f32_in(T21, T22) -> f34_in(T21) :|: TRUE f34_out(x6) -> f35_in(x7) :|: TRUE f35_out(x8) -> f32_out(x9, x8) :|: TRUE f114_in(T79) -> f118_in(T79) :|: TRUE f114_in(x10) -> f119_in :|: TRUE f118_out(x11) -> f114_out(x11) :|: TRUE f119_out -> f114_out(x12) :|: TRUE f109_out(x13) -> f41_out(x13) :|: TRUE f41_in(x14) -> f109_in(x14) :|: TRUE f44_in -> f44_out :|: TRUE f109_out(x15) -> f118_out(x15) :|: TRUE f118_in(x16) -> f109_in(x16) :|: TRUE f115_in -> f115_out :|: TRUE f112_out(x17) -> f109_out(x17) :|: TRUE f109_in(x18) -> f112_in(x18) :|: TRUE f15_out(x19) -> f35_out(x19) :|: TRUE f35_in(x20) -> f15_in(x20) :|: TRUE f38_out(x21) -> f34_out(x21) :|: TRUE f34_in(x22) -> f38_in(x22) :|: TRUE f32_out(x23, x24) -> f24_out(.(x23, .(x24, []))) :|: TRUE f33_out -> f24_out(x25) :|: TRUE f24_in(.(x26, .(x27, []))) -> f32_in(x26, x27) :|: TRUE f24_in(x28) -> f33_in :|: TRUE f15_in(x29) -> f21_in(x29) :|: TRUE f21_out(x30) -> f15_out(x30) :|: TRUE f40_out(x31) -> f38_out(x31) :|: TRUE f38_in(x32) -> f40_in(x32) :|: TRUE f41_out(x33) -> f38_out(x33) :|: TRUE f38_in(x34) -> f41_in(x34) :|: TRUE f113_in(x35) -> f116_in :|: TRUE f113_in(T71) -> f115_in :|: TRUE f115_out -> f113_out(x36) :|: TRUE f116_out -> f113_out(x37) :|: TRUE f46_out -> f40_out(x38) :|: TRUE f44_out -> f40_out(T42) :|: TRUE f40_in(x39) -> f46_in :|: TRUE f40_in(x40) -> f44_in :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x41) -> f4_in(x41) :|: TRUE f4_in(x42) -> f8_in(x42) :|: TRUE f8_out(x43) -> f4_out(x43) :|: TRUE f8_in(x44) -> f15_in(x44) :|: TRUE f16_out(x45) -> f8_out(x45) :|: TRUE f15_out(x46) -> f16_in(x46) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (166) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f21_in(x2) -> f24_in(x2) :|: TRUE f112_in(T55) -> f114_in(T55) :|: TRUE f113_out(x3) -> f112_out(x3) :|: TRUE f112_in(x4) -> f113_in(x4) :|: TRUE f114_out(x5) -> f112_out(x5) :|: TRUE f32_in(T21, T22) -> f34_in(T21) :|: TRUE f34_out(x6) -> f35_in(x7) :|: TRUE f114_in(T79) -> f118_in(T79) :|: TRUE f118_out(x11) -> f114_out(x11) :|: TRUE f109_out(x13) -> f41_out(x13) :|: TRUE f41_in(x14) -> f109_in(x14) :|: TRUE f44_in -> f44_out :|: TRUE f109_out(x15) -> f118_out(x15) :|: TRUE f118_in(x16) -> f109_in(x16) :|: TRUE f115_in -> f115_out :|: TRUE f112_out(x17) -> f109_out(x17) :|: TRUE f109_in(x18) -> f112_in(x18) :|: TRUE f35_in(x20) -> f15_in(x20) :|: TRUE f38_out(x21) -> f34_out(x21) :|: TRUE f34_in(x22) -> f38_in(x22) :|: TRUE f24_in(.(x26, .(x27, []))) -> f32_in(x26, x27) :|: TRUE f15_in(x29) -> f21_in(x29) :|: TRUE f40_out(x31) -> f38_out(x31) :|: TRUE f38_in(x32) -> f40_in(x32) :|: TRUE f41_out(x33) -> f38_out(x33) :|: TRUE f38_in(x34) -> f41_in(x34) :|: TRUE f113_in(T71) -> f115_in :|: TRUE f115_out -> f113_out(x36) :|: TRUE f44_out -> f40_out(T42) :|: TRUE f40_in(x40) -> f44_in :|: TRUE ---------------------------------------- (167) Obligation: Rules: f21_in(x2) -> f24_in(x2) :|: TRUE f112_in(T55) -> f114_in(T55) :|: TRUE f113_out(x3) -> f112_out(x3) :|: TRUE f112_in(x4) -> f113_in(x4) :|: TRUE f114_out(x5) -> f112_out(x5) :|: TRUE f32_in(T21, T22) -> f34_in(T21) :|: TRUE f34_out(x6) -> f35_in(x7) :|: TRUE f114_in(T79) -> f118_in(T79) :|: TRUE f118_out(x11) -> f114_out(x11) :|: TRUE f109_out(x13) -> f41_out(x13) :|: TRUE f41_in(x14) -> f109_in(x14) :|: TRUE f44_in -> f44_out :|: TRUE f109_out(x15) -> f118_out(x15) :|: TRUE f118_in(x16) -> f109_in(x16) :|: TRUE f115_in -> f115_out :|: TRUE f112_out(x17) -> f109_out(x17) :|: TRUE f109_in(x18) -> f112_in(x18) :|: TRUE f35_in(x20) -> f15_in(x20) :|: TRUE f38_out(x21) -> f34_out(x21) :|: TRUE f34_in(x22) -> f38_in(x22) :|: TRUE f24_in(.(x26, .(x27, []))) -> f32_in(x26, x27) :|: TRUE f15_in(x29) -> f21_in(x29) :|: TRUE f40_out(x31) -> f38_out(x31) :|: TRUE f38_in(x32) -> f40_in(x32) :|: TRUE f41_out(x33) -> f38_out(x33) :|: TRUE f38_in(x34) -> f41_in(x34) :|: TRUE f113_in(T71) -> f115_in :|: TRUE f115_out -> f113_out(x36) :|: TRUE f44_out -> f40_out(T42) :|: TRUE f40_in(x40) -> f44_in :|: TRUE ---------------------------------------- (168) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (169) Obligation: Rules: f109_out(x13:0) -> f38_out(x13:0) :|: TRUE f38_out(x21:0) -> f38_out(T42:0) :|: TRUE f109_out(x15:0) -> f109_out(x15:0) :|: TRUE f112_in(x4:0) -> f109_out(x36:0) :|: TRUE f38_out(x) -> f112_in(x1) :|: TRUE f112_in(T55:0) -> f112_in(T55:0) :|: TRUE ---------------------------------------- (170) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (171) Obligation: Rules: f109_out(x13:0) -> f38_out(x13:0) :|: TRUE f38_out(x21:0) -> f38_out(T42:0) :|: TRUE f109_out(x15:0) -> f109_out(x15:0) :|: TRUE f112_in(x4:0) -> f109_out(x36:0) :|: TRUE f38_out(x) -> f112_in(x1) :|: TRUE f112_in(T55:0) -> f112_in(T55:0) :|: TRUE ---------------------------------------- (172) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f109_out(x13:0) -> f38_out(x13:0) :|: TRUE (2) f38_out(x21:0) -> f38_out(T42:0) :|: TRUE (3) f109_out(x15:0) -> f109_out(x15:0) :|: TRUE (4) f112_in(x4:0) -> f109_out(x36:0) :|: TRUE (5) f38_out(x) -> f112_in(x1) :|: TRUE (6) f112_in(T55:0) -> f112_in(T55:0) :|: TRUE Arcs: (1) -> (2), (5) (2) -> (2), (5) (3) -> (1), (3) (4) -> (1), (3) (5) -> (4), (6) (6) -> (4), (6) This digraph is fully evaluated! ---------------------------------------- (173) Obligation: Termination digraph: Nodes: (1) f109_out(x13:0) -> f38_out(x13:0) :|: TRUE (2) f109_out(x15:0) -> f109_out(x15:0) :|: TRUE (3) f112_in(x4:0) -> f109_out(x36:0) :|: TRUE (4) f112_in(T55:0) -> f112_in(T55:0) :|: TRUE (5) f38_out(x) -> f112_in(x1) :|: TRUE (6) f38_out(x21:0) -> f38_out(T42:0) :|: TRUE Arcs: (1) -> (5), (6) (2) -> (1), (2) (3) -> (1), (2) (4) -> (3), (4) (5) -> (3), (4) (6) -> (5), (6) This digraph is fully evaluated! ---------------------------------------- (174) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f109_out(VARIABLE) f38_out(VARIABLE) f112_in(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (175) Obligation: Rules: f109_out(x13:0) -> f38_out(x13:0) :|: TRUE f109_out(x15:0) -> f109_out(x15:0) :|: TRUE f112_in(x4:0) -> f109_out(x36:0) :|: TRUE f112_in(T55:0) -> f112_in(T55:0) :|: TRUE f38_out(x) -> f112_in(x1) :|: TRUE f38_out(x21:0) -> f38_out(T42:0) :|: TRUE