/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 insert(g,a,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) TransformationProof [SOUND, 0 ms] (27) QDP (28) TransformationProof [SOUND, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) AND (34) QDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) QDP (37) QReductionProof [EQUIVALENT, 0 ms] (38) QDP (39) QDP (40) PrologToPiTRSProof [SOUND, 0 ms] (41) PiTRS (42) DependencyPairsProof [EQUIVALENT, 0 ms] (43) PiDP (44) DependencyGraphProof [EQUIVALENT, 0 ms] (45) AND (46) PiDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) PiDP (49) PiDPToQDPProof [SOUND, 0 ms] (50) QDP (51) QDPSizeChangeProof [EQUIVALENT, 0 ms] (52) YES (53) PiDP (54) UsableRulesProof [EQUIVALENT, 0 ms] (55) PiDP (56) PiDPToQDPProof [SOUND, 0 ms] (57) QDP (58) QDPSizeChangeProof [EQUIVALENT, 0 ms] (59) YES (60) PiDP (61) UsableRulesProof [EQUIVALENT, 0 ms] (62) PiDP (63) PiDPToQDPProof [SOUND, 0 ms] (64) QDP (65) TransformationProof [SOUND, 0 ms] (66) QDP (67) TransformationProof [SOUND, 0 ms] (68) QDP (69) TransformationProof [EQUIVALENT, 0 ms] (70) QDP (71) DependencyGraphProof [EQUIVALENT, 0 ms] (72) AND (73) QDP (74) UsableRulesProof [EQUIVALENT, 0 ms] (75) QDP (76) QReductionProof [EQUIVALENT, 0 ms] (77) QDP (78) QDP (79) TransformationProof [EQUIVALENT, 0 ms] (80) QDP (81) PrologToTRSTransformerProof [SOUND, 0 ms] (82) QTRS (83) DependencyPairsProof [EQUIVALENT, 0 ms] (84) QDP (85) DependencyGraphProof [EQUIVALENT, 0 ms] (86) AND (87) QDP (88) UsableRulesProof [EQUIVALENT, 0 ms] (89) QDP (90) QDPSizeChangeProof [EQUIVALENT, 0 ms] (91) YES (92) QDP (93) UsableRulesProof [EQUIVALENT, 0 ms] (94) QDP (95) QDPSizeChangeProof [EQUIVALENT, 0 ms] (96) YES (97) QDP (98) NonTerminationLoopProof [COMPLETE, 0 ms] (99) NO (100) PrologToIRSwTTransformerProof [SOUND, 58 ms] (101) AND (102) IRSwT (103) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (104) IRSwT (105) IntTRSCompressionProof [EQUIVALENT, 34 ms] (106) IRSwT (107) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (108) IRSwT (109) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (110) IRSwT (111) TempFilterProof [SOUND, 3 ms] (112) IRSwT (113) IRSwTToQDPProof [SOUND, 0 ms] (114) QDP (115) QDPSizeChangeProof [EQUIVALENT, 0 ms] (116) YES (117) IRSwT (118) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (119) IRSwT (120) IntTRSCompressionProof [EQUIVALENT, 2 ms] (121) IRSwT (122) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (123) IRSwT (124) IRSwTTerminationDigraphProof [EQUIVALENT, 2 ms] (125) IRSwT (126) TempFilterProof [SOUND, 2 ms] (127) IRSwT (128) IRSwTToQDPProof [SOUND, 0 ms] (129) QDP (130) QDPSizeChangeProof [EQUIVALENT, 0 ms] (131) YES (132) IRSwT (133) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (134) IRSwT (135) IntTRSCompressionProof [EQUIVALENT, 22 ms] (136) IRSwT (137) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (138) IRSwT (139) PrologToDTProblemTransformerProof [SOUND, 51 ms] (140) TRIPLES (141) TriplesToPiDPProof [SOUND, 45 ms] (142) PiDP (143) DependencyGraphProof [EQUIVALENT, 0 ms] (144) AND (145) PiDP (146) UsableRulesProof [EQUIVALENT, 0 ms] (147) PiDP (148) PiDPToQDPProof [SOUND, 0 ms] (149) QDP (150) QDPSizeChangeProof [EQUIVALENT, 0 ms] (151) YES (152) PiDP (153) UsableRulesProof [EQUIVALENT, 0 ms] (154) PiDP (155) PiDPToQDPProof [SOUND, 0 ms] (156) QDP (157) QDPSizeChangeProof [EQUIVALENT, 0 ms] (158) YES (159) PiDP (160) PiDPToQDPProof [SOUND, 0 ms] (161) QDP (162) TransformationProof [SOUND, 0 ms] (163) QDP (164) TransformationProof [SOUND, 0 ms] (165) QDP (166) TransformationProof [SOUND, 0 ms] (167) QDP (168) TransformationProof [SOUND, 0 ms] (169) QDP ---------------------------------------- (0) Obligation: Clauses: insert(X, void, tree(X, void, void)). insert(X, tree(X, Left, Right), tree(X, Left, Right)). insert(X, tree(Y, Left, Right), tree(Y, Left1, Right)) :- ','(less(X, Y), insert(X, Left, Left1)). insert(X, tree(Y, Left, Right), tree(Y, Left, Right1)) :- ','(less(Y, X), insert(X, Right, Right1)). less(0, s(X1)). less(s(X), s(Y)) :- less(X, Y). Query: insert(g,a,a) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: insert_in_3: (b,f,f) less_in_2: (b,f) (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) ---------------------------------------- (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: INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_GA(X, Y) LESS_IN_GA(s(X), s(Y)) -> U5_GA(X, Y, less_in_ga(X, Y)) LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_GAA(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_AG(Y, X) LESS_IN_AG(s(X), s(Y)) -> U5_AG(X, Y, less_in_ag(X, Y)) LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_GAA(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x1, x3) U2_GAA(x1, x2, x3, x4, x5, x6) = U2_GAA(x1, x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x2, x3) U4_GAA(x1, x2, x3, x4, x5, x6) = U4_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_GA(X, Y) LESS_IN_GA(s(X), s(Y)) -> U5_GA(X, Y, less_in_ga(X, Y)) LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_GAA(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_AG(Y, X) LESS_IN_AG(s(X), s(Y)) -> U5_AG(X, Y, less_in_ag(X, Y)) LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_GAA(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x1, x3) U2_GAA(x1, x2, x3, x4, x5, x6) = U2_GAA(x1, x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x2, x3) U4_GAA(x1, x2, x3, x4, x5, x6) = U4_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(Y)) -> LESS_IN_AG(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: *LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) 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: LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) 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: LESS_IN_GA(s(X)) -> LESS_IN_GA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *LESS_IN_GA(s(X)) -> LESS_IN_GA(X) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x1, x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x1, x6) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The argument filtering Pi contains the following mapping: less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga(x1) s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x1, x3) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1, x2) U5_ag(x1, x2, x3) = U5_ag(x2, x3) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, less_out_ga(X)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(X) -> U1_GAA(X, less_in_ga(X)) INSERT_IN_GAA(X) -> U3_GAA(X, less_in_ag(X)) U3_GAA(X, less_out_ag(Y, X)) -> INSERT_IN_GAA(X) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(Y)) -> U5_ag(Y, less_in_ag(Y)) U5_ga(X, less_out_ga(X)) -> less_out_ga(s(X)) U5_ag(Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (SOUND) By narrowing [LPAR04] the rule INSERT_IN_GAA(X) -> U1_GAA(X, less_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)),INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0))) (INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(x0, less_in_ga(x0))),INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(x0, less_in_ga(x0)))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, less_out_ga(X)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(X) -> U3_GAA(X, less_in_ag(X)) U3_GAA(X, less_out_ag(Y, X)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)) INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(x0, less_in_ga(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(Y)) -> U5_ag(Y, less_in_ag(Y)) U5_ga(X, less_out_ga(X)) -> less_out_ga(s(X)) U5_ag(Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) TransformationProof (SOUND) By narrowing [LPAR04] the rule INSERT_IN_GAA(X) -> U3_GAA(X, less_in_ag(X)) at position [1] we obtained the following new rules [LPAR04]: (INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0, s(x0))),INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0, s(x0)))) (INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(x0, less_in_ag(x0))),INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(x0, less_in_ag(x0)))) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, less_out_ga(X)) -> INSERT_IN_GAA(X) U3_GAA(X, less_out_ag(Y, X)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)) INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(x0, less_in_ga(x0))) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0, s(x0))) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(x0, less_in_ag(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(Y)) -> U5_ag(Y, less_in_ag(Y)) U5_ga(X, less_out_ga(X)) -> less_out_ga(s(X)) U5_ag(Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_GAA(X, less_out_ga(X)) -> INSERT_IN_GAA(X) we obtained the following new rules [LPAR04]: (U1_GAA(0, less_out_ga(0)) -> INSERT_IN_GAA(0),U1_GAA(0, less_out_ga(0)) -> INSERT_IN_GAA(0)) (U1_GAA(s(z0), less_out_ga(s(z0))) -> INSERT_IN_GAA(s(z0)),U1_GAA(s(z0), less_out_ga(s(z0))) -> INSERT_IN_GAA(s(z0))) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GAA(X, less_out_ag(Y, X)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)) INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(x0, less_in_ga(x0))) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0, s(x0))) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(x0, less_in_ag(x0))) U1_GAA(0, less_out_ga(0)) -> INSERT_IN_GAA(0) U1_GAA(s(z0), less_out_ga(s(z0))) -> INSERT_IN_GAA(s(z0)) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(Y)) -> U5_ag(Y, less_in_ag(Y)) U5_ga(X, less_out_ga(X)) -> less_out_ga(s(X)) U5_ag(Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (33) Complex Obligation (AND) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(0, less_out_ga(0)) -> INSERT_IN_GAA(0) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(Y)) -> U5_ag(Y, less_in_ag(Y)) U5_ga(X, less_out_ga(X)) -> less_out_ga(s(X)) U5_ag(Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) 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. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(0, less_out_ga(0)) -> INSERT_IN_GAA(0) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)) R is empty. The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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]. less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(0, less_out_ga(0)) -> INSERT_IN_GAA(0) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga(0)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(x0, less_in_ga(x0))) U1_GAA(s(z0), less_out_ga(s(z0))) -> INSERT_IN_GAA(s(z0)) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0, s(x0))) U3_GAA(X, less_out_ag(Y, X)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(x0, less_in_ag(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(Y)) -> U5_ag(Y, less_in_ag(Y)) U5_ga(X, less_out_ga(X)) -> less_out_ga(s(X)) U5_ag(Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0, x1) U5_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (40) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: insert_in_3: (b,f,f) less_in_2: (b,f) (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (41) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) ---------------------------------------- (42) 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: INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_GA(X, Y) LESS_IN_GA(s(X), s(Y)) -> U5_GA(X, Y, less_in_ga(X, Y)) LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_GAA(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_AG(Y, X) LESS_IN_AG(s(X), s(Y)) -> U5_AG(X, Y, less_in_ag(X, Y)) LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_GAA(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x3) U2_GAA(x1, x2, x3, x4, x5, x6) = U2_GAA(x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x3) U4_GAA(x1, x2, x3, x4, x5, x6) = U4_GAA(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (43) Obligation: Pi DP problem: The TRS P consists of the following rules: INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_GA(X, Y) LESS_IN_GA(s(X), s(Y)) -> U5_GA(X, Y, less_in_ga(X, Y)) LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_GAA(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_AG(Y, X) LESS_IN_AG(s(X), s(Y)) -> U5_AG(X, Y, less_in_ag(X, Y)) LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_GAA(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x3) U2_GAA(x1, x2, x3, x4, x5, x6) = U2_GAA(x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x3) U4_GAA(x1, x2, x3, x4, x5, x6) = U4_GAA(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (44) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (45) Complex Obligation (AND) ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (49) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) 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: *LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y) The graph contains the following edges 1 > 1 ---------------------------------------- (52) YES ---------------------------------------- (53) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (54) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (55) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (56) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: LESS_IN_GA(s(X)) -> LESS_IN_GA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (58) 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: *LESS_IN_GA(s(X)) -> LESS_IN_GA(X) The graph contains the following edges 1 > 1 ---------------------------------------- (59) YES ---------------------------------------- (60) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: insert_in_gaa(X, void, tree(X, void, void)) -> insert_out_gaa(X, void, tree(X, void, void)) insert_in_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gaa(X, tree(X, Left, Right), tree(X, Left, Right)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gaa(X, Y, Left, Right, Left1, less_in_ga(X, Y)) less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U1_gaa(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> U2_gaa(X, Y, Left, Right, Left1, insert_in_gaa(X, Left, Left1)) insert_in_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gaa(X, Y, Left, Right, Right1, less_in_ag(Y, X)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) U3_gaa(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> U4_gaa(X, Y, Left, Right, Right1, insert_in_gaa(X, Right, Right1)) U4_gaa(X, Y, Left, Right, Right1, insert_out_gaa(X, Right, Right1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left, Right1)) U2_gaa(X, Y, Left, Right, Left1, insert_out_gaa(X, Left, Left1)) -> insert_out_gaa(X, tree(Y, Left, Right), tree(Y, Left1, Right)) The argument filtering Pi contains the following mapping: insert_in_gaa(x1, x2, x3) = insert_in_gaa(x1) insert_out_gaa(x1, x2, x3) = insert_out_gaa U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x1, x6) less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) U4_gaa(x1, x2, x3, x4, x5, x6) = U4_gaa(x6) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (61) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (62) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, Left, Right, Left1, less_out_ga(X, Y)) -> INSERT_IN_GAA(X, Left, Left1) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAA(X, Y, Left, Right, Left1, less_in_ga(X, Y)) INSERT_IN_GAA(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAA(X, Y, Left, Right, Right1, less_in_ag(Y, X)) U3_GAA(X, Y, Left, Right, Right1, less_out_ag(Y, X)) -> INSERT_IN_GAA(X, Right, Right1) The TRS R consists of the following rules: less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1)) less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y)) U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y)) U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y)) The argument filtering Pi contains the following mapping: less_in_ga(x1, x2) = less_in_ga(x1) 0 = 0 less_out_ga(x1, x2) = less_out_ga s(x1) = s(x1) U5_ga(x1, x2, x3) = U5_ga(x3) less_in_ag(x1, x2) = less_in_ag(x2) less_out_ag(x1, x2) = less_out_ag(x1) U5_ag(x1, x2, x3) = U5_ag(x3) INSERT_IN_GAA(x1, x2, x3) = INSERT_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (63) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, less_out_ga) -> INSERT_IN_GAA(X) INSERT_IN_GAA(X) -> U1_GAA(X, less_in_ga(X)) INSERT_IN_GAA(X) -> U3_GAA(X, less_in_ag(X)) U3_GAA(X, less_out_ag(Y)) -> INSERT_IN_GAA(X) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (65) TransformationProof (SOUND) By narrowing [LPAR04] the rule INSERT_IN_GAA(X) -> U1_GAA(X, less_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga),INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga)) (INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0))),INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0)))) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, less_out_ga) -> INSERT_IN_GAA(X) INSERT_IN_GAA(X) -> U3_GAA(X, less_in_ag(X)) U3_GAA(X, less_out_ag(Y)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (67) TransformationProof (SOUND) By narrowing [LPAR04] the rule INSERT_IN_GAA(X) -> U3_GAA(X, less_in_ag(X)) at position [1] we obtained the following new rules [LPAR04]: (INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0)),INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0))) (INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(less_in_ag(x0))),INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(less_in_ag(x0)))) ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, less_out_ga) -> INSERT_IN_GAA(X) U3_GAA(X, less_out_ag(Y)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0))) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0)) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(less_in_ag(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (69) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_GAA(X, less_out_ga) -> INSERT_IN_GAA(X) we obtained the following new rules [LPAR04]: (U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0),U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0)) (U1_GAA(s(z0), less_out_ga) -> INSERT_IN_GAA(s(z0)),U1_GAA(s(z0), less_out_ga) -> INSERT_IN_GAA(s(z0))) ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GAA(X, less_out_ag(Y)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0))) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0)) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(less_in_ag(x0))) U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0) U1_GAA(s(z0), less_out_ga) -> INSERT_IN_GAA(s(z0)) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (71) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (72) Complex Obligation (AND) ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (74) 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. ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) R is empty. The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (76) 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]. less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0) INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0))) U1_GAA(s(z0), less_out_ga) -> INSERT_IN_GAA(s(z0)) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0)) U3_GAA(X, less_out_ag(Y)) -> INSERT_IN_GAA(X) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(less_in_ag(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (79) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U3_GAA(X, less_out_ag(Y)) -> INSERT_IN_GAA(X) we obtained the following new rules [LPAR04]: (U3_GAA(s(z0), less_out_ag(0)) -> INSERT_IN_GAA(s(z0)),U3_GAA(s(z0), less_out_ag(0)) -> INSERT_IN_GAA(s(z0))) (U3_GAA(s(z0), less_out_ag(x1)) -> INSERT_IN_GAA(s(z0)),U3_GAA(s(z0), less_out_ag(x1)) -> INSERT_IN_GAA(s(z0))) ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: INSERT_IN_GAA(s(x0)) -> U1_GAA(s(x0), U5_ga(less_in_ga(x0))) U1_GAA(s(z0), less_out_ga) -> INSERT_IN_GAA(s(z0)) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), less_out_ag(0)) INSERT_IN_GAA(s(x0)) -> U3_GAA(s(x0), U5_ag(less_in_ag(x0))) U3_GAA(s(z0), less_out_ag(0)) -> INSERT_IN_GAA(s(z0)) U3_GAA(s(z0), less_out_ag(x1)) -> INSERT_IN_GAA(s(z0)) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga less_in_ga(s(X)) -> U5_ga(less_in_ga(X)) less_in_ag(s(X1)) -> less_out_ag(0) less_in_ag(s(Y)) -> U5_ag(less_in_ag(Y)) U5_ga(less_out_ga) -> less_out_ga U5_ag(less_out_ag(X)) -> less_out_ag(s(X)) The set Q consists of the following terms: less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (81) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 3, "program": { "directives": [], "clauses": [ [ "(insert X (void) (tree X (void) (void)))", null ], [ "(insert X (tree X Left Right) (tree X Left Right))", null ], [ "(insert X (tree Y Left Right) (tree Y Left1 Right))", "(',' (less X Y) (insert X Left Left1))" ], [ "(insert X (tree Y Left Right) (tree Y Left Right1))", "(',' (less Y X) (insert X Right Right1))" ], [ "(less (0) (s X1))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "290": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T44 T54 T55)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "291": { "goal": [ { "clause": 4, "scope": 2, "term": "(less T44 T49)" }, { "clause": 5, "scope": 2, "term": "(less T44 T49)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "390": { "goal": [ { "clause": 4, "scope": 3, "term": "(less T89 T84)" }, { "clause": 5, "scope": 3, "term": "(less T89 T84)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "270": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "292": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "391": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "type": "Nodes", "293": { "goal": [{ "clause": 5, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "392": { "goal": [{ "clause": 5, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "393": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "394": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "395": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "396": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T109 T108)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T108"], "free": [], "exprvars": [] } }, "397": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "279": { "goal": [{ "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "359": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "281": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "360": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "262": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "361": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "263": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "287": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T44 T49) (insert T44 T50 T51))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "386": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T89 T84) (insert T84 T90 T91))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "266": { "goal": [{ "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "288": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "365": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T67 T69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T67"], "free": [], "exprvars": [] } }, "387": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "267": { "goal": [ { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "289": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "366": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "388": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "389": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T84 T94 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "269": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 5, "label": "PARALLEL" }, { "from": 4, "to": 6, "label": "PARALLEL" }, { "from": 5, "to": 19, "label": "EVAL with clause\ninsert(X6, void, tree(X6, void, void)).\nand substitutionT1 -> T8,\nX6 -> T8,\nT2 -> void,\nT3 -> tree(T8, void, void)" }, { "from": 5, "to": 262, "label": "EVAL-BACKTRACK" }, { "from": 6, "to": 266, "label": "PARALLEL" }, { "from": 6, "to": 267, "label": "PARALLEL" }, { "from": 19, "to": 263, "label": "SUCCESS" }, { "from": 266, "to": 268, "label": "EVAL with clause\ninsert(X19, tree(X19, X20, X21), tree(X19, X20, X21)).\nand substitutionT1 -> T21,\nX19 -> T21,\nX20 -> T22,\nX21 -> T23,\nT2 -> tree(T21, T22, T23),\nT3 -> tree(T21, T22, T23)" }, { "from": 266, "to": 269, "label": "EVAL-BACKTRACK" }, { "from": 267, "to": 279, "label": "PARALLEL" }, { "from": 267, "to": 281, "label": "PARALLEL" }, { "from": 268, "to": 270, "label": "SUCCESS" }, { "from": 279, "to": 287, "label": "EVAL with clause\ninsert(X42, tree(X43, X44, X45), tree(X43, X46, X45)) :- ','(less(X42, X43), insert(X42, X44, X46)).\nand substitutionT1 -> T44,\nX42 -> T44,\nX43 -> T49,\nX44 -> T50,\nX45 -> T47,\nT2 -> tree(T49, T50, T47),\nX46 -> T51,\nT3 -> tree(T49, T51, T47),\nT45 -> T49,\nT46 -> T50,\nT48 -> T51" }, { "from": 279, "to": 288, "label": "EVAL-BACKTRACK" }, { "from": 281, "to": 386, "label": "EVAL with clause\ninsert(X76, tree(X77, X78, X79), tree(X77, X78, X80)) :- ','(less(X77, X76), insert(X76, X79, X80)).\nand substitutionT1 -> T84,\nX76 -> T84,\nX77 -> T89,\nX78 -> T86,\nX79 -> T90,\nT2 -> tree(T89, T86, T90),\nX80 -> T91,\nT3 -> tree(T89, T86, T91),\nT85 -> T89,\nT87 -> T90,\nT88 -> T91" }, { "from": 281, "to": 387, "label": "EVAL-BACKTRACK" }, { "from": 287, "to": 289, "label": "SPLIT 1" }, { "from": 287, "to": 290, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nreplacements:T50 -> T54,\nT51 -> T55" }, { "from": 289, "to": 291, "label": "CASE" }, { "from": 290, "to": 3, "label": "INSTANCE with matching:\nT1 -> T44\nT2 -> T54\nT3 -> T55" }, { "from": 291, "to": 292, "label": "PARALLEL" }, { "from": 291, "to": 293, "label": "PARALLEL" }, { "from": 292, "to": 359, "label": "EVAL with clause\nless(0, s(X55)).\nand substitutionT44 -> 0,\nX55 -> T62,\nT49 -> s(T62)" }, { "from": 292, "to": 360, "label": "EVAL-BACKTRACK" }, { "from": 293, "to": 365, "label": "EVAL with clause\nless(s(X60), s(X61)) :- less(X60, X61).\nand substitutionX60 -> T67,\nT44 -> s(T67),\nX61 -> T69,\nT49 -> s(T69),\nT68 -> T69" }, { "from": 293, "to": 366, "label": "EVAL-BACKTRACK" }, { "from": 359, "to": 361, "label": "SUCCESS" }, { "from": 365, "to": 289, "label": "INSTANCE with matching:\nT44 -> T67\nT49 -> T69" }, { "from": 386, "to": 388, "label": "SPLIT 1" }, { "from": 386, "to": 389, "label": "SPLIT 2\nnew knowledge:\nT89 is ground\nT84 is ground\nreplacements:T90 -> T94,\nT91 -> T95" }, { "from": 388, "to": 390, "label": "CASE" }, { "from": 389, "to": 3, "label": "INSTANCE with matching:\nT1 -> T84\nT2 -> T94\nT3 -> T95" }, { "from": 390, "to": 391, "label": "PARALLEL" }, { "from": 390, "to": 392, "label": "PARALLEL" }, { "from": 391, "to": 393, "label": "EVAL with clause\nless(0, s(X89)).\nand substitutionT89 -> 0,\nX89 -> T102,\nT84 -> s(T102)" }, { "from": 391, "to": 394, "label": "EVAL-BACKTRACK" }, { "from": 392, "to": 396, "label": "EVAL with clause\nless(s(X94), s(X95)) :- less(X94, X95).\nand substitutionX94 -> T109,\nT89 -> s(T109),\nX95 -> T108,\nT84 -> s(T108),\nT107 -> T109" }, { "from": 392, "to": 397, "label": "EVAL-BACKTRACK" }, { "from": 393, "to": 395, "label": "SUCCESS" }, { "from": 396, "to": 388, "label": "INSTANCE with matching:\nT89 -> T109\nT84 -> T108" } ], "type": "Graph" } } ---------------------------------------- (82) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in(T8) -> f3_out1 f3_in(T44) -> U1(f287_in(T44), T44) U1(f287_out1, T44) -> f3_out1 f3_in(T84) -> U2(f386_in(T84), T84) U2(f386_out1(T89), T84) -> f3_out1 f289_in(0) -> f289_out1 f289_in(s(T67)) -> U3(f289_in(T67), s(T67)) U3(f289_out1, s(T67)) -> f289_out1 f388_in(s(T102)) -> f388_out1(0) f388_in(s(T108)) -> U4(f388_in(T108), s(T108)) U4(f388_out1(T109), s(T108)) -> f388_out1(s(T109)) f287_in(T44) -> U5(f289_in(T44), T44) U5(f289_out1, T44) -> U6(f3_in(T44), T44) U6(f3_out1, T44) -> f287_out1 f386_in(T84) -> U7(f388_in(T84), T84) U7(f388_out1(T89), T84) -> U8(f3_in(T84), T84, T89) U8(f3_out1, T84, T89) -> f386_out1(T89) Q is empty. ---------------------------------------- (83) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN(T44) -> U1^1(f287_in(T44), T44) F3_IN(T44) -> F287_IN(T44) F3_IN(T84) -> U2^1(f386_in(T84), T84) F3_IN(T84) -> F386_IN(T84) F289_IN(s(T67)) -> U3^1(f289_in(T67), s(T67)) F289_IN(s(T67)) -> F289_IN(T67) F388_IN(s(T108)) -> U4^1(f388_in(T108), s(T108)) F388_IN(s(T108)) -> F388_IN(T108) F287_IN(T44) -> U5^1(f289_in(T44), T44) F287_IN(T44) -> F289_IN(T44) U5^1(f289_out1, T44) -> U6^1(f3_in(T44), T44) U5^1(f289_out1, T44) -> F3_IN(T44) F386_IN(T84) -> U7^1(f388_in(T84), T84) F386_IN(T84) -> F388_IN(T84) U7^1(f388_out1(T89), T84) -> U8^1(f3_in(T84), T84, T89) U7^1(f388_out1(T89), T84) -> F3_IN(T84) The TRS R consists of the following rules: f3_in(T8) -> f3_out1 f3_in(T44) -> U1(f287_in(T44), T44) U1(f287_out1, T44) -> f3_out1 f3_in(T84) -> U2(f386_in(T84), T84) U2(f386_out1(T89), T84) -> f3_out1 f289_in(0) -> f289_out1 f289_in(s(T67)) -> U3(f289_in(T67), s(T67)) U3(f289_out1, s(T67)) -> f289_out1 f388_in(s(T102)) -> f388_out1(0) f388_in(s(T108)) -> U4(f388_in(T108), s(T108)) U4(f388_out1(T109), s(T108)) -> f388_out1(s(T109)) f287_in(T44) -> U5(f289_in(T44), T44) U5(f289_out1, T44) -> U6(f3_in(T44), T44) U6(f3_out1, T44) -> f287_out1 f386_in(T84) -> U7(f388_in(T84), T84) U7(f388_out1(T89), T84) -> U8(f3_in(T84), T84, T89) U8(f3_out1, T84, T89) -> f386_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 8 less nodes. ---------------------------------------- (86) Complex Obligation (AND) ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: F388_IN(s(T108)) -> F388_IN(T108) The TRS R consists of the following rules: f3_in(T8) -> f3_out1 f3_in(T44) -> U1(f287_in(T44), T44) U1(f287_out1, T44) -> f3_out1 f3_in(T84) -> U2(f386_in(T84), T84) U2(f386_out1(T89), T84) -> f3_out1 f289_in(0) -> f289_out1 f289_in(s(T67)) -> U3(f289_in(T67), s(T67)) U3(f289_out1, s(T67)) -> f289_out1 f388_in(s(T102)) -> f388_out1(0) f388_in(s(T108)) -> U4(f388_in(T108), s(T108)) U4(f388_out1(T109), s(T108)) -> f388_out1(s(T109)) f287_in(T44) -> U5(f289_in(T44), T44) U5(f289_out1, T44) -> U6(f3_in(T44), T44) U6(f3_out1, T44) -> f287_out1 f386_in(T84) -> U7(f388_in(T84), T84) U7(f388_out1(T89), T84) -> U8(f3_in(T84), T84, T89) U8(f3_out1, T84, T89) -> f386_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: F388_IN(s(T108)) -> F388_IN(T108) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) 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: *F388_IN(s(T108)) -> F388_IN(T108) The graph contains the following edges 1 > 1 ---------------------------------------- (91) YES ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(s(T67)) -> F289_IN(T67) The TRS R consists of the following rules: f3_in(T8) -> f3_out1 f3_in(T44) -> U1(f287_in(T44), T44) U1(f287_out1, T44) -> f3_out1 f3_in(T84) -> U2(f386_in(T84), T84) U2(f386_out1(T89), T84) -> f3_out1 f289_in(0) -> f289_out1 f289_in(s(T67)) -> U3(f289_in(T67), s(T67)) U3(f289_out1, s(T67)) -> f289_out1 f388_in(s(T102)) -> f388_out1(0) f388_in(s(T108)) -> U4(f388_in(T108), s(T108)) U4(f388_out1(T109), s(T108)) -> f388_out1(s(T109)) f287_in(T44) -> U5(f289_in(T44), T44) U5(f289_out1, T44) -> U6(f3_in(T44), T44) U6(f3_out1, T44) -> f287_out1 f386_in(T84) -> U7(f388_in(T84), T84) U7(f388_out1(T89), T84) -> U8(f3_in(T84), T84, T89) U8(f3_out1, T84, T89) -> f386_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: F289_IN(s(T67)) -> F289_IN(T67) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) 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: *F289_IN(s(T67)) -> F289_IN(T67) The graph contains the following edges 1 > 1 ---------------------------------------- (96) YES ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN(T44) -> F287_IN(T44) F287_IN(T44) -> U5^1(f289_in(T44), T44) U5^1(f289_out1, T44) -> F3_IN(T44) F3_IN(T84) -> F386_IN(T84) F386_IN(T84) -> U7^1(f388_in(T84), T84) U7^1(f388_out1(T89), T84) -> F3_IN(T84) The TRS R consists of the following rules: f3_in(T8) -> f3_out1 f3_in(T44) -> U1(f287_in(T44), T44) U1(f287_out1, T44) -> f3_out1 f3_in(T84) -> U2(f386_in(T84), T84) U2(f386_out1(T89), T84) -> f3_out1 f289_in(0) -> f289_out1 f289_in(s(T67)) -> U3(f289_in(T67), s(T67)) U3(f289_out1, s(T67)) -> f289_out1 f388_in(s(T102)) -> f388_out1(0) f388_in(s(T108)) -> U4(f388_in(T108), s(T108)) U4(f388_out1(T109), s(T108)) -> f388_out1(s(T109)) f287_in(T44) -> U5(f289_in(T44), T44) U5(f289_out1, T44) -> U6(f3_in(T44), T44) U6(f3_out1, T44) -> f287_out1 f386_in(T84) -> U7(f388_in(T84), T84) U7(f388_out1(T89), T84) -> U8(f3_in(T84), T84, T89) U8(f3_out1, T84, T89) -> f386_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (98) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = F287_IN(0) evaluates to t =F287_IN(0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F287_IN(0) -> U5^1(f289_in(0), 0) with rule F287_IN(T44) -> U5^1(f289_in(T44), T44) at position [] and matcher [T44 / 0] U5^1(f289_in(0), 0) -> U5^1(f289_out1, 0) with rule f289_in(0) -> f289_out1 at position [0] and matcher [ ] U5^1(f289_out1, 0) -> F3_IN(0) with rule U5^1(f289_out1, T44') -> F3_IN(T44') at position [] and matcher [T44' / 0] F3_IN(0) -> F287_IN(0) with rule F3_IN(T44) -> F287_IN(T44) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (99) NO ---------------------------------------- (100) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(insert X (void) (tree X (void) (void)))", null ], [ "(insert X (tree X Left Right) (tree X Left Right))", null ], [ "(insert X (tree Y Left Right) (tree Y Left1 Right))", "(',' (less X Y) (insert X Left Left1))" ], [ "(insert X (tree Y Left Right) (tree Y Left Right1))", "(',' (less Y X) (insert X Right Right1))" ], [ "(less (0) (s X1))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "171": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "252": { "goal": [{ "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "253": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "313": { "goal": [ { "clause": 4, "scope": 2, "term": "(less T44 T49)" }, { "clause": 5, "scope": 2, "term": "(less T44 T49)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "314": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "336": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T67 T69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T67"], "free": [], "exprvars": [] } }, "216": { "goal": [{ "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "315": { "goal": [{ "clause": 5, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "337": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "316": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "317": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "219": { "goal": [ { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "318": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "182": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T44 T49) (insert T44 T50 T51))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "261": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "186": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "241": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "340": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T89 T84) (insert T84 T90 T91))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "362": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "143": { "goal": [ { "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "242": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "341": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "363": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "144": { "goal": [{ "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "265": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T44 T54 T55)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "342": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "364": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [ { "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "343": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T84 T94 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "344": { "goal": [ { "clause": 4, "scope": 3, "term": "(less T89 T84)" }, { "clause": 5, "scope": 3, "term": "(less T89 T84)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "345": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "367": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T109 T108)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T108"], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": 5, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "368": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 143, "label": "CASE" }, { "from": 143, "to": 144, "label": "PARALLEL" }, { "from": 143, "to": 145, "label": "PARALLEL" }, { "from": 144, "to": 171, "label": "EVAL with clause\ninsert(X6, void, tree(X6, void, void)).\nand substitutionT1 -> T8,\nX6 -> T8,\nT2 -> void,\nT3 -> tree(T8, void, void)" }, { "from": 144, "to": 182, "label": "EVAL-BACKTRACK" }, { "from": 145, "to": 216, "label": "PARALLEL" }, { "from": 145, "to": 219, "label": "PARALLEL" }, { "from": 171, "to": 186, "label": "SUCCESS" }, { "from": 216, "to": 241, "label": "EVAL with clause\ninsert(X19, tree(X19, X20, X21), tree(X19, X20, X21)).\nand substitutionT1 -> T21,\nX19 -> T21,\nX20 -> T22,\nX21 -> T23,\nT2 -> tree(T21, T22, T23),\nT3 -> tree(T21, T22, T23)" }, { "from": 216, "to": 242, "label": "EVAL-BACKTRACK" }, { "from": 219, "to": 252, "label": "PARALLEL" }, { "from": 219, "to": 253, "label": "PARALLEL" }, { "from": 241, "to": 243, "label": "SUCCESS" }, { "from": 252, "to": 260, "label": "EVAL with clause\ninsert(X42, tree(X43, X44, X45), tree(X43, X46, X45)) :- ','(less(X42, X43), insert(X42, X44, X46)).\nand substitutionT1 -> T44,\nX42 -> T44,\nX43 -> T49,\nX44 -> T50,\nX45 -> T47,\nT2 -> tree(T49, T50, T47),\nX46 -> T51,\nT3 -> tree(T49, T51, T47),\nT45 -> T49,\nT46 -> T50,\nT48 -> T51" }, { "from": 252, "to": 261, "label": "EVAL-BACKTRACK" }, { "from": 253, "to": 340, "label": "EVAL with clause\ninsert(X76, tree(X77, X78, X79), tree(X77, X78, X80)) :- ','(less(X77, X76), insert(X76, X79, X80)).\nand substitutionT1 -> T84,\nX76 -> T84,\nX77 -> T89,\nX78 -> T86,\nX79 -> T90,\nT2 -> tree(T89, T86, T90),\nX80 -> T91,\nT3 -> tree(T89, T86, T91),\nT85 -> T89,\nT87 -> T90,\nT88 -> T91" }, { "from": 253, "to": 341, "label": "EVAL-BACKTRACK" }, { "from": 260, "to": 264, "label": "SPLIT 1" }, { "from": 260, "to": 265, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nreplacements:T50 -> T54,\nT51 -> T55" }, { "from": 264, "to": 313, "label": "CASE" }, { "from": 265, "to": 1, "label": "INSTANCE with matching:\nT1 -> T44\nT2 -> T54\nT3 -> T55" }, { "from": 313, "to": 314, "label": "PARALLEL" }, { "from": 313, "to": 315, "label": "PARALLEL" }, { "from": 314, "to": 316, "label": "EVAL with clause\nless(0, s(X55)).\nand substitutionT44 -> 0,\nX55 -> T62,\nT49 -> s(T62)" }, { "from": 314, "to": 317, "label": "EVAL-BACKTRACK" }, { "from": 315, "to": 336, "label": "EVAL with clause\nless(s(X60), s(X61)) :- less(X60, X61).\nand substitutionX60 -> T67,\nT44 -> s(T67),\nX61 -> T69,\nT49 -> s(T69),\nT68 -> T69" }, { "from": 315, "to": 337, "label": "EVAL-BACKTRACK" }, { "from": 316, "to": 318, "label": "SUCCESS" }, { "from": 336, "to": 264, "label": "INSTANCE with matching:\nT44 -> T67\nT49 -> T69" }, { "from": 340, "to": 342, "label": "SPLIT 1" }, { "from": 340, "to": 343, "label": "SPLIT 2\nnew knowledge:\nT89 is ground\nT84 is ground\nreplacements:T90 -> T94,\nT91 -> T95" }, { "from": 342, "to": 344, "label": "CASE" }, { "from": 343, "to": 1, "label": "INSTANCE with matching:\nT1 -> T84\nT2 -> T94\nT3 -> T95" }, { "from": 344, "to": 345, "label": "PARALLEL" }, { "from": 344, "to": 346, "label": "PARALLEL" }, { "from": 345, "to": 362, "label": "EVAL with clause\nless(0, s(X89)).\nand substitutionT89 -> 0,\nX89 -> T102,\nT84 -> s(T102)" }, { "from": 345, "to": 363, "label": "EVAL-BACKTRACK" }, { "from": 346, "to": 367, "label": "EVAL with clause\nless(s(X94), s(X95)) :- less(X94, X95).\nand substitutionX94 -> T109,\nT89 -> s(T109),\nX95 -> T108,\nT84 -> s(T108),\nT107 -> T109" }, { "from": 346, "to": 368, "label": "EVAL-BACKTRACK" }, { "from": 362, "to": 364, "label": "SUCCESS" }, { "from": 367, "to": 342, "label": "INSTANCE with matching:\nT89 -> T109\nT84 -> T108" } ], "type": "Graph" } } ---------------------------------------- (101) Complex Obligation (AND) ---------------------------------------- (102) Obligation: Rules: f367_in(T108) -> f342_in(T108) :|: TRUE f342_out(x) -> f367_out(x) :|: TRUE f368_out -> f346_out(T84) :|: TRUE f346_in(s(x1)) -> f367_in(x1) :|: TRUE f367_out(x2) -> f346_out(s(x2)) :|: TRUE f346_in(x3) -> f368_in :|: TRUE f342_in(x4) -> f344_in(x4) :|: TRUE f344_out(x5) -> f342_out(x5) :|: TRUE f346_out(x6) -> f344_out(x6) :|: TRUE f344_in(x7) -> f345_in(x7) :|: TRUE f344_in(x8) -> f346_in(x8) :|: TRUE f345_out(x9) -> f344_out(x9) :|: TRUE f143_out(T1) -> f1_out(T1) :|: TRUE f1_in(x10) -> f143_in(x10) :|: TRUE f143_in(x11) -> f144_in(x11) :|: TRUE f144_out(x12) -> f143_out(x12) :|: TRUE f145_out(x13) -> f143_out(x13) :|: TRUE f143_in(x14) -> f145_in(x14) :|: TRUE f216_out(x15) -> f145_out(x15) :|: TRUE f219_out(x16) -> f145_out(x16) :|: TRUE f145_in(x17) -> f219_in(x17) :|: TRUE f145_in(x18) -> f216_in(x18) :|: TRUE f219_in(x19) -> f253_in(x19) :|: TRUE f219_in(x20) -> f252_in(x20) :|: TRUE f253_out(x21) -> f219_out(x21) :|: TRUE f252_out(x22) -> f219_out(x22) :|: TRUE f253_in(x23) -> f340_in(x23) :|: TRUE f341_out -> f253_out(x24) :|: TRUE f340_out(x25) -> f253_out(x25) :|: TRUE f253_in(x26) -> f341_in :|: TRUE f343_out(x27) -> f340_out(x27) :|: TRUE f340_in(x28) -> f342_in(x28) :|: TRUE f342_out(x29) -> f343_in(x29) :|: TRUE Start term: f1_in(T1) ---------------------------------------- (103) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f367_in(T108) -> f342_in(T108) :|: TRUE f346_in(s(x1)) -> f367_in(x1) :|: TRUE f342_in(x4) -> f344_in(x4) :|: TRUE f344_in(x8) -> f346_in(x8) :|: TRUE ---------------------------------------- (104) Obligation: Rules: f367_in(T108) -> f342_in(T108) :|: TRUE f346_in(s(x1)) -> f367_in(x1) :|: TRUE f342_in(x4) -> f344_in(x4) :|: TRUE f344_in(x8) -> f346_in(x8) :|: TRUE ---------------------------------------- (105) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (106) Obligation: Rules: f346_in(s(x1:0)) -> f346_in(x1:0) :|: TRUE ---------------------------------------- (107) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (108) Obligation: Rules: f346_in(s(x1:0)) -> f346_in(x1:0) :|: TRUE ---------------------------------------- (109) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f346_in(s(x1:0)) -> f346_in(x1:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (110) Obligation: Termination digraph: Nodes: (1) f346_in(s(x1:0)) -> f346_in(x1:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (111) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f346_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (112) Obligation: Rules: f346_in(s(x1:0)) -> f346_in(x1:0) ---------------------------------------- (113) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (114) Obligation: Q DP problem: The TRS P consists of the following rules: f346_in(s(x1:0)) -> f346_in(x1:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (115) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *f346_in(s(x1:0)) -> f346_in(x1:0) The graph contains the following edges 1 > 1 ---------------------------------------- (116) YES ---------------------------------------- (117) Obligation: Rules: f313_in(T44) -> f315_in(T44) :|: TRUE f313_in(x) -> f314_in(x) :|: TRUE f314_out(x1) -> f313_out(x1) :|: TRUE f315_out(x2) -> f313_out(x2) :|: TRUE f315_in(x3) -> f337_in :|: TRUE f336_out(T67) -> f315_out(s(T67)) :|: TRUE f315_in(s(x4)) -> f336_in(x4) :|: TRUE f337_out -> f315_out(x5) :|: TRUE f313_out(x6) -> f264_out(x6) :|: TRUE f264_in(x7) -> f313_in(x7) :|: TRUE f264_out(x8) -> f336_out(x8) :|: TRUE f336_in(x9) -> f264_in(x9) :|: TRUE f143_out(T1) -> f1_out(T1) :|: TRUE f1_in(x10) -> f143_in(x10) :|: TRUE f143_in(x11) -> f144_in(x11) :|: TRUE f144_out(x12) -> f143_out(x12) :|: TRUE f145_out(x13) -> f143_out(x13) :|: TRUE f143_in(x14) -> f145_in(x14) :|: TRUE f216_out(x15) -> f145_out(x15) :|: TRUE f219_out(x16) -> f145_out(x16) :|: TRUE f145_in(x17) -> f219_in(x17) :|: TRUE f145_in(x18) -> f216_in(x18) :|: TRUE f219_in(x19) -> f253_in(x19) :|: TRUE f219_in(x20) -> f252_in(x20) :|: TRUE f253_out(x21) -> f219_out(x21) :|: TRUE f252_out(x22) -> f219_out(x22) :|: TRUE f260_out(x23) -> f252_out(x23) :|: TRUE f252_in(x24) -> f260_in(x24) :|: TRUE f252_in(x25) -> f261_in :|: TRUE f261_out -> f252_out(x26) :|: TRUE f260_in(x27) -> f264_in(x27) :|: TRUE f264_out(x28) -> f265_in(x28) :|: TRUE f265_out(x29) -> f260_out(x29) :|: TRUE Start term: f1_in(T1) ---------------------------------------- (118) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f313_in(T44) -> f315_in(T44) :|: TRUE f315_in(s(x4)) -> f336_in(x4) :|: TRUE f264_in(x7) -> f313_in(x7) :|: TRUE f336_in(x9) -> f264_in(x9) :|: TRUE ---------------------------------------- (119) Obligation: Rules: f313_in(T44) -> f315_in(T44) :|: TRUE f315_in(s(x4)) -> f336_in(x4) :|: TRUE f264_in(x7) -> f313_in(x7) :|: TRUE f336_in(x9) -> f264_in(x9) :|: TRUE ---------------------------------------- (120) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (121) Obligation: Rules: f264_in(s(x4:0)) -> f264_in(x4:0) :|: TRUE ---------------------------------------- (122) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (123) Obligation: Rules: f264_in(s(x4:0)) -> f264_in(x4:0) :|: TRUE ---------------------------------------- (124) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f264_in(s(x4:0)) -> f264_in(x4:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (125) Obligation: Termination digraph: Nodes: (1) f264_in(s(x4:0)) -> f264_in(x4:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (126) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f264_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (127) Obligation: Rules: f264_in(s(x4:0)) -> f264_in(x4:0) ---------------------------------------- (128) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (129) Obligation: Q DP problem: The TRS P consists of the following rules: f264_in(s(x4:0)) -> f264_in(x4:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (130) 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: *f264_in(s(x4:0)) -> f264_in(x4:0) The graph contains the following edges 1 > 1 ---------------------------------------- (131) YES ---------------------------------------- (132) Obligation: Rules: f219_in(T1) -> f253_in(T1) :|: TRUE f219_in(x) -> f252_in(x) :|: TRUE f253_out(x1) -> f219_out(x1) :|: TRUE f252_out(x2) -> f219_out(x2) :|: TRUE f345_in(s(T102)) -> f362_in :|: TRUE f363_out -> f345_out(T84) :|: TRUE f345_in(x3) -> f363_in :|: TRUE f362_out -> f345_out(s(x4)) :|: TRUE f143_out(x5) -> f1_out(x5) :|: TRUE f1_in(x6) -> f143_in(x6) :|: TRUE f367_in(T108) -> f342_in(T108) :|: TRUE f342_out(x7) -> f367_out(x7) :|: TRUE f315_in(T44) -> f337_in :|: TRUE f336_out(T67) -> f315_out(s(T67)) :|: TRUE f315_in(s(x8)) -> f336_in(x8) :|: TRUE f337_out -> f315_out(x9) :|: TRUE f143_in(x10) -> f144_in(x10) :|: TRUE f144_out(x11) -> f143_out(x11) :|: TRUE f145_out(x12) -> f143_out(x12) :|: TRUE f143_in(x13) -> f145_in(x13) :|: TRUE f313_out(x14) -> f264_out(x14) :|: TRUE f264_in(x15) -> f313_in(x15) :|: TRUE f342_in(x16) -> f344_in(x16) :|: TRUE f344_out(x17) -> f342_out(x17) :|: TRUE f216_out(x18) -> f145_out(x18) :|: TRUE f219_out(x19) -> f145_out(x19) :|: TRUE f145_in(x20) -> f219_in(x20) :|: TRUE f145_in(x21) -> f216_in(x21) :|: TRUE f343_out(x22) -> f340_out(x22) :|: TRUE f340_in(x23) -> f342_in(x23) :|: TRUE f342_out(x24) -> f343_in(x24) :|: TRUE f313_in(x25) -> f315_in(x25) :|: TRUE f313_in(x26) -> f314_in(x26) :|: TRUE f314_out(x27) -> f313_out(x27) :|: TRUE f315_out(x28) -> f313_out(x28) :|: TRUE f317_out -> f314_out(x29) :|: TRUE f314_in(0) -> f316_in :|: TRUE f316_out -> f314_out(0) :|: TRUE f314_in(x30) -> f317_in :|: TRUE f260_out(x31) -> f252_out(x31) :|: TRUE f252_in(x32) -> f260_in(x32) :|: TRUE f252_in(x33) -> f261_in :|: TRUE f261_out -> f252_out(x34) :|: TRUE f265_in(x35) -> f1_in(x35) :|: TRUE f1_out(x36) -> f265_out(x36) :|: TRUE f264_out(x37) -> f336_out(x37) :|: TRUE f336_in(x38) -> f264_in(x38) :|: TRUE f346_out(x39) -> f344_out(x39) :|: TRUE f344_in(x40) -> f345_in(x40) :|: TRUE f344_in(x41) -> f346_in(x41) :|: TRUE f345_out(x42) -> f344_out(x42) :|: TRUE f260_in(x43) -> f264_in(x43) :|: TRUE f264_out(x44) -> f265_in(x44) :|: TRUE f265_out(x45) -> f260_out(x45) :|: TRUE f253_in(x46) -> f340_in(x46) :|: TRUE f341_out -> f253_out(x47) :|: TRUE f340_out(x48) -> f253_out(x48) :|: TRUE f253_in(x49) -> f341_in :|: TRUE f368_out -> f346_out(x50) :|: TRUE f346_in(s(x51)) -> f367_in(x51) :|: TRUE f367_out(x52) -> f346_out(s(x52)) :|: TRUE f346_in(x53) -> f368_in :|: TRUE f362_in -> f362_out :|: TRUE f316_in -> f316_out :|: TRUE f343_in(x54) -> f1_in(x54) :|: TRUE f1_out(x55) -> f343_out(x55) :|: TRUE Start term: f1_in(T1) ---------------------------------------- (133) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f219_in(T1) -> f253_in(T1) :|: TRUE f219_in(x) -> f252_in(x) :|: TRUE f345_in(s(T102)) -> f362_in :|: TRUE f362_out -> f345_out(s(x4)) :|: TRUE f1_in(x6) -> f143_in(x6) :|: TRUE f367_in(T108) -> f342_in(T108) :|: TRUE f342_out(x7) -> f367_out(x7) :|: TRUE f336_out(T67) -> f315_out(s(T67)) :|: TRUE f315_in(s(x8)) -> f336_in(x8) :|: TRUE f143_in(x13) -> f145_in(x13) :|: TRUE f313_out(x14) -> f264_out(x14) :|: TRUE f264_in(x15) -> f313_in(x15) :|: TRUE f342_in(x16) -> f344_in(x16) :|: TRUE f344_out(x17) -> f342_out(x17) :|: TRUE f145_in(x20) -> f219_in(x20) :|: TRUE f340_in(x23) -> f342_in(x23) :|: TRUE f342_out(x24) -> f343_in(x24) :|: TRUE f313_in(x25) -> f315_in(x25) :|: TRUE f313_in(x26) -> f314_in(x26) :|: TRUE f314_out(x27) -> f313_out(x27) :|: TRUE f315_out(x28) -> f313_out(x28) :|: TRUE f314_in(0) -> f316_in :|: TRUE f316_out -> f314_out(0) :|: TRUE f252_in(x32) -> f260_in(x32) :|: TRUE f265_in(x35) -> f1_in(x35) :|: TRUE f264_out(x37) -> f336_out(x37) :|: TRUE f336_in(x38) -> f264_in(x38) :|: TRUE f346_out(x39) -> f344_out(x39) :|: TRUE f344_in(x40) -> f345_in(x40) :|: TRUE f344_in(x41) -> f346_in(x41) :|: TRUE f345_out(x42) -> f344_out(x42) :|: TRUE f260_in(x43) -> f264_in(x43) :|: TRUE f264_out(x44) -> f265_in(x44) :|: TRUE f253_in(x46) -> f340_in(x46) :|: TRUE f346_in(s(x51)) -> f367_in(x51) :|: TRUE f367_out(x52) -> f346_out(s(x52)) :|: TRUE f362_in -> f362_out :|: TRUE f316_in -> f316_out :|: TRUE f343_in(x54) -> f1_in(x54) :|: TRUE ---------------------------------------- (134) Obligation: Rules: f219_in(T1) -> f253_in(T1) :|: TRUE f219_in(x) -> f252_in(x) :|: TRUE f345_in(s(T102)) -> f362_in :|: TRUE f362_out -> f345_out(s(x4)) :|: TRUE f1_in(x6) -> f143_in(x6) :|: TRUE f367_in(T108) -> f342_in(T108) :|: TRUE f342_out(x7) -> f367_out(x7) :|: TRUE f336_out(T67) -> f315_out(s(T67)) :|: TRUE f315_in(s(x8)) -> f336_in(x8) :|: TRUE f143_in(x13) -> f145_in(x13) :|: TRUE f313_out(x14) -> f264_out(x14) :|: TRUE f264_in(x15) -> f313_in(x15) :|: TRUE f342_in(x16) -> f344_in(x16) :|: TRUE f344_out(x17) -> f342_out(x17) :|: TRUE f145_in(x20) -> f219_in(x20) :|: TRUE f340_in(x23) -> f342_in(x23) :|: TRUE f342_out(x24) -> f343_in(x24) :|: TRUE f313_in(x25) -> f315_in(x25) :|: TRUE f313_in(x26) -> f314_in(x26) :|: TRUE f314_out(x27) -> f313_out(x27) :|: TRUE f315_out(x28) -> f313_out(x28) :|: TRUE f314_in(0) -> f316_in :|: TRUE f316_out -> f314_out(0) :|: TRUE f252_in(x32) -> f260_in(x32) :|: TRUE f265_in(x35) -> f1_in(x35) :|: TRUE f264_out(x37) -> f336_out(x37) :|: TRUE f336_in(x38) -> f264_in(x38) :|: TRUE f346_out(x39) -> f344_out(x39) :|: TRUE f344_in(x40) -> f345_in(x40) :|: TRUE f344_in(x41) -> f346_in(x41) :|: TRUE f345_out(x42) -> f344_out(x42) :|: TRUE f260_in(x43) -> f264_in(x43) :|: TRUE f264_out(x44) -> f265_in(x44) :|: TRUE f253_in(x46) -> f340_in(x46) :|: TRUE f346_in(s(x51)) -> f367_in(x51) :|: TRUE f367_out(x52) -> f346_out(s(x52)) :|: TRUE f362_in -> f362_out :|: TRUE f316_in -> f316_out :|: TRUE f343_in(x54) -> f1_in(x54) :|: TRUE ---------------------------------------- (135) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (136) Obligation: Rules: f313_out(x14:0) -> f1_in(x14:0) :|: TRUE f264_in(s(x8:0)) -> f264_in(x8:0) :|: TRUE f313_out(x) -> f313_out(s(x)) :|: TRUE f344_in(s(T102:0)) -> f344_out(s(x4:0)) :|: TRUE f344_out(x17:0) -> f344_out(s(x17:0)) :|: TRUE f264_in(cons_0) -> f313_out(0) :|: TRUE && cons_0 = 0 f344_in(s(x51:0)) -> f344_in(x51:0) :|: TRUE f1_in(x6:0) -> f344_in(x6:0) :|: TRUE f344_out(x1) -> f1_in(x1) :|: TRUE f1_in(x2) -> f264_in(x2) :|: TRUE ---------------------------------------- (137) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (138) Obligation: Rules: f313_out(x14:0) -> f1_in(x14:0) :|: TRUE f264_in(s(x8:0)) -> f264_in(x8:0) :|: TRUE f313_out(x) -> f313_out(s(x)) :|: TRUE f344_in(s(T102:0)) -> f344_out(s(x4:0)) :|: TRUE f344_out(x17:0) -> f344_out(s(x17:0)) :|: TRUE f264_in(cons_0) -> f313_out(0) :|: TRUE && cons_0 = 0 f344_in(s(x51:0)) -> f344_in(x51:0) :|: TRUE f1_in(x6:0) -> f344_in(x6:0) :|: TRUE f344_out(x1) -> f1_in(x1) :|: TRUE f1_in(x2) -> f264_in(x2) :|: TRUE ---------------------------------------- (139) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(insert X (void) (tree X (void) (void)))", null ], [ "(insert X (tree X Left Right) (tree X Left Right))", null ], [ "(insert X (tree Y Left Right) (tree Y Left1 Right))", "(',' (less X Y) (insert X Left Left1))" ], [ "(insert X (tree Y Left Right) (tree Y Left Right1))", "(',' (less Y X) (insert X Right Right1))" ], [ "(less (0) (s X1))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "89": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }, { "clause": 3, "scope": 1, "term": "(insert T17 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "type": "Nodes", "470": { "goal": [ { "clause": 4, "scope": 9, "term": "(',' (less T315 T310) (insert T310 T316 T317))" }, { "clause": 5, "scope": 9, "term": "(',' (less T315 T310) (insert T310 T316 T317))" } ], "kb": { "nonunifying": [ [ "(insert T310 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T310 T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T310"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "471": { "goal": [{ "clause": 4, "scope": 9, "term": "(',' (less T315 T310) (insert T310 T316 T317))" }], "kb": { "nonunifying": [ [ "(insert T310 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T310 T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T310"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "472": { "goal": [{ "clause": 5, "scope": 9, "term": "(',' (less T315 T310) (insert T310 T316 T317))" }], "kb": { "nonunifying": [ [ "(insert T310 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T310 T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T310"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "473": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T322) T323 T324)" }], "kb": { "nonunifying": [ [ "(insert (s T322) T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert (s T322) T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T322"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "111": { "goal": [ { "clause": 4, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }, { "clause": 5, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T17 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "474": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "475": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T333 T332) (insert (s T332) T334 T335))" }], "kb": { "nonunifying": [ [ "(insert (s T332) T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert (s T332) T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T332"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "476": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "477": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (less T343 T348) (insert T343 T349 T350))" }, { "clause": 3, "scope": 1, "term": "(insert T343 T2 T3)" } ], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "478": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [ [ "(insert T1 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T1 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "479": { "goal": [ { "clause": 4, "scope": 10, "term": "(',' (less T343 T348) (insert T343 T349 T350))" }, { "clause": 5, "scope": 10, "term": "(',' (less T343 T348) (insert T343 T349 T350))" }, { "clause": -1, "scope": 10, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T343 T2 T3)" } ], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "480": { "goal": [{ "clause": 4, "scope": 10, "term": "(',' (less T343 T348) (insert T343 T349 T350))" }], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "481": { "goal": [ { "clause": 5, "scope": 10, "term": "(',' (less T343 T348) (insert T343 T349 T350))" }, { "clause": -1, "scope": 10, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T343 T2 T3)" } ], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "482": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T356 T357)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "483": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "484": { "goal": [{ "clause": 5, "scope": 10, "term": "(',' (less T343 T348) (insert T343 T349 T350))" }], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "485": { "goal": [ { "clause": -1, "scope": 10, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T343 T2 T3)" } ], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "486": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T366 T368) (insert (s T366) T369 T370))" }], "kb": { "nonunifying": [ [ "(insert (s T366) T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert (s T366) T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T366"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "487": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "400": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (less T153 T158) (insert T153 T159 T160))" }, { "clause": 3, "scope": 1, "term": "(insert T153 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "488": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T343 T2 T3)" }], "kb": { "nonunifying": [ [ "(insert T343 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T343 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T343"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "401": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T5 T2 T3)" }], "kb": { "nonunifying": [[ "(insert T5 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "489": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T388 T383) (insert T383 T389 T390))" }], "kb": { "nonunifying": [ [ "(insert T383 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T383 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T383"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "127": { "goal": [ { "clause": 5, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T17 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "369": { "goal": [ { "clause": 4, "scope": 4, "term": "(less T82 T77)" }, { "clause": 5, "scope": 4, "term": "(less T82 T77)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "402": { "goal": [ { "clause": 4, "scope": 6, "term": "(',' (less T153 T158) (insert T153 T159 T160))" }, { "clause": 5, "scope": 6, "term": "(',' (less T153 T158) (insert T153 T159 T160))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T153 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "403": { "goal": [{ "clause": 4, "scope": 6, "term": "(',' (less T153 T158) (insert T153 T159 T160))" }], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "404": { "goal": [ { "clause": 5, "scope": 6, "term": "(',' (less T153 T158) (insert T153 T159 T160))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T153 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "405": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T166 T167)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "406": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "407": { "goal": [{ "clause": 5, "scope": 6, "term": "(',' (less T153 T158) (insert T153 T159 T160))" }], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "408": { "goal": [ { "clause": -1, "scope": 6, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T153 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "409": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T176 T178) (insert (s T176) T179 T180))" }], "kb": { "nonunifying": [[ "(insert (s T176) T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T176"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "490": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "370": { "goal": [{ "clause": 4, "scope": 4, "term": "(less T82 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "491": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T403 T398) (insert T398 T404 T405))" }], "kb": { "nonunifying": [ [ "(insert T398 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T398 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T398"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "371": { "goal": [{ "clause": 5, "scope": 4, "term": "(less T82 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "492": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "372": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "493": { "goal": [ { "clause": 4, "scope": 11, "term": "(',' (less T403 T398) (insert T398 T404 T405))" }, { "clause": 5, "scope": 11, "term": "(',' (less T403 T398) (insert T398 T404 T405))" } ], "kb": { "nonunifying": [ [ "(insert T398 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T398 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T398"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "373": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "494": { "goal": [{ "clause": 4, "scope": 11, "term": "(',' (less T403 T398) (insert T398 T404 T405))" }], "kb": { "nonunifying": [ [ "(insert T398 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T398 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T398"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "132": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T30 T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "374": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "495": { "goal": [{ "clause": 5, "scope": 11, "term": "(',' (less T403 T398) (insert T398 T404 T405))" }], "kb": { "nonunifying": [ [ "(insert T398 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T398 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T398"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "133": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "375": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T102 T101)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T101"], "free": [], "exprvars": [] } }, "496": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T410) T411 T412)" }], "kb": { "nonunifying": [ [ "(insert (s T410) T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert (s T410) T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T410"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "376": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "497": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "377": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T117 T112) (insert T112 T118 T119))" }], "kb": { "nonunifying": [[ "(insert T112 T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T112"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "410": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "498": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T421 T420) (insert (s T420) T422 T423))" }], "kb": { "nonunifying": [ [ "(insert (s T420) T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert (s T420) T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T420"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "378": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "411": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T153 T2 T3)" }], "kb": { "nonunifying": [[ "(insert T153 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T153"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "499": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "379": { "goal": [ { "clause": 4, "scope": 5, "term": "(',' (less T117 T112) (insert T112 T118 T119))" }, { "clause": 5, "scope": 5, "term": "(',' (less T117 T112) (insert T112 T118 T119))" } ], "kb": { "nonunifying": [[ "(insert T112 T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T112"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "412": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T198 T193) (insert T193 T199 T200))" }], "kb": { "nonunifying": [[ "(insert T193 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T193"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "413": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "414": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T213 T208) (insert T208 T214 T215))" }], "kb": { "nonunifying": [[ "(insert T208 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T208"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "415": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "416": { "goal": [ { "clause": 4, "scope": 7, "term": "(',' (less T213 T208) (insert T208 T214 T215))" }, { "clause": 5, "scope": 7, "term": "(',' (less T213 T208) (insert T208 T214 T215))" } ], "kb": { "nonunifying": [[ "(insert T208 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T208"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "417": { "goal": [{ "clause": 4, "scope": 7, "term": "(',' (less T213 T208) (insert T208 T214 T215))" }], "kb": { "nonunifying": [[ "(insert T208 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T208"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "418": { "goal": [{ "clause": 5, "scope": 7, "term": "(',' (less T213 T208) (insert T208 T214 T215))" }], "kb": { "nonunifying": [[ "(insert T208 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T208"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "419": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T220) T221 T222)" }], "kb": { "nonunifying": [[ "(insert (s T220) T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T220"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "32": { "goal": [ { "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "33": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(insert T5 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T5 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T5 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "34": { "goal": [ { "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T1 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X3"], "exprvars": [] } }, "35": { "goal": [ { "clause": 1, "scope": 1, "term": "(insert T5 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(insert T5 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T5 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "36": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(insert T9 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T9 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "37": { "goal": [ { "clause": 2, "scope": 1, "term": "(insert T5 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T5 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T5 T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "38": { "goal": [ { "clause": 2, "scope": 1, "term": "(insert T9 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T9 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "380": { "goal": [{ "clause": 4, "scope": 5, "term": "(',' (less T117 T112) (insert T112 T118 T119))" }], "kb": { "nonunifying": [[ "(insert T112 T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T112"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "381": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (less T117 T112) (insert T112 T118 T119))" }], "kb": { "nonunifying": [[ "(insert T112 T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T112"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "382": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T124) T125 T126)" }], "kb": { "nonunifying": [[ "(insert (s T124) T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T124"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "383": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "384": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T135 T134) (insert (s T134) T136 T137))" }], "kb": { "nonunifying": [[ "(insert (s T134) T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T134"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "385": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "420": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "300": { "goal": [ { "clause": 4, "scope": 3, "term": "(less T40 T42)" }, { "clause": 5, "scope": 3, "term": "(less T40 T42)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "421": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T231 T230) (insert (s T230) T232 T233))" }], "kb": { "nonunifying": [[ "(insert (s T230) T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T230"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "301": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "422": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "302": { "goal": [{ "clause": 5, "scope": 3, "term": "(less T40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "423": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T231 T230)" }], "kb": { "nonunifying": [[ "(insert (s T230) T2 T3)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T230"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "303": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "424": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T230) T236 T237)" }], "kb": { "nonunifying": [[ "(insert (s T230) T238 T239)", "(insert X7 (tree X7 X8 X9) (tree X7 X8 X9))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T230"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "304": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "425": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(insert T247 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T247 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T247 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T247"], "free": ["X3"], "exprvars": [] } }, "305": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "426": { "goal": [ { "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" } ], "kb": { "nonunifying": [ [ "(insert T1 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T1 T2 T3)", "(insert X197 (tree X197 X198 X199) (tree X197 X198 X199))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X3", "X197", "X198", "X199" ], "exprvars": [] } }, "306": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T60 T62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T60"], "free": [], "exprvars": [] } }, "427": { "goal": [ { "clause": 2, "scope": 1, "term": "(insert T247 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(insert T247 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T247 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T247"], "free": ["X3"], "exprvars": [] } }, "307": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "308": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T17 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "309": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T82 T77) (insert T77 T83 T84))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "310": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "398": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T135 T134)" }], "kb": { "nonunifying": [[ "(insert (s T134) T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T134"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "311": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T82 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "399": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T134) T140 T141)" }], "kb": { "nonunifying": [[ "(insert (s T134) T142 T143)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T134"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "312": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T77 T87 T88)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "294": { "goal": [{ "clause": 5, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "295": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T17 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "296": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T40 T42) (insert (s T40) T43 T44))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "297": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "298": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "299": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (s T40) T47 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "454": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (less T255 T260) (insert T255 T261 T262))" }, { "clause": 3, "scope": 1, "term": "(insert T255 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "455": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T247 T2 T3)" }], "kb": { "nonunifying": [ [ "(insert T247 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T247 T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T247"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "456": { "goal": [ { "clause": 4, "scope": 8, "term": "(',' (less T255 T260) (insert T255 T261 T262))" }, { "clause": 5, "scope": 8, "term": "(',' (less T255 T260) (insert T255 T261 T262))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T255 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "457": { "goal": [{ "clause": 4, "scope": 8, "term": "(',' (less T255 T260) (insert T255 T261 T262))" }], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "458": { "goal": [ { "clause": 5, "scope": 8, "term": "(',' (less T255 T260) (insert T255 T261 T262))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T255 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "459": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T268 T269)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "460": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "461": { "goal": [{ "clause": 5, "scope": 8, "term": "(',' (less T255 T260) (insert T255 T261 T262))" }], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "462": { "goal": [ { "clause": -1, "scope": 8, "term": null }, { "clause": 3, "scope": 1, "term": "(insert T255 T2 T3)" } ], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "463": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T278 T280) (insert (s T278) T281 T282))" }], "kb": { "nonunifying": [[ "(insert (s T278) T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T278"], "free": ["X3"], "exprvars": [] } }, "101": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T9 T2 T3)" }], "kb": { "nonunifying": [[ "(insert T9 T2 T3)", "(insert X15 (tree X16 X17 X18) (tree X16 X19 X18))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X15", "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "464": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "465": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T255 T2 T3)" }], "kb": { "nonunifying": [[ "(insert T255 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T255"], "free": ["X3"], "exprvars": [] } }, "466": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T300 T295) (insert T295 T301 T302))" }], "kb": { "nonunifying": [[ "(insert T295 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T295"], "free": ["X3"], "exprvars": [] } }, "467": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "468": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T315 T310) (insert T310 T316 T317))" }], "kb": { "nonunifying": [ [ "(insert T310 T2 T3)", "(insert X3 (void) (tree X3 (void) (void)))" ], [ "(insert T310 T2 T3)", "(insert X205 (tree X206 X207 X208) (tree X206 X209 X208))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T310"], "free": [ "X3", "X205", "X206", "X207", "X208", "X209" ], "exprvars": [] } }, "469": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 32, "label": "CASE" }, { "from": 32, "to": 33, "label": "EVAL with clause\ninsert(X3, void, tree(X3, void, void)).\nand substitutionT1 -> T5,\nX3 -> T5,\nT2 -> void,\nT3 -> tree(T5, void, void)" }, { "from": 32, "to": 34, "label": "EVAL-BACKTRACK" }, { "from": 33, "to": 35, "label": "SUCCESS" }, { "from": 34, "to": 425, "label": "EVAL with clause\ninsert(X197, tree(X197, X198, X199), tree(X197, X198, X199)).\nand substitutionT1 -> T247,\nX197 -> T247,\nX198 -> T248,\nX199 -> T249,\nT2 -> tree(T247, T248, T249),\nT3 -> tree(T247, T248, T249)" }, { "from": 34, "to": 426, "label": "EVAL-BACKTRACK" }, { "from": 35, "to": 36, "label": "EVAL with clause\ninsert(X7, tree(X7, X8, X9), tree(X7, X8, X9)).\nand substitutionT5 -> T9,\nX7 -> T9,\nX8 -> T10,\nX9 -> T11,\nT2 -> tree(T9, T10, T11),\nT3 -> tree(T9, T10, T11)" }, { "from": 35, "to": 37, "label": "EVAL-BACKTRACK" }, { "from": 36, "to": 38, "label": "SUCCESS" }, { "from": 37, "to": 400, "label": "EVAL with clause\ninsert(X124, tree(X125, X126, X127), tree(X125, X128, X127)) :- ','(less(X124, X125), insert(X124, X126, X128)).\nand substitutionT5 -> T153,\nX124 -> T153,\nX125 -> T158,\nX126 -> T159,\nX127 -> T156,\nT2 -> tree(T158, T159, T156),\nX128 -> T160,\nT3 -> tree(T158, T160, T156),\nT154 -> T158,\nT155 -> T159,\nT157 -> T160" }, { "from": 37, "to": 401, "label": "EVAL-BACKTRACK" }, { "from": 38, "to": 89, "label": "EVAL with clause\ninsert(X15, tree(X16, X17, X18), tree(X16, X19, X18)) :- ','(less(X15, X16), insert(X15, X17, X19)).\nand substitutionT9 -> T17,\nX15 -> T17,\nX16 -> T22,\nX17 -> T23,\nX18 -> T20,\nT2 -> tree(T22, T23, T20),\nX19 -> T24,\nT3 -> tree(T22, T24, T20),\nT18 -> T22,\nT19 -> T23,\nT21 -> T24" }, { "from": 38, "to": 101, "label": "EVAL-BACKTRACK" }, { "from": 89, "to": 111, "label": "CASE" }, { "from": 101, "to": 377, "label": "EVAL with clause\ninsert(X95, tree(X96, X97, X98), tree(X96, X97, X99)) :- ','(less(X96, X95), insert(X95, X98, X99)).\nand substitutionT9 -> T112,\nX95 -> T112,\nX96 -> T117,\nX97 -> T114,\nX98 -> T118,\nT2 -> tree(T117, T114, T118),\nX99 -> T119,\nT3 -> tree(T117, T114, T119),\nT113 -> T117,\nT115 -> T118,\nT116 -> T119" }, { "from": 101, "to": 378, "label": "EVAL-BACKTRACK" }, { "from": 111, "to": 123, "label": "PARALLEL" }, { "from": 111, "to": 127, "label": "PARALLEL" }, { "from": 123, "to": 132, "label": "EVAL with clause\nless(0, s(X24)).\nand substitutionT17 -> 0,\nX24 -> T29,\nT22 -> s(T29),\nT23 -> T30,\nT24 -> T31" }, { "from": 123, "to": 133, "label": "EVAL-BACKTRACK" }, { "from": 127, "to": 294, "label": "PARALLEL" }, { "from": 127, "to": 295, "label": "PARALLEL" }, { "from": 132, "to": 2, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T30\nT3 -> T31" }, { "from": 294, "to": 296, "label": "EVAL with clause\nless(s(X35), s(X36)) :- less(X35, X36).\nand substitutionX35 -> T40,\nT17 -> s(T40),\nX36 -> T42,\nT22 -> s(T42),\nT41 -> T42,\nT23 -> T43,\nT24 -> T44" }, { "from": 294, "to": 297, "label": "EVAL-BACKTRACK" }, { "from": 295, "to": 308, "label": "FAILURE" }, { "from": 296, "to": 298, "label": "SPLIT 1" }, { "from": 296, "to": 299, "label": "SPLIT 2\nnew knowledge:\nT40 is ground\nreplacements:T43 -> T47,\nT44 -> T48" }, { "from": 298, "to": 300, "label": "CASE" }, { "from": 299, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T40)\nT2 -> T47\nT3 -> T48" }, { "from": 300, "to": 301, "label": "PARALLEL" }, { "from": 300, "to": 302, "label": "PARALLEL" }, { "from": 301, "to": 303, "label": "EVAL with clause\nless(0, s(X45)).\nand substitutionT40 -> 0,\nX45 -> T55,\nT42 -> s(T55)" }, { "from": 301, "to": 304, "label": "EVAL-BACKTRACK" }, { "from": 302, "to": 306, "label": "EVAL with clause\nless(s(X50), s(X51)) :- less(X50, X51).\nand substitutionX50 -> T60,\nT40 -> s(T60),\nX51 -> T62,\nT42 -> s(T62),\nT61 -> T62" }, { "from": 302, "to": 307, "label": "EVAL-BACKTRACK" }, { "from": 303, "to": 305, "label": "SUCCESS" }, { "from": 306, "to": 298, "label": "INSTANCE with matching:\nT40 -> T60\nT42 -> T62" }, { "from": 308, "to": 309, "label": "EVAL with clause\ninsert(X66, tree(X67, X68, X69), tree(X67, X68, X70)) :- ','(less(X67, X66), insert(X66, X69, X70)).\nand substitutionT17 -> T77,\nX66 -> T77,\nX67 -> T82,\nX68 -> T79,\nX69 -> T83,\nT2 -> tree(T82, T79, T83),\nX70 -> T84,\nT3 -> tree(T82, T79, T84),\nT78 -> T82,\nT80 -> T83,\nT81 -> T84" }, { "from": 308, "to": 310, "label": "EVAL-BACKTRACK" }, { "from": 309, "to": 311, "label": "SPLIT 1" }, { "from": 309, "to": 312, "label": "SPLIT 2\nnew knowledge:\nT82 is ground\nT77 is ground\nreplacements:T83 -> T87,\nT84 -> T88" }, { "from": 311, "to": 369, "label": "CASE" }, { "from": 312, "to": 2, "label": "INSTANCE with matching:\nT1 -> T77\nT2 -> T87\nT3 -> T88" }, { "from": 369, "to": 370, "label": "PARALLEL" }, { "from": 369, "to": 371, "label": "PARALLEL" }, { "from": 370, "to": 372, "label": "EVAL with clause\nless(0, s(X79)).\nand substitutionT82 -> 0,\nX79 -> T95,\nT77 -> s(T95)" }, { "from": 370, "to": 373, "label": "EVAL-BACKTRACK" }, { "from": 371, "to": 375, "label": "EVAL with clause\nless(s(X84), s(X85)) :- less(X84, X85).\nand substitutionX84 -> T102,\nT82 -> s(T102),\nX85 -> T101,\nT77 -> s(T101),\nT100 -> T102" }, { "from": 371, "to": 376, "label": "EVAL-BACKTRACK" }, { "from": 372, "to": 374, "label": "SUCCESS" }, { "from": 375, "to": 311, "label": "INSTANCE with matching:\nT82 -> T102\nT77 -> T101" }, { "from": 377, "to": 379, "label": "CASE" }, { "from": 379, "to": 380, "label": "PARALLEL" }, { "from": 379, "to": 381, "label": "PARALLEL" }, { "from": 380, "to": 382, "label": "EVAL with clause\nless(0, s(X104)).\nand substitutionT117 -> 0,\nX104 -> T124,\nT112 -> s(T124),\nT118 -> T125,\nT119 -> T126" }, { "from": 380, "to": 383, "label": "EVAL-BACKTRACK" }, { "from": 381, "to": 384, "label": "EVAL with clause\nless(s(X111), s(X112)) :- less(X111, X112).\nand substitutionX111 -> T135,\nT117 -> s(T135),\nX112 -> T134,\nT112 -> s(T134),\nT133 -> T135,\nT118 -> T136,\nT119 -> T137" }, { "from": 381, "to": 385, "label": "EVAL-BACKTRACK" }, { "from": 382, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T124)\nT2 -> T125\nT3 -> T126" }, { "from": 384, "to": 398, "label": "SPLIT 1" }, { "from": 384, "to": 399, "label": "SPLIT 2\nnew knowledge:\nT135 is ground\nT134 is ground\nreplacements:T136 -> T140,\nT137 -> T141,\nT2 -> T142,\nT3 -> T143" }, { "from": 398, "to": 311, "label": "INSTANCE with matching:\nT82 -> T135\nT77 -> T134" }, { "from": 399, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T134)\nT2 -> T140\nT3 -> T141" }, { "from": 400, "to": 402, "label": "CASE" }, { "from": 401, "to": 414, "label": "EVAL with clause\ninsert(X170, tree(X171, X172, X173), tree(X171, X172, X174)) :- ','(less(X171, X170), insert(X170, X173, X174)).\nand substitutionT5 -> T208,\nX170 -> T208,\nX171 -> T213,\nX172 -> T210,\nX173 -> T214,\nT2 -> tree(T213, T210, T214),\nX174 -> T215,\nT3 -> tree(T213, T210, T215),\nT209 -> T213,\nT211 -> T214,\nT212 -> T215" }, { "from": 401, "to": 415, "label": "EVAL-BACKTRACK" }, { "from": 402, "to": 403, "label": "PARALLEL" }, { "from": 402, "to": 404, "label": "PARALLEL" }, { "from": 403, "to": 405, "label": "EVAL with clause\nless(0, s(X133)).\nand substitutionT153 -> 0,\nX133 -> T165,\nT158 -> s(T165),\nT159 -> T166,\nT160 -> T167" }, { "from": 403, "to": 406, "label": "EVAL-BACKTRACK" }, { "from": 404, "to": 407, "label": "PARALLEL" }, { "from": 404, "to": 408, "label": "PARALLEL" }, { "from": 405, "to": 2, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T166\nT3 -> T167" }, { "from": 407, "to": 409, "label": "EVAL with clause\nless(s(X144), s(X145)) :- less(X144, X145).\nand substitutionX144 -> T176,\nT153 -> s(T176),\nX145 -> T178,\nT158 -> s(T178),\nT177 -> T178,\nT159 -> T179,\nT160 -> T180" }, { "from": 407, "to": 410, "label": "EVAL-BACKTRACK" }, { "from": 408, "to": 411, "label": "FAILURE" }, { "from": 409, "to": 296, "label": "INSTANCE with matching:\nT40 -> T176\nT42 -> T178\nT43 -> T179\nT44 -> T180" }, { "from": 411, "to": 412, "label": "EVAL with clause\ninsert(X158, tree(X159, X160, X161), tree(X159, X160, X162)) :- ','(less(X159, X158), insert(X158, X161, X162)).\nand substitutionT153 -> T193,\nX158 -> T193,\nX159 -> T198,\nX160 -> T195,\nX161 -> T199,\nT2 -> tree(T198, T195, T199),\nX162 -> T200,\nT3 -> tree(T198, T195, T200),\nT194 -> T198,\nT196 -> T199,\nT197 -> T200" }, { "from": 411, "to": 413, "label": "EVAL-BACKTRACK" }, { "from": 412, "to": 309, "label": "INSTANCE with matching:\nT82 -> T198\nT77 -> T193\nT83 -> T199\nT84 -> T200" }, { "from": 414, "to": 416, "label": "CASE" }, { "from": 416, "to": 417, "label": "PARALLEL" }, { "from": 416, "to": 418, "label": "PARALLEL" }, { "from": 417, "to": 419, "label": "EVAL with clause\nless(0, s(X179)).\nand substitutionT213 -> 0,\nX179 -> T220,\nT208 -> s(T220),\nT214 -> T221,\nT215 -> T222" }, { "from": 417, "to": 420, "label": "EVAL-BACKTRACK" }, { "from": 418, "to": 421, "label": "EVAL with clause\nless(s(X186), s(X187)) :- less(X186, X187).\nand substitutionX186 -> T231,\nT213 -> s(T231),\nX187 -> T230,\nT208 -> s(T230),\nT229 -> T231,\nT214 -> T232,\nT215 -> T233" }, { "from": 418, "to": 422, "label": "EVAL-BACKTRACK" }, { "from": 419, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T220)\nT2 -> T221\nT3 -> T222" }, { "from": 421, "to": 423, "label": "SPLIT 1" }, { "from": 421, "to": 424, "label": "SPLIT 2\nnew knowledge:\nT231 is ground\nT230 is ground\nreplacements:T232 -> T236,\nT233 -> T237,\nT2 -> T238,\nT3 -> T239" }, { "from": 423, "to": 311, "label": "INSTANCE with matching:\nT82 -> T231\nT77 -> T230" }, { "from": 424, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T230)\nT2 -> T236\nT3 -> T237" }, { "from": 425, "to": 427, "label": "SUCCESS" }, { "from": 426, "to": 477, "label": "EVAL with clause\ninsert(X276, tree(X277, X278, X279), tree(X277, X280, X279)) :- ','(less(X276, X277), insert(X276, X278, X280)).\nand substitutionT1 -> T343,\nX276 -> T343,\nX277 -> T348,\nX278 -> T349,\nX279 -> T346,\nT2 -> tree(T348, T349, T346),\nX280 -> T350,\nT3 -> tree(T348, T350, T346),\nT344 -> T348,\nT345 -> T349,\nT347 -> T350" }, { "from": 426, "to": 478, "label": "EVAL-BACKTRACK" }, { "from": 427, "to": 454, "label": "EVAL with clause\ninsert(X205, tree(X206, X207, X208), tree(X206, X209, X208)) :- ','(less(X205, X206), insert(X205, X207, X209)).\nand substitutionT247 -> T255,\nX205 -> T255,\nX206 -> T260,\nX207 -> T261,\nX208 -> T258,\nT2 -> tree(T260, T261, T258),\nX209 -> T262,\nT3 -> tree(T260, T262, T258),\nT256 -> T260,\nT257 -> T261,\nT259 -> T262" }, { "from": 427, "to": 455, "label": "EVAL-BACKTRACK" }, { "from": 454, "to": 456, "label": "CASE" }, { "from": 455, "to": 468, "label": "EVAL with clause\ninsert(X251, tree(X252, X253, X254), tree(X252, X253, X255)) :- ','(less(X252, X251), insert(X251, X254, X255)).\nand substitutionT247 -> T310,\nX251 -> T310,\nX252 -> T315,\nX253 -> T312,\nX254 -> T316,\nT2 -> tree(T315, T312, T316),\nX255 -> T317,\nT3 -> tree(T315, T312, T317),\nT311 -> T315,\nT313 -> T316,\nT314 -> T317" }, { "from": 455, "to": 469, "label": "EVAL-BACKTRACK" }, { "from": 456, "to": 457, "label": "PARALLEL" }, { "from": 456, "to": 458, "label": "PARALLEL" }, { "from": 457, "to": 459, "label": "EVAL with clause\nless(0, s(X214)).\nand substitutionT255 -> 0,\nX214 -> T267,\nT260 -> s(T267),\nT261 -> T268,\nT262 -> T269" }, { "from": 457, "to": 460, "label": "EVAL-BACKTRACK" }, { "from": 458, "to": 461, "label": "PARALLEL" }, { "from": 458, "to": 462, "label": "PARALLEL" }, { "from": 459, "to": 2, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T268\nT3 -> T269" }, { "from": 461, "to": 463, "label": "EVAL with clause\nless(s(X225), s(X226)) :- less(X225, X226).\nand substitutionX225 -> T278,\nT255 -> s(T278),\nX226 -> T280,\nT260 -> s(T280),\nT279 -> T280,\nT261 -> T281,\nT262 -> T282" }, { "from": 461, "to": 464, "label": "EVAL-BACKTRACK" }, { "from": 462, "to": 465, "label": "FAILURE" }, { "from": 463, "to": 296, "label": "INSTANCE with matching:\nT40 -> T278\nT42 -> T280\nT43 -> T281\nT44 -> T282" }, { "from": 465, "to": 466, "label": "EVAL with clause\ninsert(X239, tree(X240, X241, X242), tree(X240, X241, X243)) :- ','(less(X240, X239), insert(X239, X242, X243)).\nand substitutionT255 -> T295,\nX239 -> T295,\nX240 -> T300,\nX241 -> T297,\nX242 -> T301,\nT2 -> tree(T300, T297, T301),\nX243 -> T302,\nT3 -> tree(T300, T297, T302),\nT296 -> T300,\nT298 -> T301,\nT299 -> T302" }, { "from": 465, "to": 467, "label": "EVAL-BACKTRACK" }, { "from": 466, "to": 309, "label": "INSTANCE with matching:\nT82 -> T300\nT77 -> T295\nT83 -> T301\nT84 -> T302" }, { "from": 468, "to": 470, "label": "CASE" }, { "from": 470, "to": 471, "label": "PARALLEL" }, { "from": 470, "to": 472, "label": "PARALLEL" }, { "from": 471, "to": 473, "label": "EVAL with clause\nless(0, s(X260)).\nand substitutionT315 -> 0,\nX260 -> T322,\nT310 -> s(T322),\nT316 -> T323,\nT317 -> T324" }, { "from": 471, "to": 474, "label": "EVAL-BACKTRACK" }, { "from": 472, "to": 475, "label": "EVAL with clause\nless(s(X267), s(X268)) :- less(X267, X268).\nand substitutionX267 -> T333,\nT315 -> s(T333),\nX268 -> T332,\nT310 -> s(T332),\nT331 -> T333,\nT316 -> T334,\nT317 -> T335" }, { "from": 472, "to": 476, "label": "EVAL-BACKTRACK" }, { "from": 473, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T322)\nT2 -> T323\nT3 -> T324" }, { "from": 475, "to": 384, "label": "INSTANCE with matching:\nT135 -> T333\nT134 -> T332\nT136 -> T334\nT137 -> T335\nX15 -> X205\nX16 -> X206\nX17 -> X207\nX18 -> X208\nX19 -> X209" }, { "from": 477, "to": 479, "label": "CASE" }, { "from": 478, "to": 491, "label": "EVAL with clause\ninsert(X322, tree(X323, X324, X325), tree(X323, X324, X326)) :- ','(less(X323, X322), insert(X322, X325, X326)).\nand substitutionT1 -> T398,\nX322 -> T398,\nX323 -> T403,\nX324 -> T400,\nX325 -> T404,\nT2 -> tree(T403, T400, T404),\nX326 -> T405,\nT3 -> tree(T403, T400, T405),\nT399 -> T403,\nT401 -> T404,\nT402 -> T405" }, { "from": 478, "to": 492, "label": "EVAL-BACKTRACK" }, { "from": 479, "to": 480, "label": "PARALLEL" }, { "from": 479, "to": 481, "label": "PARALLEL" }, { "from": 480, "to": 482, "label": "EVAL with clause\nless(0, s(X285)).\nand substitutionT343 -> 0,\nX285 -> T355,\nT348 -> s(T355),\nT349 -> T356,\nT350 -> T357" }, { "from": 480, "to": 483, "label": "EVAL-BACKTRACK" }, { "from": 481, "to": 484, "label": "PARALLEL" }, { "from": 481, "to": 485, "label": "PARALLEL" }, { "from": 482, "to": 2, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T356\nT3 -> T357" }, { "from": 484, "to": 486, "label": "EVAL with clause\nless(s(X296), s(X297)) :- less(X296, X297).\nand substitutionX296 -> T366,\nT343 -> s(T366),\nX297 -> T368,\nT348 -> s(T368),\nT367 -> T368,\nT349 -> T369,\nT350 -> T370" }, { "from": 484, "to": 487, "label": "EVAL-BACKTRACK" }, { "from": 485, "to": 488, "label": "FAILURE" }, { "from": 486, "to": 296, "label": "INSTANCE with matching:\nT40 -> T366\nT42 -> T368\nT43 -> T369\nT44 -> T370" }, { "from": 488, "to": 489, "label": "EVAL with clause\ninsert(X310, tree(X311, X312, X313), tree(X311, X312, X314)) :- ','(less(X311, X310), insert(X310, X313, X314)).\nand substitutionT343 -> T383,\nX310 -> T383,\nX311 -> T388,\nX312 -> T385,\nX313 -> T389,\nT2 -> tree(T388, T385, T389),\nX314 -> T390,\nT3 -> tree(T388, T385, T390),\nT384 -> T388,\nT386 -> T389,\nT387 -> T390" }, { "from": 488, "to": 490, "label": "EVAL-BACKTRACK" }, { "from": 489, "to": 414, "label": "INSTANCE with matching:\nT213 -> T388\nT208 -> T383\nT214 -> T389\nT215 -> T390\nX7 -> X197\nX8 -> X198\nX9 -> X199" }, { "from": 491, "to": 493, "label": "CASE" }, { "from": 493, "to": 494, "label": "PARALLEL" }, { "from": 493, "to": 495, "label": "PARALLEL" }, { "from": 494, "to": 496, "label": "EVAL with clause\nless(0, s(X331)).\nand substitutionT403 -> 0,\nX331 -> T410,\nT398 -> s(T410),\nT404 -> T411,\nT405 -> T412" }, { "from": 494, "to": 497, "label": "EVAL-BACKTRACK" }, { "from": 495, "to": 498, "label": "EVAL with clause\nless(s(X338), s(X339)) :- less(X338, X339).\nand substitutionX338 -> T421,\nT403 -> s(T421),\nX339 -> T420,\nT398 -> s(T420),\nT419 -> T421,\nT404 -> T422,\nT405 -> T423" }, { "from": 495, "to": 499, "label": "EVAL-BACKTRACK" }, { "from": 496, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T410)\nT2 -> T411\nT3 -> T412" }, { "from": 498, "to": 421, "label": "INSTANCE with matching:\nT231 -> T421\nT230 -> T420\nT232 -> T422\nT233 -> T423\nX7 -> X197\nX8 -> X198\nX9 -> X199" } ], "type": "Graph" } } ---------------------------------------- (140) Obligation: Triples: lessG(s(X1), s(X2)) :- lessG(X1, X2). lessH(s(X1), s(X2)) :- lessH(X1, X2). pB(X1, X2, X3, X4) :- lessG(X1, X2). pB(X1, X2, X3, X4) :- ','(lesscG(X1, X2), insertA(s(X1), X3, X4)). pC(X1, X2, X3, X4) :- lessH(X1, X2). pC(X1, X2, X3, X4) :- ','(lesscH(X1, X2), insertA(X2, X3, X4)). pD(X1, X2, X3, X4) :- lessH(X1, X2). pD(X1, X2, X3, X4) :- ','(lesscH(X1, X2), insertA(s(X2), X3, X4)). pE(0, s(X1), X2, X3) :- insertA(s(X1), X2, X3). pE(s(X1), s(X2), X3, X4) :- pF(X1, X2, X3, X4). pF(X1, X2, X3, X4) :- lessH(X1, X2). pF(X1, X2, X3, X4) :- ','(lesscH(X1, X2), insertA(s(X2), X3, X4)). insertA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertA(0, X2, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- pB(X1, X2, X3, X5). insertA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- pC(X2, X1, X4, X5). insertA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- insertA(s(X1), X3, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- pD(X2, X1, X4, X5). insertA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertA(0, X2, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- pB(X1, X2, X3, X5). insertA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- pC(X2, X1, X4, X5). insertA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- pE(X2, X1, X4, X5). insertA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertA(0, X2, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- pB(X1, X2, X3, X5). insertA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- pC(X2, X1, X4, X5). insertA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- insertA(s(X1), X3, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- pD(X2, X1, X4, X5). insertA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertA(0, X2, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- pB(X1, X2, X3, X5). insertA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- pE(X2, X1, X4, X5). insertA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- insertA(s(X1), X3, X4). insertA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- pF(X2, X1, X4, X5). Clauses: insertcA(X1, void, tree(X1, void, void)). insertcA(X1, tree(X1, X2, X3), tree(X1, X2, X3)). insertcA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertcA(0, X2, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- qcB(X1, X2, X3, X5). insertcA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- qcC(X2, X1, X4, X5). insertcA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- insertcA(s(X1), X3, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- qcD(X2, X1, X4, X5). insertcA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertcA(0, X2, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- qcB(X1, X2, X3, X5). insertcA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- qcC(X2, X1, X4, X5). insertcA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- qcE(X2, X1, X4, X5). insertcA(X1, tree(X1, X2, X3), tree(X1, X2, X3)). insertcA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertcA(0, X2, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- qcB(X1, X2, X3, X5). insertcA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- qcC(X2, X1, X4, X5). insertcA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- insertcA(s(X1), X3, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- qcD(X2, X1, X4, X5). insertcA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- insertcA(0, X2, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- qcB(X1, X2, X3, X5). insertcA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- qcE(X2, X1, X4, X5). insertcA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- insertcA(s(X1), X3, X4). insertcA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- qcF(X2, X1, X4, X5). lesscG(0, s(X1)). lesscG(s(X1), s(X2)) :- lesscG(X1, X2). lesscH(0, s(X1)). lesscH(s(X1), s(X2)) :- lesscH(X1, X2). qcB(X1, X2, X3, X4) :- ','(lesscG(X1, X2), insertcA(s(X1), X3, X4)). qcC(X1, X2, X3, X4) :- ','(lesscH(X1, X2), insertcA(X2, X3, X4)). qcD(X1, X2, X3, X4) :- ','(lesscH(X1, X2), insertcA(s(X2), X3, X4)). qcE(0, s(X1), X2, X3) :- insertcA(s(X1), X2, X3). qcE(s(X1), s(X2), X3, X4) :- qcF(X1, X2, X3, X4). qcF(X1, X2, X3, X4) :- ','(lesscH(X1, X2), insertcA(s(X2), X3, X4)). Afs: insertA(x1, x2, x3) = insertA(x1) ---------------------------------------- (141) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: insertA_in_3: (b,f,f) pB_in_4: (b,f,f,f) lessG_in_2: (b,f) lesscG_in_2: (b,f) pC_in_4: (f,b,f,f) lessH_in_2: (f,b) lesscH_in_2: (f,b) pD_in_4: (f,b,f,f) pE_in_4: (f,b,f,f) pF_in_4: (f,b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) -> U17_GAA(X1, X2, X3, X4, insertA_in_gaa(0, X2, X4)) INSERTA_IN_GAA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) -> INSERTA_IN_GAA(0, X2, X4) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) -> U18_GAA(X1, X2, X3, X4, X5, pB_in_gaaa(X1, X2, X3, X5)) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) -> PB_IN_GAAA(X1, X2, X3, X5) PB_IN_GAAA(X1, X2, X3, X4) -> U3_GAAA(X1, X2, X3, X4, lessG_in_ga(X1, X2)) PB_IN_GAAA(X1, X2, X3, X4) -> LESSG_IN_GA(X1, X2) LESSG_IN_GA(s(X1), s(X2)) -> U1_GA(X1, X2, lessG_in_ga(X1, X2)) LESSG_IN_GA(s(X1), s(X2)) -> LESSG_IN_GA(X1, X2) PB_IN_GAAA(X1, X2, X3, X4) -> U4_GAAA(X1, X2, X3, X4, lesscG_in_ga(X1, X2)) U4_GAAA(X1, X2, X3, X4, lesscG_out_ga(X1, X2)) -> U5_GAAA(X1, X2, X3, X4, insertA_in_gaa(s(X1), X3, X4)) U4_GAAA(X1, X2, X3, X4, lesscG_out_ga(X1, X2)) -> INSERTA_IN_GAA(s(X1), X3, X4) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> U19_GAA(X1, X2, X3, X4, X5, pC_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> PC_IN_AGAA(X2, X1, X4, X5) PC_IN_AGAA(X1, X2, X3, X4) -> U6_AGAA(X1, X2, X3, X4, lessH_in_ag(X1, X2)) PC_IN_AGAA(X1, X2, X3, X4) -> LESSH_IN_AG(X1, X2) LESSH_IN_AG(s(X1), s(X2)) -> U2_AG(X1, X2, lessH_in_ag(X1, X2)) LESSH_IN_AG(s(X1), s(X2)) -> LESSH_IN_AG(X1, X2) PC_IN_AGAA(X1, X2, X3, X4) -> U7_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U7_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> U8_AGAA(X1, X2, X3, X4, insertA_in_gaa(X2, X3, X4)) U7_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2, X3, X4) INSERTA_IN_GAA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) -> U20_GAA(X1, X2, X3, X4, insertA_in_gaa(s(X1), X3, X4)) INSERTA_IN_GAA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) -> INSERTA_IN_GAA(s(X1), X3, X4) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> U21_GAA(X1, X2, X3, X4, X5, pD_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> PD_IN_AGAA(X2, X1, X4, X5) PD_IN_AGAA(X1, X2, X3, X4) -> U9_AGAA(X1, X2, X3, X4, lessH_in_ag(X1, X2)) PD_IN_AGAA(X1, X2, X3, X4) -> LESSH_IN_AG(X1, X2) PD_IN_AGAA(X1, X2, X3, X4) -> U10_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U10_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> U11_AGAA(X1, X2, X3, X4, insertA_in_gaa(s(X2), X3, X4)) U10_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2), X3, X4) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> U22_GAA(X1, X2, X3, X4, X5, pE_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> PE_IN_AGAA(X2, X1, X4, X5) PE_IN_AGAA(0, s(X1), X2, X3) -> U12_AGAA(X1, X2, X3, insertA_in_gaa(s(X1), X2, X3)) PE_IN_AGAA(0, s(X1), X2, X3) -> INSERTA_IN_GAA(s(X1), X2, X3) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> U23_GAA(X1, X2, X3, X4, X5, pF_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> PF_IN_AGAA(X2, X1, X4, X5) PF_IN_AGAA(X1, X2, X3, X4) -> U14_AGAA(X1, X2, X3, X4, lessH_in_ag(X1, X2)) PF_IN_AGAA(X1, X2, X3, X4) -> LESSH_IN_AG(X1, X2) PF_IN_AGAA(X1, X2, X3, X4) -> U15_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U15_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> U16_AGAA(X1, X2, X3, X4, insertA_in_gaa(s(X2), X3, X4)) U15_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2), X3, X4) PE_IN_AGAA(s(X1), s(X2), X3, X4) -> U13_AGAA(X1, X2, X3, X4, pF_in_agaa(X1, X2, X3, X4)) PE_IN_AGAA(s(X1), s(X2), X3, X4) -> PF_IN_AGAA(X1, X2, X3, X4) The TRS R consists of the following rules: lesscG_in_ga(0, s(X1)) -> lesscG_out_ga(0, s(X1)) lesscG_in_ga(s(X1), s(X2)) -> U32_ga(X1, X2, lesscG_in_ga(X1, X2)) U32_ga(X1, X2, lesscG_out_ga(X1, X2)) -> lesscG_out_ga(s(X1), s(X2)) lesscH_in_ag(0, s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X1), s(X2)) -> U33_ag(X1, X2, lesscH_in_ag(X1, X2)) U33_ag(X1, X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: insertA_in_gaa(x1, x2, x3) = insertA_in_gaa(x1) 0 = 0 s(x1) = s(x1) pB_in_gaaa(x1, x2, x3, x4) = pB_in_gaaa(x1) lessG_in_ga(x1, x2) = lessG_in_ga(x1) lesscG_in_ga(x1, x2) = lesscG_in_ga(x1) lesscG_out_ga(x1, x2) = lesscG_out_ga(x1) U32_ga(x1, x2, x3) = U32_ga(x1, x3) pC_in_agaa(x1, x2, x3, x4) = pC_in_agaa(x2) lessH_in_ag(x1, x2) = lessH_in_ag(x2) lesscH_in_ag(x1, x2) = lesscH_in_ag(x2) lesscH_out_ag(x1, x2) = lesscH_out_ag(x1, x2) U33_ag(x1, x2, x3) = U33_ag(x2, x3) pD_in_agaa(x1, x2, x3, x4) = pD_in_agaa(x2) pE_in_agaa(x1, x2, x3, x4) = pE_in_agaa(x2) pF_in_agaa(x1, x2, x3, x4) = pF_in_agaa(x2) INSERTA_IN_GAA(x1, x2, x3) = INSERTA_IN_GAA(x1) U17_GAA(x1, x2, x3, x4, x5) = U17_GAA(x5) U18_GAA(x1, x2, x3, x4, x5, x6) = U18_GAA(x1, x6) PB_IN_GAAA(x1, x2, x3, x4) = PB_IN_GAAA(x1) U3_GAAA(x1, x2, x3, x4, x5) = U3_GAAA(x1, x5) LESSG_IN_GA(x1, x2) = LESSG_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) U4_GAAA(x1, x2, x3, x4, x5) = U4_GAAA(x1, x5) U5_GAAA(x1, x2, x3, x4, x5) = U5_GAAA(x1, x5) U19_GAA(x1, x2, x3, x4, x5, x6) = U19_GAA(x1, x6) PC_IN_AGAA(x1, x2, x3, x4) = PC_IN_AGAA(x2) U6_AGAA(x1, x2, x3, x4, x5) = U6_AGAA(x2, x5) LESSH_IN_AG(x1, x2) = LESSH_IN_AG(x2) U2_AG(x1, x2, x3) = U2_AG(x2, x3) U7_AGAA(x1, x2, x3, x4, x5) = U7_AGAA(x2, x5) U8_AGAA(x1, x2, x3, x4, x5) = U8_AGAA(x1, x2, x5) U20_GAA(x1, x2, x3, x4, x5) = U20_GAA(x1, x5) U21_GAA(x1, x2, x3, x4, x5, x6) = U21_GAA(x1, x6) PD_IN_AGAA(x1, x2, x3, x4) = PD_IN_AGAA(x2) U9_AGAA(x1, x2, x3, x4, x5) = U9_AGAA(x2, x5) U10_AGAA(x1, x2, x3, x4, x5) = U10_AGAA(x2, x5) U11_AGAA(x1, x2, x3, x4, x5) = U11_AGAA(x1, x2, x5) U22_GAA(x1, x2, x3, x4, x5, x6) = U22_GAA(x1, x6) PE_IN_AGAA(x1, x2, x3, x4) = PE_IN_AGAA(x2) U12_AGAA(x1, x2, x3, x4) = U12_AGAA(x1, x4) U23_GAA(x1, x2, x3, x4, x5, x6) = U23_GAA(x1, x6) PF_IN_AGAA(x1, x2, x3, x4) = PF_IN_AGAA(x2) U14_AGAA(x1, x2, x3, x4, x5) = U14_AGAA(x2, x5) U15_AGAA(x1, x2, x3, x4, x5) = U15_AGAA(x2, x5) U16_AGAA(x1, x2, x3, x4, x5) = U16_AGAA(x1, x2, x5) U13_AGAA(x1, x2, x3, x4, x5) = U13_AGAA(x2, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (142) Obligation: Pi DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) -> U17_GAA(X1, X2, X3, X4, insertA_in_gaa(0, X2, X4)) INSERTA_IN_GAA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) -> INSERTA_IN_GAA(0, X2, X4) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) -> U18_GAA(X1, X2, X3, X4, X5, pB_in_gaaa(X1, X2, X3, X5)) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) -> PB_IN_GAAA(X1, X2, X3, X5) PB_IN_GAAA(X1, X2, X3, X4) -> U3_GAAA(X1, X2, X3, X4, lessG_in_ga(X1, X2)) PB_IN_GAAA(X1, X2, X3, X4) -> LESSG_IN_GA(X1, X2) LESSG_IN_GA(s(X1), s(X2)) -> U1_GA(X1, X2, lessG_in_ga(X1, X2)) LESSG_IN_GA(s(X1), s(X2)) -> LESSG_IN_GA(X1, X2) PB_IN_GAAA(X1, X2, X3, X4) -> U4_GAAA(X1, X2, X3, X4, lesscG_in_ga(X1, X2)) U4_GAAA(X1, X2, X3, X4, lesscG_out_ga(X1, X2)) -> U5_GAAA(X1, X2, X3, X4, insertA_in_gaa(s(X1), X3, X4)) U4_GAAA(X1, X2, X3, X4, lesscG_out_ga(X1, X2)) -> INSERTA_IN_GAA(s(X1), X3, X4) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> U19_GAA(X1, X2, X3, X4, X5, pC_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> PC_IN_AGAA(X2, X1, X4, X5) PC_IN_AGAA(X1, X2, X3, X4) -> U6_AGAA(X1, X2, X3, X4, lessH_in_ag(X1, X2)) PC_IN_AGAA(X1, X2, X3, X4) -> LESSH_IN_AG(X1, X2) LESSH_IN_AG(s(X1), s(X2)) -> U2_AG(X1, X2, lessH_in_ag(X1, X2)) LESSH_IN_AG(s(X1), s(X2)) -> LESSH_IN_AG(X1, X2) PC_IN_AGAA(X1, X2, X3, X4) -> U7_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U7_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> U8_AGAA(X1, X2, X3, X4, insertA_in_gaa(X2, X3, X4)) U7_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2, X3, X4) INSERTA_IN_GAA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) -> U20_GAA(X1, X2, X3, X4, insertA_in_gaa(s(X1), X3, X4)) INSERTA_IN_GAA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) -> INSERTA_IN_GAA(s(X1), X3, X4) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> U21_GAA(X1, X2, X3, X4, X5, pD_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> PD_IN_AGAA(X2, X1, X4, X5) PD_IN_AGAA(X1, X2, X3, X4) -> U9_AGAA(X1, X2, X3, X4, lessH_in_ag(X1, X2)) PD_IN_AGAA(X1, X2, X3, X4) -> LESSH_IN_AG(X1, X2) PD_IN_AGAA(X1, X2, X3, X4) -> U10_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U10_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> U11_AGAA(X1, X2, X3, X4, insertA_in_gaa(s(X2), X3, X4)) U10_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2), X3, X4) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> U22_GAA(X1, X2, X3, X4, X5, pE_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> PE_IN_AGAA(X2, X1, X4, X5) PE_IN_AGAA(0, s(X1), X2, X3) -> U12_AGAA(X1, X2, X3, insertA_in_gaa(s(X1), X2, X3)) PE_IN_AGAA(0, s(X1), X2, X3) -> INSERTA_IN_GAA(s(X1), X2, X3) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> U23_GAA(X1, X2, X3, X4, X5, pF_in_agaa(X2, X1, X4, X5)) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> PF_IN_AGAA(X2, X1, X4, X5) PF_IN_AGAA(X1, X2, X3, X4) -> U14_AGAA(X1, X2, X3, X4, lessH_in_ag(X1, X2)) PF_IN_AGAA(X1, X2, X3, X4) -> LESSH_IN_AG(X1, X2) PF_IN_AGAA(X1, X2, X3, X4) -> U15_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U15_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> U16_AGAA(X1, X2, X3, X4, insertA_in_gaa(s(X2), X3, X4)) U15_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2), X3, X4) PE_IN_AGAA(s(X1), s(X2), X3, X4) -> U13_AGAA(X1, X2, X3, X4, pF_in_agaa(X1, X2, X3, X4)) PE_IN_AGAA(s(X1), s(X2), X3, X4) -> PF_IN_AGAA(X1, X2, X3, X4) The TRS R consists of the following rules: lesscG_in_ga(0, s(X1)) -> lesscG_out_ga(0, s(X1)) lesscG_in_ga(s(X1), s(X2)) -> U32_ga(X1, X2, lesscG_in_ga(X1, X2)) U32_ga(X1, X2, lesscG_out_ga(X1, X2)) -> lesscG_out_ga(s(X1), s(X2)) lesscH_in_ag(0, s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X1), s(X2)) -> U33_ag(X1, X2, lesscH_in_ag(X1, X2)) U33_ag(X1, X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: insertA_in_gaa(x1, x2, x3) = insertA_in_gaa(x1) 0 = 0 s(x1) = s(x1) pB_in_gaaa(x1, x2, x3, x4) = pB_in_gaaa(x1) lessG_in_ga(x1, x2) = lessG_in_ga(x1) lesscG_in_ga(x1, x2) = lesscG_in_ga(x1) lesscG_out_ga(x1, x2) = lesscG_out_ga(x1) U32_ga(x1, x2, x3) = U32_ga(x1, x3) pC_in_agaa(x1, x2, x3, x4) = pC_in_agaa(x2) lessH_in_ag(x1, x2) = lessH_in_ag(x2) lesscH_in_ag(x1, x2) = lesscH_in_ag(x2) lesscH_out_ag(x1, x2) = lesscH_out_ag(x1, x2) U33_ag(x1, x2, x3) = U33_ag(x2, x3) pD_in_agaa(x1, x2, x3, x4) = pD_in_agaa(x2) pE_in_agaa(x1, x2, x3, x4) = pE_in_agaa(x2) pF_in_agaa(x1, x2, x3, x4) = pF_in_agaa(x2) INSERTA_IN_GAA(x1, x2, x3) = INSERTA_IN_GAA(x1) U17_GAA(x1, x2, x3, x4, x5) = U17_GAA(x5) U18_GAA(x1, x2, x3, x4, x5, x6) = U18_GAA(x1, x6) PB_IN_GAAA(x1, x2, x3, x4) = PB_IN_GAAA(x1) U3_GAAA(x1, x2, x3, x4, x5) = U3_GAAA(x1, x5) LESSG_IN_GA(x1, x2) = LESSG_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) U4_GAAA(x1, x2, x3, x4, x5) = U4_GAAA(x1, x5) U5_GAAA(x1, x2, x3, x4, x5) = U5_GAAA(x1, x5) U19_GAA(x1, x2, x3, x4, x5, x6) = U19_GAA(x1, x6) PC_IN_AGAA(x1, x2, x3, x4) = PC_IN_AGAA(x2) U6_AGAA(x1, x2, x3, x4, x5) = U6_AGAA(x2, x5) LESSH_IN_AG(x1, x2) = LESSH_IN_AG(x2) U2_AG(x1, x2, x3) = U2_AG(x2, x3) U7_AGAA(x1, x2, x3, x4, x5) = U7_AGAA(x2, x5) U8_AGAA(x1, x2, x3, x4, x5) = U8_AGAA(x1, x2, x5) U20_GAA(x1, x2, x3, x4, x5) = U20_GAA(x1, x5) U21_GAA(x1, x2, x3, x4, x5, x6) = U21_GAA(x1, x6) PD_IN_AGAA(x1, x2, x3, x4) = PD_IN_AGAA(x2) U9_AGAA(x1, x2, x3, x4, x5) = U9_AGAA(x2, x5) U10_AGAA(x1, x2, x3, x4, x5) = U10_AGAA(x2, x5) U11_AGAA(x1, x2, x3, x4, x5) = U11_AGAA(x1, x2, x5) U22_GAA(x1, x2, x3, x4, x5, x6) = U22_GAA(x1, x6) PE_IN_AGAA(x1, x2, x3, x4) = PE_IN_AGAA(x2) U12_AGAA(x1, x2, x3, x4) = U12_AGAA(x1, x4) U23_GAA(x1, x2, x3, x4, x5, x6) = U23_GAA(x1, x6) PF_IN_AGAA(x1, x2, x3, x4) = PF_IN_AGAA(x2) U14_AGAA(x1, x2, x3, x4, x5) = U14_AGAA(x2, x5) U15_AGAA(x1, x2, x3, x4, x5) = U15_AGAA(x2, x5) U16_AGAA(x1, x2, x3, x4, x5) = U16_AGAA(x1, x2, x5) U13_AGAA(x1, x2, x3, x4, x5) = U13_AGAA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (143) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 23 less nodes. ---------------------------------------- (144) Complex Obligation (AND) ---------------------------------------- (145) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSH_IN_AG(s(X1), s(X2)) -> LESSH_IN_AG(X1, X2) The TRS R consists of the following rules: lesscG_in_ga(0, s(X1)) -> lesscG_out_ga(0, s(X1)) lesscG_in_ga(s(X1), s(X2)) -> U32_ga(X1, X2, lesscG_in_ga(X1, X2)) U32_ga(X1, X2, lesscG_out_ga(X1, X2)) -> lesscG_out_ga(s(X1), s(X2)) lesscH_in_ag(0, s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X1), s(X2)) -> U33_ag(X1, X2, lesscH_in_ag(X1, X2)) U33_ag(X1, X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: 0 = 0 s(x1) = s(x1) lesscG_in_ga(x1, x2) = lesscG_in_ga(x1) lesscG_out_ga(x1, x2) = lesscG_out_ga(x1) U32_ga(x1, x2, x3) = U32_ga(x1, x3) lesscH_in_ag(x1, x2) = lesscH_in_ag(x2) lesscH_out_ag(x1, x2) = lesscH_out_ag(x1, x2) U33_ag(x1, x2, x3) = U33_ag(x2, x3) LESSH_IN_AG(x1, x2) = LESSH_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (146) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (147) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSH_IN_AG(s(X1), s(X2)) -> LESSH_IN_AG(X1, X2) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESSH_IN_AG(x1, x2) = LESSH_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (148) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (149) Obligation: Q DP problem: The TRS P consists of the following rules: LESSH_IN_AG(s(X2)) -> LESSH_IN_AG(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (150) 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: *LESSH_IN_AG(s(X2)) -> LESSH_IN_AG(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (151) YES ---------------------------------------- (152) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSG_IN_GA(s(X1), s(X2)) -> LESSG_IN_GA(X1, X2) The TRS R consists of the following rules: lesscG_in_ga(0, s(X1)) -> lesscG_out_ga(0, s(X1)) lesscG_in_ga(s(X1), s(X2)) -> U32_ga(X1, X2, lesscG_in_ga(X1, X2)) U32_ga(X1, X2, lesscG_out_ga(X1, X2)) -> lesscG_out_ga(s(X1), s(X2)) lesscH_in_ag(0, s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X1), s(X2)) -> U33_ag(X1, X2, lesscH_in_ag(X1, X2)) U33_ag(X1, X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: 0 = 0 s(x1) = s(x1) lesscG_in_ga(x1, x2) = lesscG_in_ga(x1) lesscG_out_ga(x1, x2) = lesscG_out_ga(x1) U32_ga(x1, x2, x3) = U32_ga(x1, x3) lesscH_in_ag(x1, x2) = lesscH_in_ag(x2) lesscH_out_ag(x1, x2) = lesscH_out_ag(x1, x2) U33_ag(x1, x2, x3) = U33_ag(x2, x3) LESSG_IN_GA(x1, x2) = LESSG_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (153) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (154) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSG_IN_GA(s(X1), s(X2)) -> LESSG_IN_GA(X1, X2) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESSG_IN_GA(x1, x2) = LESSG_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (155) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (156) Obligation: Q DP problem: The TRS P consists of the following rules: LESSG_IN_GA(s(X1)) -> LESSG_IN_GA(X1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (157) 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: *LESSG_IN_GA(s(X1)) -> LESSG_IN_GA(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (158) YES ---------------------------------------- (159) Obligation: Pi DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> PC_IN_AGAA(X2, X1, X4, X5) PC_IN_AGAA(X1, X2, X3, X4) -> U7_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U7_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2, X3, X4) INSERTA_IN_GAA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) -> INSERTA_IN_GAA(0, X2, X4) INSERTA_IN_GAA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) -> PE_IN_AGAA(X2, X1, X4, X5) PE_IN_AGAA(0, s(X1), X2, X3) -> INSERTA_IN_GAA(s(X1), X2, X3) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) -> PB_IN_GAAA(X1, X2, X3, X5) PB_IN_GAAA(X1, X2, X3, X4) -> U4_GAAA(X1, X2, X3, X4, lesscG_in_ga(X1, X2)) U4_GAAA(X1, X2, X3, X4, lesscG_out_ga(X1, X2)) -> INSERTA_IN_GAA(s(X1), X3, X4) INSERTA_IN_GAA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) -> INSERTA_IN_GAA(s(X1), X3, X4) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> PD_IN_AGAA(X2, X1, X4, X5) PD_IN_AGAA(X1, X2, X3, X4) -> U10_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U10_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2), X3, X4) INSERTA_IN_GAA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) -> PF_IN_AGAA(X2, X1, X4, X5) PF_IN_AGAA(X1, X2, X3, X4) -> U15_AGAA(X1, X2, X3, X4, lesscH_in_ag(X1, X2)) U15_AGAA(X1, X2, X3, X4, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2), X3, X4) PE_IN_AGAA(s(X1), s(X2), X3, X4) -> PF_IN_AGAA(X1, X2, X3, X4) The TRS R consists of the following rules: lesscG_in_ga(0, s(X1)) -> lesscG_out_ga(0, s(X1)) lesscG_in_ga(s(X1), s(X2)) -> U32_ga(X1, X2, lesscG_in_ga(X1, X2)) U32_ga(X1, X2, lesscG_out_ga(X1, X2)) -> lesscG_out_ga(s(X1), s(X2)) lesscH_in_ag(0, s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X1), s(X2)) -> U33_ag(X1, X2, lesscH_in_ag(X1, X2)) U33_ag(X1, X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: 0 = 0 s(x1) = s(x1) lesscG_in_ga(x1, x2) = lesscG_in_ga(x1) lesscG_out_ga(x1, x2) = lesscG_out_ga(x1) U32_ga(x1, x2, x3) = U32_ga(x1, x3) lesscH_in_ag(x1, x2) = lesscH_in_ag(x2) lesscH_out_ag(x1, x2) = lesscH_out_ag(x1, x2) U33_ag(x1, x2, x3) = U33_ag(x2, x3) INSERTA_IN_GAA(x1, x2, x3) = INSERTA_IN_GAA(x1) PB_IN_GAAA(x1, x2, x3, x4) = PB_IN_GAAA(x1) U4_GAAA(x1, x2, x3, x4, x5) = U4_GAAA(x1, x5) PC_IN_AGAA(x1, x2, x3, x4) = PC_IN_AGAA(x2) U7_AGAA(x1, x2, x3, x4, x5) = U7_AGAA(x2, x5) PD_IN_AGAA(x1, x2, x3, x4) = PD_IN_AGAA(x2) U10_AGAA(x1, x2, x3, x4, x5) = U10_AGAA(x2, x5) PE_IN_AGAA(x1, x2, x3, x4) = PE_IN_AGAA(x2) PF_IN_AGAA(x1, x2, x3, x4) = PF_IN_AGAA(x2) U15_AGAA(x1, x2, x3, x4, x5) = U15_AGAA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (160) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (161) Obligation: Q DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(X1) -> PC_IN_AGAA(X1) PC_IN_AGAA(X2) -> U7_AGAA(X2, lesscH_in_ag(X2)) U7_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2) INSERTA_IN_GAA(0) -> INSERTA_IN_GAA(0) INSERTA_IN_GAA(X1) -> PE_IN_AGAA(X1) PE_IN_AGAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PB_IN_GAAA(X1) PB_IN_GAAA(X1) -> U4_GAAA(X1, lesscG_in_ga(X1)) U4_GAAA(X1, lesscG_out_ga(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PD_IN_AGAA(X1) PD_IN_AGAA(X2) -> U10_AGAA(X2, lesscH_in_ag(X2)) U10_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) INSERTA_IN_GAA(s(X1)) -> PF_IN_AGAA(X1) PF_IN_AGAA(X2) -> U15_AGAA(X2, lesscH_in_ag(X2)) U15_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) PE_IN_AGAA(s(X2)) -> PF_IN_AGAA(X2) The TRS R consists of the following rules: lesscG_in_ga(0) -> lesscG_out_ga(0) lesscG_in_ga(s(X1)) -> U32_ga(X1, lesscG_in_ga(X1)) U32_ga(X1, lesscG_out_ga(X1)) -> lesscG_out_ga(s(X1)) lesscH_in_ag(s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X2)) -> U33_ag(X2, lesscH_in_ag(X2)) U33_ag(X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The set Q consists of the following terms: lesscG_in_ga(x0) U32_ga(x0, x1) lesscH_in_ag(x0) U33_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (162) TransformationProof (SOUND) By narrowing [LPAR04] the rule PC_IN_AGAA(X2) -> U7_AGAA(X2, lesscH_in_ag(X2)) at position [1] we obtained the following new rules [LPAR04]: (PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), lesscH_out_ag(0, s(x0))),PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), lesscH_out_ag(0, s(x0)))) (PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))),PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0)))) ---------------------------------------- (163) Obligation: Q DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(X1) -> PC_IN_AGAA(X1) U7_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2) INSERTA_IN_GAA(0) -> INSERTA_IN_GAA(0) INSERTA_IN_GAA(X1) -> PE_IN_AGAA(X1) PE_IN_AGAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PB_IN_GAAA(X1) PB_IN_GAAA(X1) -> U4_GAAA(X1, lesscG_in_ga(X1)) U4_GAAA(X1, lesscG_out_ga(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PD_IN_AGAA(X1) PD_IN_AGAA(X2) -> U10_AGAA(X2, lesscH_in_ag(X2)) U10_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) INSERTA_IN_GAA(s(X1)) -> PF_IN_AGAA(X1) PF_IN_AGAA(X2) -> U15_AGAA(X2, lesscH_in_ag(X2)) U15_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) PE_IN_AGAA(s(X2)) -> PF_IN_AGAA(X2) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) The TRS R consists of the following rules: lesscG_in_ga(0) -> lesscG_out_ga(0) lesscG_in_ga(s(X1)) -> U32_ga(X1, lesscG_in_ga(X1)) U32_ga(X1, lesscG_out_ga(X1)) -> lesscG_out_ga(s(X1)) lesscH_in_ag(s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X2)) -> U33_ag(X2, lesscH_in_ag(X2)) U33_ag(X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The set Q consists of the following terms: lesscG_in_ga(x0) U32_ga(x0, x1) lesscH_in_ag(x0) U33_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (164) TransformationProof (SOUND) By narrowing [LPAR04] the rule PB_IN_GAAA(X1) -> U4_GAAA(X1, lesscG_in_ga(X1)) at position [1] we obtained the following new rules [LPAR04]: (PB_IN_GAAA(0) -> U4_GAAA(0, lesscG_out_ga(0)),PB_IN_GAAA(0) -> U4_GAAA(0, lesscG_out_ga(0))) (PB_IN_GAAA(s(x0)) -> U4_GAAA(s(x0), U32_ga(x0, lesscG_in_ga(x0))),PB_IN_GAAA(s(x0)) -> U4_GAAA(s(x0), U32_ga(x0, lesscG_in_ga(x0)))) ---------------------------------------- (165) Obligation: Q DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(X1) -> PC_IN_AGAA(X1) U7_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2) INSERTA_IN_GAA(0) -> INSERTA_IN_GAA(0) INSERTA_IN_GAA(X1) -> PE_IN_AGAA(X1) PE_IN_AGAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PB_IN_GAAA(X1) U4_GAAA(X1, lesscG_out_ga(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PD_IN_AGAA(X1) PD_IN_AGAA(X2) -> U10_AGAA(X2, lesscH_in_ag(X2)) U10_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) INSERTA_IN_GAA(s(X1)) -> PF_IN_AGAA(X1) PF_IN_AGAA(X2) -> U15_AGAA(X2, lesscH_in_ag(X2)) U15_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) PE_IN_AGAA(s(X2)) -> PF_IN_AGAA(X2) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) PB_IN_GAAA(0) -> U4_GAAA(0, lesscG_out_ga(0)) PB_IN_GAAA(s(x0)) -> U4_GAAA(s(x0), U32_ga(x0, lesscG_in_ga(x0))) The TRS R consists of the following rules: lesscG_in_ga(0) -> lesscG_out_ga(0) lesscG_in_ga(s(X1)) -> U32_ga(X1, lesscG_in_ga(X1)) U32_ga(X1, lesscG_out_ga(X1)) -> lesscG_out_ga(s(X1)) lesscH_in_ag(s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X2)) -> U33_ag(X2, lesscH_in_ag(X2)) U33_ag(X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The set Q consists of the following terms: lesscG_in_ga(x0) U32_ga(x0, x1) lesscH_in_ag(x0) U33_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (166) TransformationProof (SOUND) By narrowing [LPAR04] the rule PD_IN_AGAA(X2) -> U10_AGAA(X2, lesscH_in_ag(X2)) at position [1] we obtained the following new rules [LPAR04]: (PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), lesscH_out_ag(0, s(x0))),PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), lesscH_out_ag(0, s(x0)))) (PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))),PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0)))) ---------------------------------------- (167) Obligation: Q DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(X1) -> PC_IN_AGAA(X1) U7_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2) INSERTA_IN_GAA(0) -> INSERTA_IN_GAA(0) INSERTA_IN_GAA(X1) -> PE_IN_AGAA(X1) PE_IN_AGAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PB_IN_GAAA(X1) U4_GAAA(X1, lesscG_out_ga(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PD_IN_AGAA(X1) U10_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) INSERTA_IN_GAA(s(X1)) -> PF_IN_AGAA(X1) PF_IN_AGAA(X2) -> U15_AGAA(X2, lesscH_in_ag(X2)) U15_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) PE_IN_AGAA(s(X2)) -> PF_IN_AGAA(X2) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) PB_IN_GAAA(0) -> U4_GAAA(0, lesscG_out_ga(0)) PB_IN_GAAA(s(x0)) -> U4_GAAA(s(x0), U32_ga(x0, lesscG_in_ga(x0))) PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) The TRS R consists of the following rules: lesscG_in_ga(0) -> lesscG_out_ga(0) lesscG_in_ga(s(X1)) -> U32_ga(X1, lesscG_in_ga(X1)) U32_ga(X1, lesscG_out_ga(X1)) -> lesscG_out_ga(s(X1)) lesscH_in_ag(s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X2)) -> U33_ag(X2, lesscH_in_ag(X2)) U33_ag(X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The set Q consists of the following terms: lesscG_in_ga(x0) U32_ga(x0, x1) lesscH_in_ag(x0) U33_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (168) TransformationProof (SOUND) By narrowing [LPAR04] the rule PF_IN_AGAA(X2) -> U15_AGAA(X2, lesscH_in_ag(X2)) at position [1] we obtained the following new rules [LPAR04]: (PF_IN_AGAA(s(x0)) -> U15_AGAA(s(x0), lesscH_out_ag(0, s(x0))),PF_IN_AGAA(s(x0)) -> U15_AGAA(s(x0), lesscH_out_ag(0, s(x0)))) (PF_IN_AGAA(s(x0)) -> U15_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))),PF_IN_AGAA(s(x0)) -> U15_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0)))) ---------------------------------------- (169) Obligation: Q DP problem: The TRS P consists of the following rules: INSERTA_IN_GAA(X1) -> PC_IN_AGAA(X1) U7_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(X2) INSERTA_IN_GAA(0) -> INSERTA_IN_GAA(0) INSERTA_IN_GAA(X1) -> PE_IN_AGAA(X1) PE_IN_AGAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PB_IN_GAAA(X1) U4_GAAA(X1, lesscG_out_ga(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> INSERTA_IN_GAA(s(X1)) INSERTA_IN_GAA(s(X1)) -> PD_IN_AGAA(X1) U10_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) INSERTA_IN_GAA(s(X1)) -> PF_IN_AGAA(X1) U15_AGAA(X2, lesscH_out_ag(X1, X2)) -> INSERTA_IN_GAA(s(X2)) PE_IN_AGAA(s(X2)) -> PF_IN_AGAA(X2) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PC_IN_AGAA(s(x0)) -> U7_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) PB_IN_GAAA(0) -> U4_GAAA(0, lesscG_out_ga(0)) PB_IN_GAAA(s(x0)) -> U4_GAAA(s(x0), U32_ga(x0, lesscG_in_ga(x0))) PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PD_IN_AGAA(s(x0)) -> U10_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) PF_IN_AGAA(s(x0)) -> U15_AGAA(s(x0), lesscH_out_ag(0, s(x0))) PF_IN_AGAA(s(x0)) -> U15_AGAA(s(x0), U33_ag(x0, lesscH_in_ag(x0))) The TRS R consists of the following rules: lesscG_in_ga(0) -> lesscG_out_ga(0) lesscG_in_ga(s(X1)) -> U32_ga(X1, lesscG_in_ga(X1)) U32_ga(X1, lesscG_out_ga(X1)) -> lesscG_out_ga(s(X1)) lesscH_in_ag(s(X1)) -> lesscH_out_ag(0, s(X1)) lesscH_in_ag(s(X2)) -> U33_ag(X2, lesscH_in_ag(X2)) U33_ag(X2, lesscH_out_ag(X1, X2)) -> lesscH_out_ag(s(X1), s(X2)) The set Q consists of the following terms: lesscG_in_ga(x0) U32_ga(x0, x1) lesscH_in_ag(x0) U33_ag(x0, x1) We have to consider all (P,Q,R)-chains.