MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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, 10 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) PrologToPiTRSProof [SOUND, 0 ms] (27) PiTRS (28) DependencyPairsProof [EQUIVALENT, 4 ms] (29) PiDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) AND (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES (39) PiDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) PiDP (42) PiDPToQDPProof [SOUND, 0 ms] (43) QDP (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] (45) YES (46) PiDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) PiDP (49) PiDPToQDPProof [SOUND, 1 ms] (50) QDP (51) TransformationProof [SOUND, 0 ms] (52) QDP (53) TransformationProof [SOUND, 0 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 0 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) AND (59) QDP (60) UsableRulesProof [EQUIVALENT, 0 ms] (61) QDP (62) QReductionProof [EQUIVALENT, 0 ms] (63) QDP (64) NonTerminationLoopProof [COMPLETE, 0 ms] (65) NO (66) QDP (67) TransformationProof [EQUIVALENT, 0 ms] (68) QDP (69) PrologToTRSTransformerProof [SOUND, 0 ms] (70) QTRS (71) DependencyPairsProof [EQUIVALENT, 0 ms] (72) QDP (73) DependencyGraphProof [EQUIVALENT, 0 ms] (74) AND (75) QDP (76) UsableRulesProof [EQUIVALENT, 0 ms] (77) QDP (78) QDPSizeChangeProof [EQUIVALENT, 0 ms] (79) YES (80) QDP (81) UsableRulesProof [EQUIVALENT, 0 ms] (82) QDP (83) QDPSizeChangeProof [EQUIVALENT, 0 ms] (84) YES (85) QDP (86) NonTerminationLoopProof [COMPLETE, 0 ms] (87) NO (88) PrologToIRSwTTransformerProof [SOUND, 35 ms] (89) AND (90) IRSwT (91) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (92) IRSwT (93) IntTRSCompressionProof [EQUIVALENT, 0 ms] (94) IRSwT (95) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (96) IRSwT (97) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (98) IRSwT (99) TempFilterProof [SOUND, 3 ms] (100) IRSwT (101) IRSwTToQDPProof [SOUND, 0 ms] (102) QDP (103) QDPSizeChangeProof [EQUIVALENT, 0 ms] (104) YES (105) IRSwT (106) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (107) IRSwT (108) IntTRSCompressionProof [EQUIVALENT, 0 ms] (109) IRSwT (110) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (111) IRSwT (112) IRSwTTerminationDigraphProof [EQUIVALENT, 2 ms] (113) IRSwT (114) TempFilterProof [SOUND, 1 ms] (115) IRSwT (116) IRSwTToQDPProof [SOUND, 0 ms] (117) QDP (118) QDPSizeChangeProof [EQUIVALENT, 0 ms] (119) YES (120) IRSwT (121) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (122) IRSwT (123) IntTRSCompressionProof [EQUIVALENT, 20 ms] (124) IRSwT (125) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (126) IRSwT (127) IRSwTTerminationDigraphProof [EQUIVALENT, 42 ms] (128) IRSwT (129) IntTRSCompressionProof [EQUIVALENT, 14 ms] (130) IRSwT (131) IRSwTToIntTRSProof [SOUND, 22 ms] (132) IRSwT (133) PrologToDTProblemTransformerProof [SOUND, 102 ms] (134) TRIPLES (135) TriplesToPiDPProof [SOUND, 9 ms] (136) PiDP (137) DependencyGraphProof [EQUIVALENT, 0 ms] (138) AND (139) PiDP (140) UsableRulesProof [EQUIVALENT, 0 ms] (141) PiDP (142) PiDPToQDPProof [SOUND, 0 ms] (143) QDP (144) QDPSizeChangeProof [EQUIVALENT, 0 ms] (145) YES (146) PiDP (147) UsableRulesProof [EQUIVALENT, 0 ms] (148) PiDP (149) PiDPToQDPProof [SOUND, 0 ms] (150) QDP (151) QDPSizeChangeProof [EQUIVALENT, 0 ms] (152) YES (153) PiDP (154) PiDPToQDPProof [SOUND, 0 ms] (155) 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) 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 ---------------------------------------- (27) 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) ---------------------------------------- (28) 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 ---------------------------------------- (29) 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 ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (31) Complex Obligation (AND) ---------------------------------------- (32) 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 ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (35) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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 ---------------------------------------- (38) YES ---------------------------------------- (39) 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 ---------------------------------------- (40) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (41) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (42) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: LESS_IN_GA(s(X)) -> LESS_IN_GA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (44) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LESS_IN_GA(s(X)) -> LESS_IN_GA(X) The graph contains the following edges 1 > 1 ---------------------------------------- (45) YES ---------------------------------------- (46) 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 ---------------------------------------- (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: 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 ---------------------------------------- (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: 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. ---------------------------------------- (51) 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)))) ---------------------------------------- (52) 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. ---------------------------------------- (53) 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)))) ---------------------------------------- (54) 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. ---------------------------------------- (55) 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))) ---------------------------------------- (56) 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. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (58) Complex Obligation (AND) ---------------------------------------- (59) 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. ---------------------------------------- (60) 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. ---------------------------------------- (61) 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. ---------------------------------------- (62) 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) ---------------------------------------- (63) 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. ---------------------------------------- (64) 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 = INSERT_IN_GAA(0) evaluates to t =INSERT_IN_GAA(0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) with rule INSERT_IN_GAA(0) -> U1_GAA(0, less_out_ga) at position [] and matcher [ ] U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0) with rule U1_GAA(0, less_out_ga) -> INSERT_IN_GAA(0) 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. ---------------------------------------- (65) NO ---------------------------------------- (66) 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. ---------------------------------------- (67) 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))) ---------------------------------------- (68) 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. ---------------------------------------- (69) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 5, "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": { "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "150": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "293": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "130": { "goal": [{ "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "131": { "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": [] } }, "330": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "276": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "277": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T44 T54 T55)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "137": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "138": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "139": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T84 T94 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "338": { "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": [] } }, "15": { "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": [] } }, "280": { "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": [] } }, "140": { "goal": [{ "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "141": { "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": [] } }, "284": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "285": { "goal": [{ "clause": 5, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "341": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "144": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "342": { "goal": [{ "clause": 5, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "145": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "343": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "289": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "300": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T67 T69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T67"], "free": [], "exprvars": [] } }, "344": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "147": { "goal": [{ "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "301": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "345": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "148": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T109 T108)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T108"], "free": [], "exprvars": [] } }, "149": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T44 T49) (insert T44 T50 T51))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "347": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "328": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T89 T84) (insert T84 T90 T91))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 15, "label": "CASE" }, { "from": 15, "to": 130, "label": "PARALLEL" }, { "from": 15, "to": 131, "label": "PARALLEL" }, { "from": 130, "to": 137, "label": "EVAL with clause\ninsert(X6, void, tree(X6, void, void)).\nand substitutionT1 -> T8,\nX6 -> T8,\nT2 -> void,\nT3 -> tree(T8, void, void)" }, { "from": 130, "to": 138, "label": "EVAL-BACKTRACK" }, { "from": 131, "to": 140, "label": "PARALLEL" }, { "from": 131, "to": 141, "label": "PARALLEL" }, { "from": 137, "to": 139, "label": "SUCCESS" }, { "from": 140, "to": 144, "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": 140, "to": 145, "label": "EVAL-BACKTRACK" }, { "from": 141, "to": 147, "label": "PARALLEL" }, { "from": 141, "to": 148, "label": "PARALLEL" }, { "from": 144, "to": 146, "label": "SUCCESS" }, { "from": 147, "to": 149, "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": 147, "to": 150, "label": "EVAL-BACKTRACK" }, { "from": 148, "to": 328, "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": 148, "to": 330, "label": "EVAL-BACKTRACK" }, { "from": 149, "to": 276, "label": "SPLIT 1" }, { "from": 149, "to": 277, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nreplacements:T50 -> T54,\nT51 -> T55" }, { "from": 276, "to": 280, "label": "CASE" }, { "from": 277, "to": 5, "label": "INSTANCE with matching:\nT1 -> T44\nT2 -> T54\nT3 -> T55" }, { "from": 280, "to": 284, "label": "PARALLEL" }, { "from": 280, "to": 285, "label": "PARALLEL" }, { "from": 284, "to": 289, "label": "EVAL with clause\nless(0, s(X55)).\nand substitutionT44 -> 0,\nX55 -> T62,\nT49 -> s(T62)" }, { "from": 284, "to": 292, "label": "EVAL-BACKTRACK" }, { "from": 285, "to": 300, "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": 285, "to": 301, "label": "EVAL-BACKTRACK" }, { "from": 289, "to": 293, "label": "SUCCESS" }, { "from": 300, "to": 276, "label": "INSTANCE with matching:\nT44 -> T67\nT49 -> T69" }, { "from": 328, "to": 335, "label": "SPLIT 1" }, { "from": 328, "to": 337, "label": "SPLIT 2\nnew knowledge:\nT89 is ground\nT84 is ground\nreplacements:T90 -> T94,\nT91 -> T95" }, { "from": 335, "to": 338, "label": "CASE" }, { "from": 337, "to": 5, "label": "INSTANCE with matching:\nT1 -> T84\nT2 -> T94\nT3 -> T95" }, { "from": 338, "to": 341, "label": "PARALLEL" }, { "from": 338, "to": 342, "label": "PARALLEL" }, { "from": 341, "to": 343, "label": "EVAL with clause\nless(0, s(X89)).\nand substitutionT89 -> 0,\nX89 -> T102,\nT84 -> s(T102)" }, { "from": 341, "to": 344, "label": "EVAL-BACKTRACK" }, { "from": 342, "to": 346, "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": 342, "to": 347, "label": "EVAL-BACKTRACK" }, { "from": 343, "to": 345, "label": "SUCCESS" }, { "from": 346, "to": 335, "label": "INSTANCE with matching:\nT89 -> T109\nT84 -> T108" } ], "type": "Graph" } } ---------------------------------------- (70) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in(T8) -> f5_out1 f5_in(T44) -> U1(f149_in(T44), T44) U1(f149_out1, T44) -> f5_out1 f5_in(T84) -> U2(f328_in(T84), T84) U2(f328_out1(T89), T84) -> f5_out1 f276_in(0) -> f276_out1 f276_in(s(T67)) -> U3(f276_in(T67), s(T67)) U3(f276_out1, s(T67)) -> f276_out1 f335_in(s(T102)) -> f335_out1(0) f335_in(s(T108)) -> U4(f335_in(T108), s(T108)) U4(f335_out1(T109), s(T108)) -> f335_out1(s(T109)) f149_in(T44) -> U5(f276_in(T44), T44) U5(f276_out1, T44) -> U6(f5_in(T44), T44) U6(f5_out1, T44) -> f149_out1 f328_in(T84) -> U7(f335_in(T84), T84) U7(f335_out1(T89), T84) -> U8(f5_in(T84), T84, T89) U8(f5_out1, T84, T89) -> f328_out1(T89) Q is empty. ---------------------------------------- (71) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN(T44) -> U1^1(f149_in(T44), T44) F5_IN(T44) -> F149_IN(T44) F5_IN(T84) -> U2^1(f328_in(T84), T84) F5_IN(T84) -> F328_IN(T84) F276_IN(s(T67)) -> U3^1(f276_in(T67), s(T67)) F276_IN(s(T67)) -> F276_IN(T67) F335_IN(s(T108)) -> U4^1(f335_in(T108), s(T108)) F335_IN(s(T108)) -> F335_IN(T108) F149_IN(T44) -> U5^1(f276_in(T44), T44) F149_IN(T44) -> F276_IN(T44) U5^1(f276_out1, T44) -> U6^1(f5_in(T44), T44) U5^1(f276_out1, T44) -> F5_IN(T44) F328_IN(T84) -> U7^1(f335_in(T84), T84) F328_IN(T84) -> F335_IN(T84) U7^1(f335_out1(T89), T84) -> U8^1(f5_in(T84), T84, T89) U7^1(f335_out1(T89), T84) -> F5_IN(T84) The TRS R consists of the following rules: f5_in(T8) -> f5_out1 f5_in(T44) -> U1(f149_in(T44), T44) U1(f149_out1, T44) -> f5_out1 f5_in(T84) -> U2(f328_in(T84), T84) U2(f328_out1(T89), T84) -> f5_out1 f276_in(0) -> f276_out1 f276_in(s(T67)) -> U3(f276_in(T67), s(T67)) U3(f276_out1, s(T67)) -> f276_out1 f335_in(s(T102)) -> f335_out1(0) f335_in(s(T108)) -> U4(f335_in(T108), s(T108)) U4(f335_out1(T109), s(T108)) -> f335_out1(s(T109)) f149_in(T44) -> U5(f276_in(T44), T44) U5(f276_out1, T44) -> U6(f5_in(T44), T44) U6(f5_out1, T44) -> f149_out1 f328_in(T84) -> U7(f335_in(T84), T84) U7(f335_out1(T89), T84) -> U8(f5_in(T84), T84, T89) U8(f5_out1, T84, T89) -> f328_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 8 less nodes. ---------------------------------------- (74) Complex Obligation (AND) ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: F335_IN(s(T108)) -> F335_IN(T108) The TRS R consists of the following rules: f5_in(T8) -> f5_out1 f5_in(T44) -> U1(f149_in(T44), T44) U1(f149_out1, T44) -> f5_out1 f5_in(T84) -> U2(f328_in(T84), T84) U2(f328_out1(T89), T84) -> f5_out1 f276_in(0) -> f276_out1 f276_in(s(T67)) -> U3(f276_in(T67), s(T67)) U3(f276_out1, s(T67)) -> f276_out1 f335_in(s(T102)) -> f335_out1(0) f335_in(s(T108)) -> U4(f335_in(T108), s(T108)) U4(f335_out1(T109), s(T108)) -> f335_out1(s(T109)) f149_in(T44) -> U5(f276_in(T44), T44) U5(f276_out1, T44) -> U6(f5_in(T44), T44) U6(f5_out1, T44) -> f149_out1 f328_in(T84) -> U7(f335_in(T84), T84) U7(f335_out1(T89), T84) -> U8(f5_in(T84), T84, T89) U8(f5_out1, T84, T89) -> f328_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) 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. ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: F335_IN(s(T108)) -> F335_IN(T108) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) 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: *F335_IN(s(T108)) -> F335_IN(T108) The graph contains the following edges 1 > 1 ---------------------------------------- (79) YES ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: F276_IN(s(T67)) -> F276_IN(T67) The TRS R consists of the following rules: f5_in(T8) -> f5_out1 f5_in(T44) -> U1(f149_in(T44), T44) U1(f149_out1, T44) -> f5_out1 f5_in(T84) -> U2(f328_in(T84), T84) U2(f328_out1(T89), T84) -> f5_out1 f276_in(0) -> f276_out1 f276_in(s(T67)) -> U3(f276_in(T67), s(T67)) U3(f276_out1, s(T67)) -> f276_out1 f335_in(s(T102)) -> f335_out1(0) f335_in(s(T108)) -> U4(f335_in(T108), s(T108)) U4(f335_out1(T109), s(T108)) -> f335_out1(s(T109)) f149_in(T44) -> U5(f276_in(T44), T44) U5(f276_out1, T44) -> U6(f5_in(T44), T44) U6(f5_out1, T44) -> f149_out1 f328_in(T84) -> U7(f335_in(T84), T84) U7(f335_out1(T89), T84) -> U8(f5_in(T84), T84, T89) U8(f5_out1, T84, T89) -> f328_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) 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. ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: F276_IN(s(T67)) -> F276_IN(T67) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) 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: *F276_IN(s(T67)) -> F276_IN(T67) The graph contains the following edges 1 > 1 ---------------------------------------- (84) YES ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN(T44) -> F149_IN(T44) F149_IN(T44) -> U5^1(f276_in(T44), T44) U5^1(f276_out1, T44) -> F5_IN(T44) F5_IN(T84) -> F328_IN(T84) F328_IN(T84) -> U7^1(f335_in(T84), T84) U7^1(f335_out1(T89), T84) -> F5_IN(T84) The TRS R consists of the following rules: f5_in(T8) -> f5_out1 f5_in(T44) -> U1(f149_in(T44), T44) U1(f149_out1, T44) -> f5_out1 f5_in(T84) -> U2(f328_in(T84), T84) U2(f328_out1(T89), T84) -> f5_out1 f276_in(0) -> f276_out1 f276_in(s(T67)) -> U3(f276_in(T67), s(T67)) U3(f276_out1, s(T67)) -> f276_out1 f335_in(s(T102)) -> f335_out1(0) f335_in(s(T108)) -> U4(f335_in(T108), s(T108)) U4(f335_out1(T109), s(T108)) -> f335_out1(s(T109)) f149_in(T44) -> U5(f276_in(T44), T44) U5(f276_out1, T44) -> U6(f5_in(T44), T44) U6(f5_out1, T44) -> f149_out1 f328_in(T84) -> U7(f335_in(T84), T84) U7(f335_out1(T89), T84) -> U8(f5_in(T84), T84, T89) U8(f5_out1, T84, T89) -> f328_out1(T89) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) 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 = F149_IN(0) evaluates to t =F149_IN(0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F149_IN(0) -> U5^1(f276_in(0), 0) with rule F149_IN(T44) -> U5^1(f276_in(T44), T44) at position [] and matcher [T44 / 0] U5^1(f276_in(0), 0) -> U5^1(f276_out1, 0) with rule f276_in(0) -> f276_out1 at position [0] and matcher [ ] U5^1(f276_out1, 0) -> F5_IN(0) with rule U5^1(f276_out1, T44') -> F5_IN(T44') at position [] and matcher [T44' / 0] F5_IN(0) -> F149_IN(0) with rule F5_IN(T44) -> F149_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. ---------------------------------------- (87) NO ---------------------------------------- (88) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "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": { "type": "Nodes", "370": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "272": { "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": [] } }, "371": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "372": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T109 T108)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T108"], "free": [], "exprvars": [] } }, "153": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "274": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "373": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "154": { "goal": [{ "clause": 1, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "198": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "275": { "goal": [{ "clause": 5, "scope": 2, "term": "(less T44 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "155": { "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": [] } }, "156": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "157": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "158": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "312": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T67 T69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T67"], "free": [], "exprvars": [] } }, "159": { "goal": [{ "clause": 2, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "314": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "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": [] } }, "160": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "161": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T44 T49) (insert T44 T50 T51))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "162": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [{ "clause": 0, "scope": 1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "143": { "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": [] } }, "320": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T89 T84) (insert T84 T90 T91))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "364": { "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": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "321": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "322": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "202": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T44 T54 T55)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "323": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T84 T94 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "367": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "368": { "goal": [{ "clause": 5, "scope": 3, "term": "(less T89 T84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T84"], "free": [], "exprvars": [] } }, "369": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "306": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "307": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "309": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 16, "label": "CASE" }, { "from": 16, "to": 142, "label": "PARALLEL" }, { "from": 16, "to": 143, "label": "PARALLEL" }, { "from": 142, "to": 151, "label": "EVAL with clause\ninsert(X6, void, tree(X6, void, void)).\nand substitutionT1 -> T8,\nX6 -> T8,\nT2 -> void,\nT3 -> tree(T8, void, void)" }, { "from": 142, "to": 152, "label": "EVAL-BACKTRACK" }, { "from": 143, "to": 154, "label": "PARALLEL" }, { "from": 143, "to": 155, "label": "PARALLEL" }, { "from": 151, "to": 153, "label": "SUCCESS" }, { "from": 154, "to": 156, "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": 154, "to": 157, "label": "EVAL-BACKTRACK" }, { "from": 155, "to": 159, "label": "PARALLEL" }, { "from": 155, "to": 160, "label": "PARALLEL" }, { "from": 156, "to": 158, "label": "SUCCESS" }, { "from": 159, "to": 161, "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": 159, "to": 162, "label": "EVAL-BACKTRACK" }, { "from": 160, "to": 320, "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": 160, "to": 321, "label": "EVAL-BACKTRACK" }, { "from": 161, "to": 198, "label": "SPLIT 1" }, { "from": 161, "to": 202, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nreplacements:T50 -> T54,\nT51 -> T55" }, { "from": 198, "to": 272, "label": "CASE" }, { "from": 202, "to": 2, "label": "INSTANCE with matching:\nT1 -> T44\nT2 -> T54\nT3 -> T55" }, { "from": 272, "to": 274, "label": "PARALLEL" }, { "from": 272, "to": 275, "label": "PARALLEL" }, { "from": 274, "to": 306, "label": "EVAL with clause\nless(0, s(X55)).\nand substitutionT44 -> 0,\nX55 -> T62,\nT49 -> s(T62)" }, { "from": 274, "to": 307, "label": "EVAL-BACKTRACK" }, { "from": 275, "to": 312, "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": 275, "to": 314, "label": "EVAL-BACKTRACK" }, { "from": 306, "to": 309, "label": "SUCCESS" }, { "from": 312, "to": 198, "label": "INSTANCE with matching:\nT44 -> T67\nT49 -> T69" }, { "from": 320, "to": 322, "label": "SPLIT 1" }, { "from": 320, "to": 323, "label": "SPLIT 2\nnew knowledge:\nT89 is ground\nT84 is ground\nreplacements:T90 -> T94,\nT91 -> T95" }, { "from": 322, "to": 364, "label": "CASE" }, { "from": 323, "to": 2, "label": "INSTANCE with matching:\nT1 -> T84\nT2 -> T94\nT3 -> T95" }, { "from": 364, "to": 367, "label": "PARALLEL" }, { "from": 364, "to": 368, "label": "PARALLEL" }, { "from": 367, "to": 369, "label": "EVAL with clause\nless(0, s(X89)).\nand substitutionT89 -> 0,\nX89 -> T102,\nT84 -> s(T102)" }, { "from": 367, "to": 370, "label": "EVAL-BACKTRACK" }, { "from": 368, "to": 372, "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": 368, "to": 373, "label": "EVAL-BACKTRACK" }, { "from": 369, "to": 371, "label": "SUCCESS" }, { "from": 372, "to": 322, "label": "INSTANCE with matching:\nT89 -> T109\nT84 -> T108" } ], "type": "Graph" } } ---------------------------------------- (89) Complex Obligation (AND) ---------------------------------------- (90) Obligation: Rules: f322_in(T84) -> f364_in(T84) :|: TRUE f364_out(x) -> f322_out(x) :|: TRUE f364_in(x1) -> f367_in(x1) :|: TRUE f367_out(x2) -> f364_out(x2) :|: TRUE f364_in(x3) -> f368_in(x3) :|: TRUE f368_out(x4) -> f364_out(x4) :|: TRUE f322_out(T108) -> f372_out(T108) :|: TRUE f372_in(x5) -> f322_in(x5) :|: TRUE f372_out(x6) -> f368_out(s(x6)) :|: TRUE f368_in(s(x7)) -> f372_in(x7) :|: TRUE f373_out -> f368_out(x8) :|: TRUE f368_in(x9) -> f373_in :|: TRUE f2_in(T1) -> f16_in(T1) :|: TRUE f16_out(x10) -> f2_out(x10) :|: TRUE f16_in(x11) -> f143_in(x11) :|: TRUE f16_in(x12) -> f142_in(x12) :|: TRUE f142_out(x13) -> f16_out(x13) :|: TRUE f143_out(x14) -> f16_out(x14) :|: TRUE f143_in(x15) -> f154_in(x15) :|: TRUE f143_in(x16) -> f155_in(x16) :|: TRUE f155_out(x17) -> f143_out(x17) :|: TRUE f154_out(x18) -> f143_out(x18) :|: TRUE f155_in(x19) -> f159_in(x19) :|: TRUE f160_out(x20) -> f155_out(x20) :|: TRUE f155_in(x21) -> f160_in(x21) :|: TRUE f159_out(x22) -> f155_out(x22) :|: TRUE f160_in(x23) -> f321_in :|: TRUE f320_out(x24) -> f160_out(x24) :|: TRUE f160_in(x25) -> f320_in(x25) :|: TRUE f321_out -> f160_out(x26) :|: TRUE f320_in(x27) -> f322_in(x27) :|: TRUE f322_out(x28) -> f323_in(x28) :|: TRUE f323_out(x29) -> f320_out(x29) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (91) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f322_in(T84) -> f364_in(T84) :|: TRUE f364_in(x3) -> f368_in(x3) :|: TRUE f372_in(x5) -> f322_in(x5) :|: TRUE f368_in(s(x7)) -> f372_in(x7) :|: TRUE ---------------------------------------- (92) Obligation: Rules: f322_in(T84) -> f364_in(T84) :|: TRUE f364_in(x3) -> f368_in(x3) :|: TRUE f372_in(x5) -> f322_in(x5) :|: TRUE f368_in(s(x7)) -> f372_in(x7) :|: TRUE ---------------------------------------- (93) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (94) Obligation: Rules: f372_in(s(x7:0)) -> f372_in(x7:0) :|: TRUE ---------------------------------------- (95) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (96) Obligation: Rules: f372_in(s(x7:0)) -> f372_in(x7:0) :|: TRUE ---------------------------------------- (97) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f372_in(s(x7:0)) -> f372_in(x7:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (98) Obligation: Termination digraph: Nodes: (1) f372_in(s(x7:0)) -> f372_in(x7:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (99) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f372_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (100) Obligation: Rules: f372_in(s(x7:0)) -> f372_in(x7:0) ---------------------------------------- (101) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: f372_in(s(x7:0)) -> f372_in(x7:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (103) 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: *f372_in(s(x7:0)) -> f372_in(x7:0) The graph contains the following edges 1 > 1 ---------------------------------------- (104) YES ---------------------------------------- (105) Obligation: Rules: f272_out(T44) -> f198_out(T44) :|: TRUE f198_in(x) -> f272_in(x) :|: TRUE f275_in(x1) -> f314_in :|: TRUE f312_out(T67) -> f275_out(s(T67)) :|: TRUE f275_in(s(x2)) -> f312_in(x2) :|: TRUE f314_out -> f275_out(x3) :|: TRUE f312_in(x4) -> f198_in(x4) :|: TRUE f198_out(x5) -> f312_out(x5) :|: TRUE f272_in(x6) -> f274_in(x6) :|: TRUE f274_out(x7) -> f272_out(x7) :|: TRUE f275_out(x8) -> f272_out(x8) :|: TRUE f272_in(x9) -> f275_in(x9) :|: TRUE f2_in(T1) -> f16_in(T1) :|: TRUE f16_out(x10) -> f2_out(x10) :|: TRUE f16_in(x11) -> f143_in(x11) :|: TRUE f16_in(x12) -> f142_in(x12) :|: TRUE f142_out(x13) -> f16_out(x13) :|: TRUE f143_out(x14) -> f16_out(x14) :|: TRUE f143_in(x15) -> f154_in(x15) :|: TRUE f143_in(x16) -> f155_in(x16) :|: TRUE f155_out(x17) -> f143_out(x17) :|: TRUE f154_out(x18) -> f143_out(x18) :|: TRUE f155_in(x19) -> f159_in(x19) :|: TRUE f160_out(x20) -> f155_out(x20) :|: TRUE f155_in(x21) -> f160_in(x21) :|: TRUE f159_out(x22) -> f155_out(x22) :|: TRUE f162_out -> f159_out(x23) :|: TRUE f159_in(x24) -> f161_in(x24) :|: TRUE f159_in(x25) -> f162_in :|: TRUE f161_out(x26) -> f159_out(x26) :|: TRUE f161_in(x27) -> f198_in(x27) :|: TRUE f198_out(x28) -> f202_in(x28) :|: TRUE f202_out(x29) -> f161_out(x29) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (106) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f198_in(x) -> f272_in(x) :|: TRUE f275_in(s(x2)) -> f312_in(x2) :|: TRUE f312_in(x4) -> f198_in(x4) :|: TRUE f272_in(x9) -> f275_in(x9) :|: TRUE ---------------------------------------- (107) Obligation: Rules: f198_in(x) -> f272_in(x) :|: TRUE f275_in(s(x2)) -> f312_in(x2) :|: TRUE f312_in(x4) -> f198_in(x4) :|: TRUE f272_in(x9) -> f275_in(x9) :|: TRUE ---------------------------------------- (108) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (109) Obligation: Rules: f275_in(s(x2:0)) -> f275_in(x2:0) :|: TRUE ---------------------------------------- (110) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (111) Obligation: Rules: f275_in(s(x2:0)) -> f275_in(x2:0) :|: TRUE ---------------------------------------- (112) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f275_in(s(x2:0)) -> f275_in(x2:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (113) Obligation: Termination digraph: Nodes: (1) f275_in(s(x2:0)) -> f275_in(x2:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (114) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f275_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (115) Obligation: Rules: f275_in(s(x2:0)) -> f275_in(x2:0) ---------------------------------------- (116) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (117) Obligation: Q DP problem: The TRS P consists of the following rules: f275_in(s(x2:0)) -> f275_in(x2:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (118) 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: *f275_in(s(x2:0)) -> f275_in(x2:0) The graph contains the following edges 1 > 1 ---------------------------------------- (119) YES ---------------------------------------- (120) Obligation: Rules: f202_in(T44) -> f2_in(T44) :|: TRUE f2_out(x) -> f202_out(x) :|: TRUE f272_out(x1) -> f198_out(x1) :|: TRUE f198_in(x2) -> f272_in(x2) :|: TRUE f312_in(T67) -> f198_in(T67) :|: TRUE f198_out(x3) -> f312_out(x3) :|: TRUE f160_in(T1) -> f321_in :|: TRUE f320_out(T84) -> f160_out(T84) :|: TRUE f160_in(x4) -> f320_in(x4) :|: TRUE f321_out -> f160_out(x5) :|: TRUE f320_in(x6) -> f322_in(x6) :|: TRUE f322_out(x7) -> f323_in(x7) :|: TRUE f323_out(x8) -> f320_out(x8) :|: TRUE f275_in(x9) -> f314_in :|: TRUE f312_out(x10) -> f275_out(s(x10)) :|: TRUE f275_in(s(x11)) -> f312_in(x11) :|: TRUE f314_out -> f275_out(x12) :|: TRUE f323_in(x13) -> f2_in(x13) :|: TRUE f2_out(x14) -> f323_out(x14) :|: TRUE f274_in(x15) -> f307_in :|: TRUE f306_out -> f274_out(0) :|: TRUE f274_in(0) -> f306_in :|: TRUE f307_out -> f274_out(x16) :|: TRUE f322_in(x17) -> f364_in(x17) :|: TRUE f364_out(x18) -> f322_out(x18) :|: TRUE f364_in(x19) -> f367_in(x19) :|: TRUE f367_out(x20) -> f364_out(x20) :|: TRUE f364_in(x21) -> f368_in(x21) :|: TRUE f368_out(x22) -> f364_out(x22) :|: TRUE f322_out(T108) -> f372_out(T108) :|: TRUE f372_in(x23) -> f322_in(x23) :|: TRUE f161_in(x24) -> f198_in(x24) :|: TRUE f198_out(x25) -> f202_in(x25) :|: TRUE f202_out(x26) -> f161_out(x26) :|: TRUE f162_out -> f159_out(x27) :|: TRUE f159_in(x28) -> f161_in(x28) :|: TRUE f159_in(x29) -> f162_in :|: TRUE f161_out(x30) -> f159_out(x30) :|: TRUE f143_in(x31) -> f154_in(x31) :|: TRUE f143_in(x32) -> f155_in(x32) :|: TRUE f155_out(x33) -> f143_out(x33) :|: TRUE f154_out(x34) -> f143_out(x34) :|: TRUE f272_in(x35) -> f274_in(x35) :|: TRUE f274_out(x36) -> f272_out(x36) :|: TRUE f275_out(x37) -> f272_out(x37) :|: TRUE f272_in(x38) -> f275_in(x38) :|: TRUE f372_out(x39) -> f368_out(s(x39)) :|: TRUE f368_in(s(x40)) -> f372_in(x40) :|: TRUE f373_out -> f368_out(x41) :|: TRUE f368_in(x42) -> f373_in :|: TRUE f2_in(x43) -> f16_in(x43) :|: TRUE f16_out(x44) -> f2_out(x44) :|: TRUE f369_out -> f367_out(s(T102)) :|: TRUE f367_in(x45) -> f370_in :|: TRUE f370_out -> f367_out(x46) :|: TRUE f367_in(s(x47)) -> f369_in :|: TRUE f306_in -> f306_out :|: TRUE f16_in(x48) -> f143_in(x48) :|: TRUE f16_in(x49) -> f142_in(x49) :|: TRUE f142_out(x50) -> f16_out(x50) :|: TRUE f143_out(x51) -> f16_out(x51) :|: TRUE f369_in -> f369_out :|: TRUE f155_in(x52) -> f159_in(x52) :|: TRUE f160_out(x53) -> f155_out(x53) :|: TRUE f155_in(x54) -> f160_in(x54) :|: TRUE f159_out(x55) -> f155_out(x55) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (121) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f202_in(T44) -> f2_in(T44) :|: TRUE f272_out(x1) -> f198_out(x1) :|: TRUE f198_in(x2) -> f272_in(x2) :|: TRUE f312_in(T67) -> f198_in(T67) :|: TRUE f198_out(x3) -> f312_out(x3) :|: TRUE f160_in(x4) -> f320_in(x4) :|: TRUE f320_in(x6) -> f322_in(x6) :|: TRUE f322_out(x7) -> f323_in(x7) :|: TRUE f312_out(x10) -> f275_out(s(x10)) :|: TRUE f275_in(s(x11)) -> f312_in(x11) :|: TRUE f323_in(x13) -> f2_in(x13) :|: TRUE f306_out -> f274_out(0) :|: TRUE f274_in(0) -> f306_in :|: TRUE f322_in(x17) -> f364_in(x17) :|: TRUE f364_out(x18) -> f322_out(x18) :|: TRUE f364_in(x19) -> f367_in(x19) :|: TRUE f367_out(x20) -> f364_out(x20) :|: TRUE f364_in(x21) -> f368_in(x21) :|: TRUE f368_out(x22) -> f364_out(x22) :|: TRUE f322_out(T108) -> f372_out(T108) :|: TRUE f372_in(x23) -> f322_in(x23) :|: TRUE f161_in(x24) -> f198_in(x24) :|: TRUE f198_out(x25) -> f202_in(x25) :|: TRUE f159_in(x28) -> f161_in(x28) :|: TRUE f143_in(x32) -> f155_in(x32) :|: TRUE f272_in(x35) -> f274_in(x35) :|: TRUE f274_out(x36) -> f272_out(x36) :|: TRUE f275_out(x37) -> f272_out(x37) :|: TRUE f272_in(x38) -> f275_in(x38) :|: TRUE f372_out(x39) -> f368_out(s(x39)) :|: TRUE f368_in(s(x40)) -> f372_in(x40) :|: TRUE f2_in(x43) -> f16_in(x43) :|: TRUE f369_out -> f367_out(s(T102)) :|: TRUE f367_in(s(x47)) -> f369_in :|: TRUE f306_in -> f306_out :|: TRUE f16_in(x48) -> f143_in(x48) :|: TRUE f369_in -> f369_out :|: TRUE f155_in(x52) -> f159_in(x52) :|: TRUE f155_in(x54) -> f160_in(x54) :|: TRUE ---------------------------------------- (122) Obligation: Rules: f202_in(T44) -> f2_in(T44) :|: TRUE f272_out(x1) -> f198_out(x1) :|: TRUE f198_in(x2) -> f272_in(x2) :|: TRUE f312_in(T67) -> f198_in(T67) :|: TRUE f198_out(x3) -> f312_out(x3) :|: TRUE f160_in(x4) -> f320_in(x4) :|: TRUE f320_in(x6) -> f322_in(x6) :|: TRUE f322_out(x7) -> f323_in(x7) :|: TRUE f312_out(x10) -> f275_out(s(x10)) :|: TRUE f275_in(s(x11)) -> f312_in(x11) :|: TRUE f323_in(x13) -> f2_in(x13) :|: TRUE f306_out -> f274_out(0) :|: TRUE f274_in(0) -> f306_in :|: TRUE f322_in(x17) -> f364_in(x17) :|: TRUE f364_out(x18) -> f322_out(x18) :|: TRUE f364_in(x19) -> f367_in(x19) :|: TRUE f367_out(x20) -> f364_out(x20) :|: TRUE f364_in(x21) -> f368_in(x21) :|: TRUE f368_out(x22) -> f364_out(x22) :|: TRUE f322_out(T108) -> f372_out(T108) :|: TRUE f372_in(x23) -> f322_in(x23) :|: TRUE f161_in(x24) -> f198_in(x24) :|: TRUE f198_out(x25) -> f202_in(x25) :|: TRUE f159_in(x28) -> f161_in(x28) :|: TRUE f143_in(x32) -> f155_in(x32) :|: TRUE f272_in(x35) -> f274_in(x35) :|: TRUE f274_out(x36) -> f272_out(x36) :|: TRUE f275_out(x37) -> f272_out(x37) :|: TRUE f272_in(x38) -> f275_in(x38) :|: TRUE f372_out(x39) -> f368_out(s(x39)) :|: TRUE f368_in(s(x40)) -> f372_in(x40) :|: TRUE f2_in(x43) -> f16_in(x43) :|: TRUE f369_out -> f367_out(s(T102)) :|: TRUE f367_in(s(x47)) -> f369_in :|: TRUE f306_in -> f306_out :|: TRUE f16_in(x48) -> f143_in(x48) :|: TRUE f369_in -> f369_out :|: TRUE f155_in(x52) -> f159_in(x52) :|: TRUE f155_in(x54) -> f160_in(x54) :|: TRUE ---------------------------------------- (123) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (124) Obligation: Rules: f364_in(s(x40:0)) -> f364_in(x40:0) :|: TRUE f272_out(x1:0) -> f143_in(x1:0) :|: TRUE f364_in(s(x47:0)) -> f364_out(s(T102:0)) :|: TRUE f143_in(x32:0) -> f198_in(x32:0) :|: TRUE f143_in(x) -> f364_in(x) :|: TRUE f364_out(x18:0) -> f364_out(s(x18:0)) :|: TRUE f198_in(s(x11:0)) -> f198_in(x11:0) :|: TRUE f272_out(x1) -> f272_out(s(x1)) :|: TRUE f364_out(x2) -> f143_in(x2) :|: TRUE f198_in(cons_0) -> f272_out(0) :|: TRUE && cons_0 = 0 ---------------------------------------- (125) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (126) Obligation: Rules: f364_in(s(x40:0)) -> f364_in(x40:0) :|: TRUE f272_out(x1:0) -> f143_in(x1:0) :|: TRUE f364_in(s(x47:0)) -> f364_out(s(T102:0)) :|: TRUE f143_in(x32:0) -> f198_in(x32:0) :|: TRUE f143_in(x) -> f364_in(x) :|: TRUE f364_out(x18:0) -> f364_out(s(x18:0)) :|: TRUE f198_in(s(x11:0)) -> f198_in(x11:0) :|: TRUE f272_out(x1) -> f272_out(s(x1)) :|: TRUE f364_out(x2) -> f143_in(x2) :|: TRUE f198_in(cons_0) -> f272_out(0) :|: TRUE && cons_0 = 0 ---------------------------------------- (127) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f364_in(s(x40:0)) -> f364_in(x40:0) :|: TRUE (2) f272_out(x1:0) -> f143_in(x1:0) :|: TRUE (3) f364_in(s(x47:0)) -> f364_out(s(T102:0)) :|: TRUE (4) f143_in(x32:0) -> f198_in(x32:0) :|: TRUE (5) f143_in(x) -> f364_in(x) :|: TRUE (6) f364_out(x18:0) -> f364_out(s(x18:0)) :|: TRUE (7) f198_in(s(x11:0)) -> f198_in(x11:0) :|: TRUE (8) f272_out(x1) -> f272_out(s(x1)) :|: TRUE (9) f364_out(x2) -> f143_in(x2) :|: TRUE (10) f198_in(cons_0) -> f272_out(0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1), (3) (2) -> (4), (5) (3) -> (6), (9) (4) -> (7), (10) (5) -> (1), (3) (6) -> (6), (9) (7) -> (7), (10) (8) -> (2), (8) (9) -> (4), (5) (10) -> (2), (8) This digraph is fully evaluated! ---------------------------------------- (128) Obligation: Termination digraph: Nodes: (1) f364_in(s(x40:0)) -> f364_in(x40:0) :|: TRUE (2) f143_in(x) -> f364_in(x) :|: TRUE (3) f272_out(x1:0) -> f143_in(x1:0) :|: TRUE (4) f272_out(x1) -> f272_out(s(x1)) :|: TRUE (5) f198_in(cons_0) -> f272_out(0) :|: TRUE && cons_0 = 0 (6) f198_in(s(x11:0)) -> f198_in(x11:0) :|: TRUE (7) f143_in(x32:0) -> f198_in(x32:0) :|: TRUE (8) f364_out(x2) -> f143_in(x2) :|: TRUE (9) f364_out(x18:0) -> f364_out(s(x18:0)) :|: TRUE (10) f364_in(s(x47:0)) -> f364_out(s(T102:0)) :|: TRUE Arcs: (1) -> (1), (10) (2) -> (1), (10) (3) -> (2), (7) (4) -> (3), (4) (5) -> (3), (4) (6) -> (5), (6) (7) -> (5), (6) (8) -> (2), (7) (9) -> (8), (9) (10) -> (8), (9) This digraph is fully evaluated! ---------------------------------------- (129) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (130) Obligation: Rules: f143_in(x32:0:0) -> f198_in(x32:0:0) :|: TRUE f364_out(x2:0) -> f143_in(x2:0) :|: TRUE f143_in(x:0) -> f364_in(x:0) :|: TRUE f272_out(x1:0) -> f272_out(s(x1:0)) :|: TRUE f272_out(x1:0:0) -> f143_in(x1:0:0) :|: TRUE f198_in(cons_0) -> f272_out(0) :|: TRUE && cons_0 = 0 f198_in(s(x11:0:0)) -> f198_in(x11:0:0) :|: TRUE f364_out(x18:0:0) -> f364_out(s(x18:0:0)) :|: TRUE f364_in(s(x40:0:0)) -> f364_in(x40:0:0) :|: TRUE f364_in(s(x47:0:0)) -> f364_out(s(T102:0:0)) :|: TRUE ---------------------------------------- (131) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (132) Obligation: Rules: f143_in(x) -> f198_in(x) :|: TRUE f364_out(x1) -> f143_in(x1) :|: TRUE f143_in(x2) -> f364_in(x2) :|: TRUE f272_out(x3) -> f272_out(s(x3)) :|: TRUE f272_out(x4) -> f143_in(x4) :|: TRUE f198_in(cons_0) -> f272_out(0) :|: TRUE && cons_0 = 0 f198_in(s(x6)) -> f198_in(x6) :|: TRUE f364_out(x7) -> f364_out(s(x7)) :|: TRUE f364_in(s(x8)) -> f364_in(x8) :|: TRUE f364_in(s(x9)) -> f364_out(s(x10)) :|: TRUE ---------------------------------------- (133) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 17, "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": { "type": "Nodes", "350": { "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": [] } }, "351": { "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": [] } }, "352": { "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": [] } }, "111": { "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": [] } }, "353": { "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": [] } }, "354": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "113": { "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": [] } }, "355": { "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": [] } }, "114": { "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": [] } }, "356": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "117": { "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": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "18": { "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": [] } }, "121": { "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": [] } }, "124": { "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": [] } }, "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": [] } }, "374": { "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": [] } }, "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": [] } }, "375": { "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": [] } }, "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": [ { "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": [] } }, "497": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "377": { "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": [] } }, "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": [ { "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": [] } }, "499": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "379": { "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": [] } }, "380": { "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": [] } }, "381": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T166 T167)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "382": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "383": { "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": [] } }, "384": { "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": [] } }, "385": { "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": [] } }, "386": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "387": { "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": [] } }, "388": { "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": [] } }, "389": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "302": { "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": [] } }, "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": [], "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": [{ "clause": -1, "scope": -1, "term": "(less T40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "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": [{ "clause": -1, "scope": -1, "term": "(insert (s T40) T47 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "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": [] } }, "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": [] } }, "428": { "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": [] } }, "308": { "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": [] } }, "429": { "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": [] } }, "390": { "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": [] } }, "391": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "392": { "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": [] } }, "393": { "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": [] } }, "394": { "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": [] } }, "395": { "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": [] } }, "396": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "397": { "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": [] } }, "430": { "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": [] } }, "310": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "398": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "431": { "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": [] } }, "311": { "goal": [{ "clause": 5, "scope": 3, "term": "(less T40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "432": { "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": [] } }, "433": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T268 T269)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "434": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "435": { "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": [] } }, "315": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "436": { "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": [] } }, "316": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "437": { "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": [] } }, "317": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T60 T62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T60"], "free": [], "exprvars": [] } }, "438": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "318": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "439": { "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": [] } }, "319": { "goal": [{ "clause": 3, "scope": 1, "term": "(insert T17 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "163": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "164": { "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": [] } }, "440": { "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": [] } }, "441": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "442": { "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": [] } }, "443": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "444": { "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": [] } }, "324": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T82 T77) (insert T77 T83 T84))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "445": { "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": [] } }, "325": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "446": { "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": [] } }, "326": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T82 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "447": { "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": [] } }, "327": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T77 T87 T88)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "448": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "449": { "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": [] } }, "329": { "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": [] } }, "450": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "451": { "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": [] } }, "298": { "goal": [{ "clause": 5, "scope": 2, "term": "(',' (less T17 T22) (insert T17 T23 T24))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "331": { "goal": [{ "clause": 4, "scope": 4, "term": "(less T82 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "452": { "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": [] } }, "299": { "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": [] } }, "332": { "goal": [{ "clause": 5, "scope": 4, "term": "(less T82 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T77"], "free": [], "exprvars": [] } }, "453": { "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": [] } }, "179": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T30 T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "333": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "454": { "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": [] } }, "334": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "455": { "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": [] } }, "456": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert (0) T356 T357)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "336": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "457": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "458": { "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": [] } }, "459": { "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": [] } }, "339": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T102 T101)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T101"], "free": [], "exprvars": [] } }, "180": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "460": { "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": [] } }, "340": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "461": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "462": { "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": [] } }, "463": { "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": [] } }, "464": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "465": { "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": [] } }, "466": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "467": { "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": [] } }, "348": { "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": [] } }, "107": { "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": [] } }, "349": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "108": { "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": [] } }, "109": { "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": [] } } }, "edges": [ { "from": 17, "to": 18, "label": "CASE" }, { "from": 18, "to": 107, "label": "EVAL with clause\ninsert(X3, void, tree(X3, void, void)).\nand substitutionT1 -> T5,\nX3 -> T5,\nT2 -> void,\nT3 -> tree(T5, void, void)" }, { "from": 18, "to": 108, "label": "EVAL-BACKTRACK" }, { "from": 107, "to": 109, "label": "SUCCESS" }, { "from": 108, "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": 108, "to": 426, "label": "EVAL-BACKTRACK" }, { "from": 109, "to": 111, "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": 109, "to": 113, "label": "EVAL-BACKTRACK" }, { "from": 111, "to": 114, "label": "SUCCESS" }, { "from": 113, "to": 376, "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": 113, "to": 377, "label": "EVAL-BACKTRACK" }, { "from": 114, "to": 117, "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": 114, "to": 121, "label": "EVAL-BACKTRACK" }, { "from": 117, "to": 124, "label": "CASE" }, { "from": 121, "to": 348, "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": 121, "to": 349, "label": "EVAL-BACKTRACK" }, { "from": 124, "to": 163, "label": "PARALLEL" }, { "from": 124, "to": 164, "label": "PARALLEL" }, { "from": 163, "to": 179, "label": "EVAL with clause\nless(0, s(X24)).\nand substitutionT17 -> 0,\nX24 -> T29,\nT22 -> s(T29),\nT23 -> T30,\nT24 -> T31" }, { "from": 163, "to": 180, "label": "EVAL-BACKTRACK" }, { "from": 164, "to": 298, "label": "PARALLEL" }, { "from": 164, "to": 299, "label": "PARALLEL" }, { "from": 179, "to": 17, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T30\nT3 -> T31" }, { "from": 298, "to": 302, "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": 298, "to": 303, "label": "EVAL-BACKTRACK" }, { "from": 299, "to": 319, "label": "FAILURE" }, { "from": 302, "to": 304, "label": "SPLIT 1" }, { "from": 302, "to": 305, "label": "SPLIT 2\nnew knowledge:\nT40 is ground\nreplacements:T43 -> T47,\nT44 -> T48" }, { "from": 304, "to": 308, "label": "CASE" }, { "from": 305, "to": 17, "label": "INSTANCE with matching:\nT1 -> s(T40)\nT2 -> T47\nT3 -> T48" }, { "from": 308, "to": 310, "label": "PARALLEL" }, { "from": 308, "to": 311, "label": "PARALLEL" }, { "from": 310, "to": 313, "label": "EVAL with clause\nless(0, s(X45)).\nand substitutionT40 -> 0,\nX45 -> T55,\nT42 -> s(T55)" }, { "from": 310, "to": 315, "label": "EVAL-BACKTRACK" }, { "from": 311, "to": 317, "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": 311, "to": 318, "label": "EVAL-BACKTRACK" }, { "from": 313, "to": 316, "label": "SUCCESS" }, { "from": 317, "to": 304, "label": "INSTANCE with matching:\nT40 -> T60\nT42 -> T62" }, { "from": 319, "to": 324, "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": 319, "to": 325, "label": "EVAL-BACKTRACK" }, { "from": 324, "to": 326, "label": "SPLIT 1" }, { "from": 324, "to": 327, "label": "SPLIT 2\nnew knowledge:\nT82 is ground\nT77 is ground\nreplacements:T83 -> T87,\nT84 -> T88" }, { "from": 326, "to": 329, "label": "CASE" }, { "from": 327, "to": 17, "label": "INSTANCE with matching:\nT1 -> T77\nT2 -> T87\nT3 -> T88" }, { "from": 329, "to": 331, "label": "PARALLEL" }, { "from": 329, "to": 332, "label": "PARALLEL" }, { "from": 331, "to": 333, "label": "EVAL with clause\nless(0, s(X79)).\nand substitutionT82 -> 0,\nX79 -> T95,\nT77 -> s(T95)" }, { "from": 331, "to": 334, "label": "EVAL-BACKTRACK" }, { "from": 332, "to": 339, "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": 332, "to": 340, "label": "EVAL-BACKTRACK" }, { "from": 333, "to": 336, "label": "SUCCESS" }, { "from": 339, "to": 326, "label": "INSTANCE with matching:\nT82 -> T102\nT77 -> T101" }, { "from": 348, "to": 350, "label": "CASE" }, { "from": 350, "to": 351, "label": "PARALLEL" }, { "from": 350, "to": 352, "label": "PARALLEL" }, { "from": 351, "to": 353, "label": "EVAL with clause\nless(0, s(X104)).\nand substitutionT117 -> 0,\nX104 -> T124,\nT112 -> s(T124),\nT118 -> T125,\nT119 -> T126" }, { "from": 351, "to": 354, "label": "EVAL-BACKTRACK" }, { "from": 352, "to": 355, "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": 352, "to": 356, "label": "EVAL-BACKTRACK" }, { "from": 353, "to": 17, "label": "INSTANCE with matching:\nT1 -> s(T124)\nT2 -> T125\nT3 -> T126" }, { "from": 355, "to": 374, "label": "SPLIT 1" }, { "from": 355, "to": 375, "label": "SPLIT 2\nnew knowledge:\nT135 is ground\nT134 is ground\nreplacements:T136 -> T140,\nT137 -> T141,\nT2 -> T142,\nT3 -> T143" }, { "from": 374, "to": 326, "label": "INSTANCE with matching:\nT82 -> T135\nT77 -> T134" }, { "from": 375, "to": 17, "label": "INSTANCE with matching:\nT1 -> s(T134)\nT2 -> T140\nT3 -> T141" }, { "from": 376, "to": 378, "label": "CASE" }, { "from": 377, "to": 390, "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": 377, "to": 391, "label": "EVAL-BACKTRACK" }, { "from": 378, "to": 379, "label": "PARALLEL" }, { "from": 378, "to": 380, "label": "PARALLEL" }, { "from": 379, "to": 381, "label": "EVAL with clause\nless(0, s(X133)).\nand substitutionT153 -> 0,\nX133 -> T165,\nT158 -> s(T165),\nT159 -> T166,\nT160 -> T167" }, { "from": 379, "to": 382, "label": "EVAL-BACKTRACK" }, { "from": 380, "to": 383, "label": "PARALLEL" }, { "from": 380, "to": 384, "label": "PARALLEL" }, { "from": 381, "to": 17, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T166\nT3 -> T167" }, { "from": 383, "to": 385, "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": 383, "to": 386, "label": "EVAL-BACKTRACK" }, { "from": 384, "to": 387, "label": "FAILURE" }, { "from": 385, "to": 302, "label": "INSTANCE with matching:\nT40 -> T176\nT42 -> T178\nT43 -> T179\nT44 -> T180" }, { "from": 387, "to": 388, "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": 387, "to": 389, "label": "EVAL-BACKTRACK" }, { "from": 388, "to": 324, "label": "INSTANCE with matching:\nT82 -> T198\nT77 -> T193\nT83 -> T199\nT84 -> T200" }, { "from": 390, "to": 392, "label": "CASE" }, { "from": 392, "to": 393, "label": "PARALLEL" }, { "from": 392, "to": 394, "label": "PARALLEL" }, { "from": 393, "to": 395, "label": "EVAL with clause\nless(0, s(X179)).\nand substitutionT213 -> 0,\nX179 -> T220,\nT208 -> s(T220),\nT214 -> T221,\nT215 -> T222" }, { "from": 393, "to": 396, "label": "EVAL-BACKTRACK" }, { "from": 394, "to": 397, "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": 394, "to": 398, "label": "EVAL-BACKTRACK" }, { "from": 395, "to": 17, "label": "INSTANCE with matching:\nT1 -> s(T220)\nT2 -> T221\nT3 -> T222" }, { "from": 397, "to": 423, "label": "SPLIT 1" }, { "from": 397, "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": 326, "label": "INSTANCE with matching:\nT82 -> T231\nT77 -> T230" }, { "from": 424, "to": 17, "label": "INSTANCE with matching:\nT1 -> s(T230)\nT2 -> T236\nT3 -> T237" }, { "from": 425, "to": 427, "label": "SUCCESS" }, { "from": 426, "to": 451, "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": 452, "label": "EVAL-BACKTRACK" }, { "from": 427, "to": 428, "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": 429, "label": "EVAL-BACKTRACK" }, { "from": 428, "to": 430, "label": "CASE" }, { "from": 429, "to": 442, "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": 429, "to": 443, "label": "EVAL-BACKTRACK" }, { "from": 430, "to": 431, "label": "PARALLEL" }, { "from": 430, "to": 432, "label": "PARALLEL" }, { "from": 431, "to": 433, "label": "EVAL with clause\nless(0, s(X214)).\nand substitutionT255 -> 0,\nX214 -> T267,\nT260 -> s(T267),\nT261 -> T268,\nT262 -> T269" }, { "from": 431, "to": 434, "label": "EVAL-BACKTRACK" }, { "from": 432, "to": 435, "label": "PARALLEL" }, { "from": 432, "to": 436, "label": "PARALLEL" }, { "from": 433, "to": 17, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T268\nT3 -> T269" }, { "from": 435, "to": 437, "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": 435, "to": 438, "label": "EVAL-BACKTRACK" }, { "from": 436, "to": 439, "label": "FAILURE" }, { "from": 437, "to": 302, "label": "INSTANCE with matching:\nT40 -> T278\nT42 -> T280\nT43 -> T281\nT44 -> T282" }, { "from": 439, "to": 440, "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": 439, "to": 441, "label": "EVAL-BACKTRACK" }, { "from": 440, "to": 324, "label": "INSTANCE with matching:\nT82 -> T300\nT77 -> T295\nT83 -> T301\nT84 -> T302" }, { "from": 442, "to": 444, "label": "CASE" }, { "from": 444, "to": 445, "label": "PARALLEL" }, { "from": 444, "to": 446, "label": "PARALLEL" }, { "from": 445, "to": 447, "label": "EVAL with clause\nless(0, s(X260)).\nand substitutionT315 -> 0,\nX260 -> T322,\nT310 -> s(T322),\nT316 -> T323,\nT317 -> T324" }, { "from": 445, "to": 448, "label": "EVAL-BACKTRACK" }, { "from": 446, "to": 449, "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": 446, "to": 450, "label": "EVAL-BACKTRACK" }, { "from": 447, "to": 17, "label": "INSTANCE with matching:\nT1 -> s(T322)\nT2 -> T323\nT3 -> T324" }, { "from": 449, "to": 355, "label": "INSTANCE with matching:\nT135 -> T333\nT134 -> T332\nT136 -> T334\nT137 -> T335\nX15 -> X205\nX16 -> X206\nX17 -> X207\nX18 -> X208\nX19 -> X209" }, { "from": 451, "to": 453, "label": "CASE" }, { "from": 452, "to": 465, "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": 452, "to": 466, "label": "EVAL-BACKTRACK" }, { "from": 453, "to": 454, "label": "PARALLEL" }, { "from": 453, "to": 455, "label": "PARALLEL" }, { "from": 454, "to": 456, "label": "EVAL with clause\nless(0, s(X285)).\nand substitutionT343 -> 0,\nX285 -> T355,\nT348 -> s(T355),\nT349 -> T356,\nT350 -> T357" }, { "from": 454, "to": 457, "label": "EVAL-BACKTRACK" }, { "from": 455, "to": 458, "label": "PARALLEL" }, { "from": 455, "to": 459, "label": "PARALLEL" }, { "from": 456, "to": 17, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T356\nT3 -> T357" }, { "from": 458, "to": 460, "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": 458, "to": 461, "label": "EVAL-BACKTRACK" }, { "from": 459, "to": 462, "label": "FAILURE" }, { "from": 460, "to": 302, "label": "INSTANCE with matching:\nT40 -> T366\nT42 -> T368\nT43 -> T369\nT44 -> T370" }, { "from": 462, "to": 463, "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": 462, "to": 464, "label": "EVAL-BACKTRACK" }, { "from": 463, "to": 390, "label": "INSTANCE with matching:\nT213 -> T388\nT208 -> T383\nT214 -> T389\nT215 -> T390\nX7 -> X197\nX8 -> X198\nX9 -> X199" }, { "from": 465, "to": 467, "label": "CASE" }, { "from": 467, "to": 494, "label": "PARALLEL" }, { "from": 467, "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": 17, "label": "INSTANCE with matching:\nT1 -> s(T410)\nT2 -> T411\nT3 -> T412" }, { "from": 498, "to": 397, "label": "INSTANCE with matching:\nT231 -> T421\nT230 -> T420\nT232 -> T422\nT233 -> T423\nX7 -> X197\nX8 -> X198\nX9 -> X199" } ], "type": "Graph" } } ---------------------------------------- (134) 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) ---------------------------------------- (135) 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 ---------------------------------------- (136) 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 ---------------------------------------- (137) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 23 less nodes. ---------------------------------------- (138) Complex Obligation (AND) ---------------------------------------- (139) 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 ---------------------------------------- (140) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (141) 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 ---------------------------------------- (142) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (143) 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. ---------------------------------------- (144) 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 ---------------------------------------- (145) YES ---------------------------------------- (146) 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 ---------------------------------------- (147) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (148) 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 ---------------------------------------- (149) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (150) 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. ---------------------------------------- (151) 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 ---------------------------------------- (152) YES ---------------------------------------- (153) 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 ---------------------------------------- (154) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (155) 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.