/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern in(g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 19 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 3 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, 2 ms] (25) QDP (26) TransformationProof [SOUND, 0 ms] (27) QDP (28) TransformationProof [SOUND, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) AND (34) QDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) QDP (37) QReductionProof [EQUIVALENT, 0 ms] (38) QDP (39) NonTerminationLoopProof [COMPLETE, 0 ms] (40) NO (41) QDP (42) TransformationProof [EQUIVALENT, 0 ms] (43) QDP (44) PrologToPiTRSProof [SOUND, 0 ms] (45) PiTRS (46) DependencyPairsProof [EQUIVALENT, 12 ms] (47) PiDP (48) DependencyGraphProof [EQUIVALENT, 0 ms] (49) AND (50) PiDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) PiDP (53) PiDPToQDPProof [SOUND, 0 ms] (54) QDP (55) QDPSizeChangeProof [EQUIVALENT, 0 ms] (56) YES (57) PiDP (58) UsableRulesProof [EQUIVALENT, 0 ms] (59) PiDP (60) PiDPToQDPProof [SOUND, 0 ms] (61) QDP (62) QDPSizeChangeProof [EQUIVALENT, 0 ms] (63) YES (64) PiDP (65) UsableRulesProof [EQUIVALENT, 0 ms] (66) PiDP (67) PiDPToQDPProof [SOUND, 0 ms] (68) QDP (69) PrologToTRSTransformerProof [SOUND, 28 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, 28 ms] (89) AND (90) IRSwT (91) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (92) IRSwT (93) IntTRSCompressionProof [EQUIVALENT, 23 ms] (94) IRSwT (95) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (96) IRSwT (97) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (98) IRSwT (99) TempFilterProof [SOUND, 5 ms] (100) IRSwT (101) IRSwTToQDPProof [SOUND, 1 ms] (102) QDP (103) QDPSizeChangeProof [EQUIVALENT, 0 ms] (104) YES (105) IRSwT (106) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (107) IRSwT (108) IntTRSCompressionProof [EQUIVALENT, 3 ms] (109) IRSwT (110) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (111) IRSwT (112) IRSwTTerminationDigraphProof [EQUIVALENT, 0 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, 21 ms] (124) IRSwT (125) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (126) IRSwT (127) IRSwTTerminationDigraphProof [EQUIVALENT, 45 ms] (128) IRSwT (129) IntTRSCompressionProof [EQUIVALENT, 15 ms] (130) IRSwT (131) IRSwTToIntTRSProof [SOUND, 19 ms] (132) IRSwT (133) IntTRSCompressionProof [EQUIVALENT, 14 ms] (134) IRSwT (135) PrologToDTProblemTransformerProof [SOUND, 38 ms] (136) TRIPLES (137) TriplesToPiDPProof [SOUND, 11 ms] (138) PiDP (139) DependencyGraphProof [EQUIVALENT, 0 ms] (140) AND (141) PiDP (142) UsableRulesProof [EQUIVALENT, 0 ms] (143) PiDP (144) PiDPToQDPProof [SOUND, 0 ms] (145) QDP (146) QDPSizeChangeProof [EQUIVALENT, 0 ms] (147) YES (148) PiDP (149) UsableRulesProof [EQUIVALENT, 0 ms] (150) PiDP (151) PiDPToQDPProof [SOUND, 0 ms] (152) QDP (153) QDPSizeChangeProof [EQUIVALENT, 0 ms] (154) YES (155) PiDP (156) PiDPToQDPProof [SOUND, 0 ms] (157) QDP ---------------------------------------- (0) Obligation: Clauses: in(X, tree(X, X1, X2)). in(X, tree(Y, Left, X3)) :- ','(less(X, Y), in(X, Left)). in(X, tree(Y, X4, Right)) :- ','(less(Y, X), in(X, Right)). less(0, s(X5)). less(s(X), s(Y)) :- less(X, Y). Query: in(g,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: in_in_2: (b,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: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) ---------------------------------------- (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: IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, Left, X3)) -> 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_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_GA(X, Y, Left, X3, in_in_ga(X, Left)) U1_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) IN_IN_GA(X, tree(Y, X4, Right)) -> 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_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_GA(X, Y, X4, Right, in_in_ga(X, Right)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x3) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x3) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, Left, X3)) -> 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_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_GA(X, Y, Left, X3, in_in_ga(X, Left)) U1_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) IN_IN_GA(X, tree(Y, X4, Right)) -> 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_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_GA(X, Y, X4, Right, in_in_ga(X, Right)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x3) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x3) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) 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: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 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: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 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_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x5) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) 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_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) 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_GA(X, less_out_ga) -> IN_IN_GA(X) IN_IN_GA(X) -> U1_GA(X, less_in_ga(X)) IN_IN_GA(X) -> U3_GA(X, less_in_ag(X)) U3_GA(X, less_out_ag(Y)) -> IN_IN_GA(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(X5)) -> 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. ---------------------------------------- (26) TransformationProof (SOUND) By narrowing [LPAR04] the rule IN_IN_GA(X) -> U1_GA(X, less_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (IN_IN_GA(0) -> U1_GA(0, less_out_ga),IN_IN_GA(0) -> U1_GA(0, less_out_ga)) (IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(less_in_ga(x0))),IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(less_in_ga(x0)))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(X, less_out_ga) -> IN_IN_GA(X) IN_IN_GA(X) -> U3_GA(X, less_in_ag(X)) U3_GA(X, less_out_ag(Y)) -> IN_IN_GA(X) IN_IN_GA(0) -> U1_GA(0, less_out_ga) IN_IN_GA(s(x0)) -> U1_GA(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(X5)) -> 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. ---------------------------------------- (28) TransformationProof (SOUND) By narrowing [LPAR04] the rule IN_IN_GA(X) -> U3_GA(X, less_in_ag(X)) at position [1] we obtained the following new rules [LPAR04]: (IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0)),IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0))) (IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(less_in_ag(x0))),IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(less_in_ag(x0)))) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(X, less_out_ga) -> IN_IN_GA(X) U3_GA(X, less_out_ag(Y)) -> IN_IN_GA(X) IN_IN_GA(0) -> U1_GA(0, less_out_ga) IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(less_in_ga(x0))) IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0)) IN_IN_GA(s(x0)) -> U3_GA(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(X5)) -> 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. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_GA(X, less_out_ga) -> IN_IN_GA(X) we obtained the following new rules [LPAR04]: (U1_GA(0, less_out_ga) -> IN_IN_GA(0),U1_GA(0, less_out_ga) -> IN_IN_GA(0)) (U1_GA(s(z0), less_out_ga) -> IN_IN_GA(s(z0)),U1_GA(s(z0), less_out_ga) -> IN_IN_GA(s(z0))) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GA(X, less_out_ag(Y)) -> IN_IN_GA(X) IN_IN_GA(0) -> U1_GA(0, less_out_ga) IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(less_in_ga(x0))) IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0)) IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(less_in_ag(x0))) U1_GA(0, less_out_ga) -> IN_IN_GA(0) U1_GA(s(z0), less_out_ga) -> IN_IN_GA(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(X5)) -> 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. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (33) Complex Obligation (AND) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(0, less_out_ga) -> IN_IN_GA(0) IN_IN_GA(0) -> U1_GA(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(X5)) -> 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. ---------------------------------------- (35) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(0, less_out_ga) -> IN_IN_GA(0) IN_IN_GA(0) -> U1_GA(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. ---------------------------------------- (37) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. less_in_ga(x0) less_in_ag(x0) U5_ga(x0) U5_ag(x0) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(0, less_out_ga) -> IN_IN_GA(0) IN_IN_GA(0) -> U1_GA(0, less_out_ga) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) 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 = IN_IN_GA(0) evaluates to t =IN_IN_GA(0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence IN_IN_GA(0) -> U1_GA(0, less_out_ga) with rule IN_IN_GA(0) -> U1_GA(0, less_out_ga) at position [] and matcher [ ] U1_GA(0, less_out_ga) -> IN_IN_GA(0) with rule U1_GA(0, less_out_ga) -> IN_IN_GA(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. ---------------------------------------- (40) NO ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(less_in_ga(x0))) U1_GA(s(z0), less_out_ga) -> IN_IN_GA(s(z0)) IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0)) U3_GA(X, less_out_ag(Y)) -> IN_IN_GA(X) IN_IN_GA(s(x0)) -> U3_GA(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(X5)) -> 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. ---------------------------------------- (42) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U3_GA(X, less_out_ag(Y)) -> IN_IN_GA(X) we obtained the following new rules [LPAR04]: (U3_GA(s(z0), less_out_ag(0)) -> IN_IN_GA(s(z0)),U3_GA(s(z0), less_out_ag(0)) -> IN_IN_GA(s(z0))) (U3_GA(s(z0), less_out_ag(x1)) -> IN_IN_GA(s(z0)),U3_GA(s(z0), less_out_ag(x1)) -> IN_IN_GA(s(z0))) ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(less_in_ga(x0))) U1_GA(s(z0), less_out_ga) -> IN_IN_GA(s(z0)) IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0)) IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(less_in_ag(x0))) U3_GA(s(z0), less_out_ag(0)) -> IN_IN_GA(s(z0)) U3_GA(s(z0), less_out_ag(x1)) -> IN_IN_GA(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(X5)) -> 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. ---------------------------------------- (44) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: in_in_2: (b,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: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (45) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) ---------------------------------------- (46) 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: IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, Left, X3)) -> 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_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_GA(X, Y, Left, X3, in_in_ga(X, Left)) U1_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) IN_IN_GA(X, tree(Y, X4, Right)) -> 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_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_GA(X, Y, X4, Right, in_in_ga(X, Right)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x1, x3) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x2, x3) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) Obligation: Pi DP problem: The TRS P consists of the following rules: IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, Left, X3)) -> 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_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_GA(X, Y, Left, X3, in_in_ga(X, Left)) U1_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) IN_IN_GA(X, tree(Y, X4, Right)) -> 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_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_GA(X, Y, X4, Right, in_in_ga(X, Right)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x1, x3) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) U5_AG(x1, x2, x3) = U5_AG(x2, x3) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (48) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (49) Complex Obligation (AND) ---------------------------------------- (50) 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: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) LESS_IN_AG(x1, x2) = LESS_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (51) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: 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 ---------------------------------------- (53) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (55) 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 ---------------------------------------- (56) YES ---------------------------------------- (57) 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: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) LESS_IN_GA(x1, x2) = LESS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (58) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (59) 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 ---------------------------------------- (60) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (61) 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. ---------------------------------------- (62) 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 ---------------------------------------- (63) YES ---------------------------------------- (64) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: in_in_ga(X, tree(X, X1, X2)) -> in_out_ga(X, tree(X, X1, X2)) in_in_ga(X, tree(Y, Left, X3)) -> U1_ga(X, Y, Left, X3, less_in_ga(X, Y)) less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) 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_ga(X, Y, Left, X3, less_out_ga(X, Y)) -> U2_ga(X, Y, Left, X3, in_in_ga(X, Left)) in_in_ga(X, tree(Y, X4, Right)) -> U3_ga(X, Y, X4, Right, less_in_ag(Y, X)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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_ga(X, Y, X4, Right, less_out_ag(Y, X)) -> U4_ga(X, Y, X4, Right, in_in_ga(X, Right)) U4_ga(X, Y, X4, Right, in_out_ga(X, Right)) -> in_out_ga(X, tree(Y, X4, Right)) U2_ga(X, Y, Left, X3, in_out_ga(X, Left)) -> in_out_ga(X, tree(Y, Left, X3)) The argument filtering Pi contains the following mapping: in_in_ga(x1, x2) = in_in_ga(x1) in_out_ga(x1, x2) = in_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x5) 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_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (65) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (66) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GA(X, Y, Left, X3, less_out_ga(X, Y)) -> IN_IN_GA(X, Left) IN_IN_GA(X, tree(Y, Left, X3)) -> U1_GA(X, Y, Left, X3, less_in_ga(X, Y)) IN_IN_GA(X, tree(Y, X4, Right)) -> U3_GA(X, Y, X4, Right, less_in_ag(Y, X)) U3_GA(X, Y, X4, Right, less_out_ag(Y, X)) -> IN_IN_GA(X, Right) The TRS R consists of the following rules: less_in_ga(0, s(X5)) -> less_out_ga(0, s(X5)) less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y)) less_in_ag(0, s(X5)) -> less_out_ag(0, s(X5)) 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) IN_IN_GA(x1, x2) = IN_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (67) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(X, less_out_ga(X)) -> IN_IN_GA(X) IN_IN_GA(X) -> U1_GA(X, less_in_ga(X)) IN_IN_GA(X) -> U3_GA(X, less_in_ag(X)) U3_GA(X, less_out_ag(Y, X)) -> IN_IN_GA(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(X5)) -> less_out_ag(0, s(X5)) 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. ---------------------------------------- (69) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 27, "program": { "directives": [], "clauses": [ [ "(in X (tree X X1 X2))", null ], [ "(in X (tree Y Left X3))", "(',' (less X Y) (in X Left))" ], [ "(in X (tree Y X4 Right))", "(',' (less Y X) (in X Right))" ], [ "(less (0) (s X5))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "292": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "293": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "295": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "254": { "goal": [ { "clause": 3, "scope": 2, "term": "(less T34 T38)" }, { "clause": 4, "scope": 2, "term": "(less T34 T38)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "278": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T77 T73) (in T73 T78))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "311": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "257": { "goal": [{ "clause": 3, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "312": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "258": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "259": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "30": { "goal": [ { "clause": 0, "scope": 1, "term": "(in T1 T2)" }, { "clause": 1, "scope": 1, "term": "(in T1 T2)" }, { "clause": 2, "scope": 1, "term": "(in T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "58": { "goal": [{ "clause": 0, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "280": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "261": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T73 T81)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "262": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T54 T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "241": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "263": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T34 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "286": { "goal": [ { "clause": 3, "scope": 3, "term": "(less T77 T73)" }, { "clause": 4, "scope": 3, "term": "(less T77 T73)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "221": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "222": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "288": { "goal": [{ "clause": 3, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "289": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "224": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": 1, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "227": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "228": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T34 T38) (in T34 T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "229": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [ { "clause": 1, "scope": 1, "term": "(in T1 T2)" }, { "clause": 2, "scope": 1, "term": "(in T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 27, "to": 30, "label": "CASE" }, { "from": 30, "to": 58, "label": "PARALLEL" }, { "from": 30, "to": 60, "label": "PARALLEL" }, { "from": 58, "to": 221, "label": "EVAL with clause\nin(X18, tree(X18, X19, X20)).\nand substitutionT1 -> T15,\nX18 -> T15,\nX19 -> T16,\nX20 -> T17,\nT2 -> tree(T15, T16, T17)" }, { "from": 58, "to": 222, "label": "EVAL-BACKTRACK" }, { "from": 60, "to": 226, "label": "PARALLEL" }, { "from": 60, "to": 227, "label": "PARALLEL" }, { "from": 221, "to": 224, "label": "SUCCESS" }, { "from": 226, "to": 228, "label": "EVAL with clause\nin(X37, tree(X38, X39, X40)) :- ','(less(X37, X38), in(X37, X39)).\nand substitutionT1 -> T34,\nX37 -> T34,\nX38 -> T38,\nX39 -> T39,\nX40 -> T37,\nT2 -> tree(T38, T39, T37),\nT35 -> T38,\nT36 -> T39" }, { "from": 226, "to": 229, "label": "EVAL-BACKTRACK" }, { "from": 227, "to": 278, "label": "EVAL with clause\nin(X72, tree(X73, X74, X75)) :- ','(less(X73, X72), in(X72, X75)).\nand substitutionT1 -> T73,\nX72 -> T73,\nX73 -> T77,\nX74 -> T75,\nX75 -> T78,\nT2 -> tree(T77, T75, T78),\nT74 -> T77,\nT76 -> T78" }, { "from": 227, "to": 280, "label": "EVAL-BACKTRACK" }, { "from": 228, "to": 241, "label": "SPLIT 1" }, { "from": 228, "to": 242, "label": "SPLIT 2\nnew knowledge:\nT34 is ground\nreplacements:T39 -> T42" }, { "from": 241, "to": 254, "label": "CASE" }, { "from": 242, "to": 27, "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T42" }, { "from": 254, "to": 257, "label": "PARALLEL" }, { "from": 254, "to": 258, "label": "PARALLEL" }, { "from": 257, "to": 259, "label": "EVAL with clause\nless(0, s(X49)).\nand substitutionT34 -> 0,\nX49 -> T49,\nT38 -> s(T49)" }, { "from": 257, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 258, "to": 262, "label": "EVAL with clause\nless(s(X54), s(X55)) :- less(X54, X55).\nand substitutionX54 -> T54,\nT34 -> s(T54),\nX55 -> T56,\nT38 -> s(T56),\nT55 -> T56" }, { "from": 258, "to": 263, "label": "EVAL-BACKTRACK" }, { "from": 259, "to": 261, "label": "SUCCESS" }, { "from": 262, "to": 241, "label": "INSTANCE with matching:\nT34 -> T54\nT38 -> T56" }, { "from": 278, "to": 282, "label": "SPLIT 1" }, { "from": 278, "to": 283, "label": "SPLIT 2\nnew knowledge:\nT77 is ground\nT73 is ground\nreplacements:T78 -> T81" }, { "from": 282, "to": 286, "label": "CASE" }, { "from": 283, "to": 27, "label": "INSTANCE with matching:\nT1 -> T73\nT2 -> T81" }, { "from": 286, "to": 288, "label": "PARALLEL" }, { "from": 286, "to": 289, "label": "PARALLEL" }, { "from": 288, "to": 292, "label": "EVAL with clause\nless(0, s(X84)).\nand substitutionT77 -> 0,\nX84 -> T88,\nT73 -> s(T88)" }, { "from": 288, "to": 293, "label": "EVAL-BACKTRACK" }, { "from": 289, "to": 311, "label": "EVAL with clause\nless(s(X89), s(X90)) :- less(X89, X90).\nand substitutionX89 -> T95,\nT77 -> s(T95),\nX90 -> T94,\nT73 -> s(T94),\nT93 -> T95" }, { "from": 289, "to": 312, "label": "EVAL-BACKTRACK" }, { "from": 292, "to": 295, "label": "SUCCESS" }, { "from": 311, "to": 282, "label": "INSTANCE with matching:\nT77 -> T95\nT73 -> T94" } ], "type": "Graph" } } ---------------------------------------- (70) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f27_in(T15) -> f27_out1 f27_in(T34) -> U1(f228_in(T34), T34) U1(f228_out1, T34) -> f27_out1 f27_in(T73) -> U2(f278_in(T73), T73) U2(f278_out1(T77), T73) -> f27_out1 f241_in(0) -> f241_out1 f241_in(s(T54)) -> U3(f241_in(T54), s(T54)) U3(f241_out1, s(T54)) -> f241_out1 f282_in(s(T88)) -> f282_out1(0) f282_in(s(T94)) -> U4(f282_in(T94), s(T94)) U4(f282_out1(T95), s(T94)) -> f282_out1(s(T95)) f228_in(T34) -> U5(f241_in(T34), T34) U5(f241_out1, T34) -> U6(f27_in(T34), T34) U6(f27_out1, T34) -> f228_out1 f278_in(T73) -> U7(f282_in(T73), T73) U7(f282_out1(T77), T73) -> U8(f27_in(T73), T73, T77) U8(f27_out1, T73, T77) -> f278_out1(T77) 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: F27_IN(T34) -> U1^1(f228_in(T34), T34) F27_IN(T34) -> F228_IN(T34) F27_IN(T73) -> U2^1(f278_in(T73), T73) F27_IN(T73) -> F278_IN(T73) F241_IN(s(T54)) -> U3^1(f241_in(T54), s(T54)) F241_IN(s(T54)) -> F241_IN(T54) F282_IN(s(T94)) -> U4^1(f282_in(T94), s(T94)) F282_IN(s(T94)) -> F282_IN(T94) F228_IN(T34) -> U5^1(f241_in(T34), T34) F228_IN(T34) -> F241_IN(T34) U5^1(f241_out1, T34) -> U6^1(f27_in(T34), T34) U5^1(f241_out1, T34) -> F27_IN(T34) F278_IN(T73) -> U7^1(f282_in(T73), T73) F278_IN(T73) -> F282_IN(T73) U7^1(f282_out1(T77), T73) -> U8^1(f27_in(T73), T73, T77) U7^1(f282_out1(T77), T73) -> F27_IN(T73) The TRS R consists of the following rules: f27_in(T15) -> f27_out1 f27_in(T34) -> U1(f228_in(T34), T34) U1(f228_out1, T34) -> f27_out1 f27_in(T73) -> U2(f278_in(T73), T73) U2(f278_out1(T77), T73) -> f27_out1 f241_in(0) -> f241_out1 f241_in(s(T54)) -> U3(f241_in(T54), s(T54)) U3(f241_out1, s(T54)) -> f241_out1 f282_in(s(T88)) -> f282_out1(0) f282_in(s(T94)) -> U4(f282_in(T94), s(T94)) U4(f282_out1(T95), s(T94)) -> f282_out1(s(T95)) f228_in(T34) -> U5(f241_in(T34), T34) U5(f241_out1, T34) -> U6(f27_in(T34), T34) U6(f27_out1, T34) -> f228_out1 f278_in(T73) -> U7(f282_in(T73), T73) U7(f282_out1(T77), T73) -> U8(f27_in(T73), T73, T77) U8(f27_out1, T73, T77) -> f278_out1(T77) 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: F282_IN(s(T94)) -> F282_IN(T94) The TRS R consists of the following rules: f27_in(T15) -> f27_out1 f27_in(T34) -> U1(f228_in(T34), T34) U1(f228_out1, T34) -> f27_out1 f27_in(T73) -> U2(f278_in(T73), T73) U2(f278_out1(T77), T73) -> f27_out1 f241_in(0) -> f241_out1 f241_in(s(T54)) -> U3(f241_in(T54), s(T54)) U3(f241_out1, s(T54)) -> f241_out1 f282_in(s(T88)) -> f282_out1(0) f282_in(s(T94)) -> U4(f282_in(T94), s(T94)) U4(f282_out1(T95), s(T94)) -> f282_out1(s(T95)) f228_in(T34) -> U5(f241_in(T34), T34) U5(f241_out1, T34) -> U6(f27_in(T34), T34) U6(f27_out1, T34) -> f228_out1 f278_in(T73) -> U7(f282_in(T73), T73) U7(f282_out1(T77), T73) -> U8(f27_in(T73), T73, T77) U8(f27_out1, T73, T77) -> f278_out1(T77) 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: F282_IN(s(T94)) -> F282_IN(T94) 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: *F282_IN(s(T94)) -> F282_IN(T94) The graph contains the following edges 1 > 1 ---------------------------------------- (79) YES ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: F241_IN(s(T54)) -> F241_IN(T54) The TRS R consists of the following rules: f27_in(T15) -> f27_out1 f27_in(T34) -> U1(f228_in(T34), T34) U1(f228_out1, T34) -> f27_out1 f27_in(T73) -> U2(f278_in(T73), T73) U2(f278_out1(T77), T73) -> f27_out1 f241_in(0) -> f241_out1 f241_in(s(T54)) -> U3(f241_in(T54), s(T54)) U3(f241_out1, s(T54)) -> f241_out1 f282_in(s(T88)) -> f282_out1(0) f282_in(s(T94)) -> U4(f282_in(T94), s(T94)) U4(f282_out1(T95), s(T94)) -> f282_out1(s(T95)) f228_in(T34) -> U5(f241_in(T34), T34) U5(f241_out1, T34) -> U6(f27_in(T34), T34) U6(f27_out1, T34) -> f228_out1 f278_in(T73) -> U7(f282_in(T73), T73) U7(f282_out1(T77), T73) -> U8(f27_in(T73), T73, T77) U8(f27_out1, T73, T77) -> f278_out1(T77) 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: F241_IN(s(T54)) -> F241_IN(T54) 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: *F241_IN(s(T54)) -> F241_IN(T54) The graph contains the following edges 1 > 1 ---------------------------------------- (84) YES ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: F27_IN(T34) -> F228_IN(T34) F228_IN(T34) -> U5^1(f241_in(T34), T34) U5^1(f241_out1, T34) -> F27_IN(T34) F27_IN(T73) -> F278_IN(T73) F278_IN(T73) -> U7^1(f282_in(T73), T73) U7^1(f282_out1(T77), T73) -> F27_IN(T73) The TRS R consists of the following rules: f27_in(T15) -> f27_out1 f27_in(T34) -> U1(f228_in(T34), T34) U1(f228_out1, T34) -> f27_out1 f27_in(T73) -> U2(f278_in(T73), T73) U2(f278_out1(T77), T73) -> f27_out1 f241_in(0) -> f241_out1 f241_in(s(T54)) -> U3(f241_in(T54), s(T54)) U3(f241_out1, s(T54)) -> f241_out1 f282_in(s(T88)) -> f282_out1(0) f282_in(s(T94)) -> U4(f282_in(T94), s(T94)) U4(f282_out1(T95), s(T94)) -> f282_out1(s(T95)) f228_in(T34) -> U5(f241_in(T34), T34) U5(f241_out1, T34) -> U6(f27_in(T34), T34) U6(f27_out1, T34) -> f228_out1 f278_in(T73) -> U7(f282_in(T73), T73) U7(f282_out1(T77), T73) -> U8(f27_in(T73), T73, T77) U8(f27_out1, T73, T77) -> f278_out1(T77) 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 = F228_IN(0) evaluates to t =F228_IN(0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F228_IN(0) -> U5^1(f241_in(0), 0) with rule F228_IN(T34) -> U5^1(f241_in(T34), T34) at position [] and matcher [T34 / 0] U5^1(f241_in(0), 0) -> U5^1(f241_out1, 0) with rule f241_in(0) -> f241_out1 at position [0] and matcher [ ] U5^1(f241_out1, 0) -> F27_IN(0) with rule U5^1(f241_out1, T34') -> F27_IN(T34') at position [] and matcher [T34' / 0] F27_IN(0) -> F228_IN(0) with rule F27_IN(T34) -> F228_IN(T34) 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": 14, "program": { "directives": [], "clauses": [ [ "(in X (tree X X1 X2))", null ], [ "(in X (tree Y Left X3))", "(',' (less X Y) (in X Left))" ], [ "(in X (tree Y X4 Right))", "(',' (less Y X) (in X Right))" ], [ "(less (0) (s X5))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "88": { "goal": [{ "clause": 0, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "89": { "goal": [ { "clause": 1, "scope": 1, "term": "(in T1 T2)" }, { "clause": 2, "scope": 1, "term": "(in T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "290": { "goal": [{ "clause": 3, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "291": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "type": "Nodes", "250": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "251": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "252": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "253": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "255": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T54 T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "256": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T77 T73) (in T73 T78))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": 1, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "237": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "238": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T34 T38) (in T34 T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "239": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "17": { "goal": [ { "clause": 0, "scope": 1, "term": "(in T1 T2)" }, { "clause": 1, "scope": 1, "term": "(in T1 T2)" }, { "clause": 2, "scope": 1, "term": "(in T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "281": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "284": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "285": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T73 T81)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "243": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T34 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "287": { "goal": [ { "clause": 3, "scope": 3, "term": "(less T77 T73)" }, { "clause": 4, "scope": 3, "term": "(less T77 T73)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "223": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "322": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "323": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "225": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "324": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "248": { "goal": [ { "clause": 3, "scope": 2, "term": "(less T34 T38)" }, { "clause": 4, "scope": 2, "term": "(less T34 T38)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "325": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "249": { "goal": [{ "clause": 3, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "326": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 14, "to": 17, "label": "CASE" }, { "from": 17, "to": 88, "label": "PARALLEL" }, { "from": 17, "to": 89, "label": "PARALLEL" }, { "from": 88, "to": 220, "label": "EVAL with clause\nin(X18, tree(X18, X19, X20)).\nand substitutionT1 -> T15,\nX18 -> T15,\nX19 -> T16,\nX20 -> T17,\nT2 -> tree(T15, T16, T17)" }, { "from": 88, "to": 223, "label": "EVAL-BACKTRACK" }, { "from": 89, "to": 236, "label": "PARALLEL" }, { "from": 89, "to": 237, "label": "PARALLEL" }, { "from": 220, "to": 225, "label": "SUCCESS" }, { "from": 236, "to": 238, "label": "EVAL with clause\nin(X37, tree(X38, X39, X40)) :- ','(less(X37, X38), in(X37, X39)).\nand substitutionT1 -> T34,\nX37 -> T34,\nX38 -> T38,\nX39 -> T39,\nX40 -> T37,\nT2 -> tree(T38, T39, T37),\nT35 -> T38,\nT36 -> T39" }, { "from": 236, "to": 239, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 279, "label": "EVAL with clause\nin(X72, tree(X73, X74, X75)) :- ','(less(X73, X72), in(X72, X75)).\nand substitutionT1 -> T73,\nX72 -> T73,\nX73 -> T77,\nX74 -> T75,\nX75 -> T78,\nT2 -> tree(T77, T75, T78),\nT74 -> T77,\nT76 -> T78" }, { "from": 237, "to": 281, "label": "EVAL-BACKTRACK" }, { "from": 238, "to": 240, "label": "SPLIT 1" }, { "from": 238, "to": 243, "label": "SPLIT 2\nnew knowledge:\nT34 is ground\nreplacements:T39 -> T42" }, { "from": 240, "to": 248, "label": "CASE" }, { "from": 243, "to": 14, "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T42" }, { "from": 248, "to": 249, "label": "PARALLEL" }, { "from": 248, "to": 250, "label": "PARALLEL" }, { "from": 249, "to": 251, "label": "EVAL with clause\nless(0, s(X49)).\nand substitutionT34 -> 0,\nX49 -> T49,\nT38 -> s(T49)" }, { "from": 249, "to": 252, "label": "EVAL-BACKTRACK" }, { "from": 250, "to": 255, "label": "EVAL with clause\nless(s(X54), s(X55)) :- less(X54, X55).\nand substitutionX54 -> T54,\nT34 -> s(T54),\nX55 -> T56,\nT38 -> s(T56),\nT55 -> T56" }, { "from": 250, "to": 256, "label": "EVAL-BACKTRACK" }, { "from": 251, "to": 253, "label": "SUCCESS" }, { "from": 255, "to": 240, "label": "INSTANCE with matching:\nT34 -> T54\nT38 -> T56" }, { "from": 279, "to": 284, "label": "SPLIT 1" }, { "from": 279, "to": 285, "label": "SPLIT 2\nnew knowledge:\nT77 is ground\nT73 is ground\nreplacements:T78 -> T81" }, { "from": 284, "to": 287, "label": "CASE" }, { "from": 285, "to": 14, "label": "INSTANCE with matching:\nT1 -> T73\nT2 -> T81" }, { "from": 287, "to": 290, "label": "PARALLEL" }, { "from": 287, "to": 291, "label": "PARALLEL" }, { "from": 290, "to": 322, "label": "EVAL with clause\nless(0, s(X84)).\nand substitutionT77 -> 0,\nX84 -> T88,\nT73 -> s(T88)" }, { "from": 290, "to": 323, "label": "EVAL-BACKTRACK" }, { "from": 291, "to": 325, "label": "EVAL with clause\nless(s(X89), s(X90)) :- less(X89, X90).\nand substitutionX89 -> T95,\nT77 -> s(T95),\nX90 -> T94,\nT73 -> s(T94),\nT93 -> T95" }, { "from": 291, "to": 326, "label": "EVAL-BACKTRACK" }, { "from": 322, "to": 324, "label": "SUCCESS" }, { "from": 325, "to": 284, "label": "INSTANCE with matching:\nT77 -> T95\nT73 -> T94" } ], "type": "Graph" } } ---------------------------------------- (89) Complex Obligation (AND) ---------------------------------------- (90) Obligation: Rules: f284_in(T73) -> f287_in(T73) :|: TRUE f287_out(x) -> f284_out(x) :|: TRUE f291_in(x1) -> f326_in :|: TRUE f291_in(s(T94)) -> f325_in(T94) :|: TRUE f326_out -> f291_out(x2) :|: TRUE f325_out(x3) -> f291_out(s(x3)) :|: TRUE f290_out(x4) -> f287_out(x4) :|: TRUE f287_in(x5) -> f291_in(x5) :|: TRUE f291_out(x6) -> f287_out(x6) :|: TRUE f287_in(x7) -> f290_in(x7) :|: TRUE f325_in(x8) -> f284_in(x8) :|: TRUE f284_out(x9) -> f325_out(x9) :|: TRUE f14_in(T1) -> f17_in(T1) :|: TRUE f17_out(x10) -> f14_out(x10) :|: TRUE f17_in(x11) -> f88_in(x11) :|: TRUE f89_out(x12) -> f17_out(x12) :|: TRUE f88_out(x13) -> f17_out(x13) :|: TRUE f17_in(x14) -> f89_in(x14) :|: TRUE f89_in(x15) -> f236_in(x15) :|: TRUE f237_out(x16) -> f89_out(x16) :|: TRUE f89_in(x17) -> f237_in(x17) :|: TRUE f236_out(x18) -> f89_out(x18) :|: TRUE f281_out -> f237_out(x19) :|: TRUE f237_in(x20) -> f279_in(x20) :|: TRUE f237_in(x21) -> f281_in :|: TRUE f279_out(x22) -> f237_out(x22) :|: TRUE f279_in(x23) -> f284_in(x23) :|: TRUE f284_out(x24) -> f285_in(x24) :|: TRUE f285_out(x25) -> f279_out(x25) :|: TRUE Start term: f14_in(T1) ---------------------------------------- (91) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f284_in(T73) -> f287_in(T73) :|: TRUE f291_in(s(T94)) -> f325_in(T94) :|: TRUE f287_in(x5) -> f291_in(x5) :|: TRUE f325_in(x8) -> f284_in(x8) :|: TRUE ---------------------------------------- (92) Obligation: Rules: f284_in(T73) -> f287_in(T73) :|: TRUE f291_in(s(T94)) -> f325_in(T94) :|: TRUE f287_in(x5) -> f291_in(x5) :|: TRUE f325_in(x8) -> f284_in(x8) :|: TRUE ---------------------------------------- (93) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (94) Obligation: Rules: f284_in(s(T94:0)) -> f284_in(T94:0) :|: TRUE ---------------------------------------- (95) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (96) Obligation: Rules: f284_in(s(T94:0)) -> f284_in(T94:0) :|: TRUE ---------------------------------------- (97) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f284_in(s(T94:0)) -> f284_in(T94:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (98) Obligation: Termination digraph: Nodes: (1) f284_in(s(T94:0)) -> f284_in(T94:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (99) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f284_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (100) Obligation: Rules: f284_in(s(T94:0)) -> f284_in(T94: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: f284_in(s(T94:0)) -> f284_in(T94: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: *f284_in(s(T94:0)) -> f284_in(T94:0) The graph contains the following edges 1 > 1 ---------------------------------------- (104) YES ---------------------------------------- (105) Obligation: Rules: f255_in(T54) -> f240_in(T54) :|: TRUE f240_out(x) -> f255_out(x) :|: TRUE f240_in(T34) -> f248_in(T34) :|: TRUE f248_out(x1) -> f240_out(x1) :|: TRUE f250_in(s(x2)) -> f255_in(x2) :|: TRUE f255_out(x3) -> f250_out(s(x3)) :|: TRUE f250_in(x4) -> f256_in :|: TRUE f256_out -> f250_out(x5) :|: TRUE f248_in(x6) -> f249_in(x6) :|: TRUE f249_out(x7) -> f248_out(x7) :|: TRUE f250_out(x8) -> f248_out(x8) :|: TRUE f248_in(x9) -> f250_in(x9) :|: TRUE f14_in(T1) -> f17_in(T1) :|: TRUE f17_out(x10) -> f14_out(x10) :|: TRUE f17_in(x11) -> f88_in(x11) :|: TRUE f89_out(x12) -> f17_out(x12) :|: TRUE f88_out(x13) -> f17_out(x13) :|: TRUE f17_in(x14) -> f89_in(x14) :|: TRUE f89_in(x15) -> f236_in(x15) :|: TRUE f237_out(x16) -> f89_out(x16) :|: TRUE f89_in(x17) -> f237_in(x17) :|: TRUE f236_out(x18) -> f89_out(x18) :|: TRUE f236_in(x19) -> f238_in(x19) :|: TRUE f239_out -> f236_out(x20) :|: TRUE f238_out(x21) -> f236_out(x21) :|: TRUE f236_in(x22) -> f239_in :|: TRUE f238_in(x23) -> f240_in(x23) :|: TRUE f243_out(x24) -> f238_out(x24) :|: TRUE f240_out(x25) -> f243_in(x25) :|: TRUE Start term: f14_in(T1) ---------------------------------------- (106) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f255_in(T54) -> f240_in(T54) :|: TRUE f240_in(T34) -> f248_in(T34) :|: TRUE f250_in(s(x2)) -> f255_in(x2) :|: TRUE f248_in(x9) -> f250_in(x9) :|: TRUE ---------------------------------------- (107) Obligation: Rules: f255_in(T54) -> f240_in(T54) :|: TRUE f240_in(T34) -> f248_in(T34) :|: TRUE f250_in(s(x2)) -> f255_in(x2) :|: TRUE f248_in(x9) -> f250_in(x9) :|: TRUE ---------------------------------------- (108) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (109) Obligation: Rules: f250_in(s(x2:0)) -> f250_in(x2:0) :|: TRUE ---------------------------------------- (110) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (111) Obligation: Rules: f250_in(s(x2:0)) -> f250_in(x2:0) :|: TRUE ---------------------------------------- (112) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f250_in(s(x2:0)) -> f250_in(x2:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (113) Obligation: Termination digraph: Nodes: (1) f250_in(s(x2:0)) -> f250_in(x2:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (114) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f250_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (115) Obligation: Rules: f250_in(s(x2:0)) -> f250_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: f250_in(s(x2:0)) -> f250_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: *f250_in(s(x2:0)) -> f250_in(x2:0) The graph contains the following edges 1 > 1 ---------------------------------------- (119) YES ---------------------------------------- (120) Obligation: Rules: f255_in(T54) -> f240_in(T54) :|: TRUE f240_out(x) -> f255_out(x) :|: TRUE f322_in -> f322_out :|: TRUE f14_in(T1) -> f17_in(T1) :|: TRUE f17_out(x1) -> f14_out(x1) :|: TRUE f281_out -> f237_out(x2) :|: TRUE f237_in(T73) -> f279_in(T73) :|: TRUE f237_in(x3) -> f281_in :|: TRUE f279_out(x4) -> f237_out(x4) :|: TRUE f250_in(s(x5)) -> f255_in(x5) :|: TRUE f255_out(x6) -> f250_out(s(x6)) :|: TRUE f250_in(T34) -> f256_in :|: TRUE f256_out -> f250_out(x7) :|: TRUE f236_in(x8) -> f238_in(x8) :|: TRUE f239_out -> f236_out(x9) :|: TRUE f238_out(x10) -> f236_out(x10) :|: TRUE f236_in(x11) -> f239_in :|: TRUE f279_in(x12) -> f284_in(x12) :|: TRUE f284_out(x13) -> f285_in(x13) :|: TRUE f285_out(x14) -> f279_out(x14) :|: TRUE f322_out -> f290_out(s(T88)) :|: TRUE f290_in(x15) -> f323_in :|: TRUE f323_out -> f290_out(x16) :|: TRUE f290_in(s(x17)) -> f322_in :|: TRUE f290_out(x18) -> f287_out(x18) :|: TRUE f287_in(x19) -> f291_in(x19) :|: TRUE f291_out(x20) -> f287_out(x20) :|: TRUE f287_in(x21) -> f290_in(x21) :|: TRUE f249_in(x22) -> f252_in :|: TRUE f252_out -> f249_out(x23) :|: TRUE f249_in(0) -> f251_in :|: TRUE f251_out -> f249_out(0) :|: TRUE f243_in(x24) -> f14_in(x24) :|: TRUE f14_out(x25) -> f243_out(x25) :|: TRUE f284_in(x26) -> f287_in(x26) :|: TRUE f287_out(x27) -> f284_out(x27) :|: TRUE f291_in(x28) -> f326_in :|: TRUE f291_in(s(T94)) -> f325_in(T94) :|: TRUE f326_out -> f291_out(x29) :|: TRUE f325_out(x30) -> f291_out(s(x30)) :|: TRUE f89_in(x31) -> f236_in(x31) :|: TRUE f237_out(x32) -> f89_out(x32) :|: TRUE f89_in(x33) -> f237_in(x33) :|: TRUE f236_out(x34) -> f89_out(x34) :|: TRUE f285_in(x35) -> f14_in(x35) :|: TRUE f14_out(x36) -> f285_out(x36) :|: TRUE f238_in(x37) -> f240_in(x37) :|: TRUE f243_out(x38) -> f238_out(x38) :|: TRUE f240_out(x39) -> f243_in(x39) :|: TRUE f325_in(x40) -> f284_in(x40) :|: TRUE f284_out(x41) -> f325_out(x41) :|: TRUE f251_in -> f251_out :|: TRUE f17_in(x42) -> f88_in(x42) :|: TRUE f89_out(x43) -> f17_out(x43) :|: TRUE f88_out(x44) -> f17_out(x44) :|: TRUE f17_in(x45) -> f89_in(x45) :|: TRUE f240_in(x46) -> f248_in(x46) :|: TRUE f248_out(x47) -> f240_out(x47) :|: TRUE f248_in(x48) -> f249_in(x48) :|: TRUE f249_out(x49) -> f248_out(x49) :|: TRUE f250_out(x50) -> f248_out(x50) :|: TRUE f248_in(x51) -> f250_in(x51) :|: TRUE Start term: f14_in(T1) ---------------------------------------- (121) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f255_in(T54) -> f240_in(T54) :|: TRUE f240_out(x) -> f255_out(x) :|: TRUE f322_in -> f322_out :|: TRUE f14_in(T1) -> f17_in(T1) :|: TRUE f237_in(T73) -> f279_in(T73) :|: TRUE f250_in(s(x5)) -> f255_in(x5) :|: TRUE f255_out(x6) -> f250_out(s(x6)) :|: TRUE f236_in(x8) -> f238_in(x8) :|: TRUE f279_in(x12) -> f284_in(x12) :|: TRUE f284_out(x13) -> f285_in(x13) :|: TRUE f322_out -> f290_out(s(T88)) :|: TRUE f290_in(s(x17)) -> f322_in :|: TRUE f290_out(x18) -> f287_out(x18) :|: TRUE f287_in(x19) -> f291_in(x19) :|: TRUE f291_out(x20) -> f287_out(x20) :|: TRUE f287_in(x21) -> f290_in(x21) :|: TRUE f249_in(0) -> f251_in :|: TRUE f251_out -> f249_out(0) :|: TRUE f243_in(x24) -> f14_in(x24) :|: TRUE f284_in(x26) -> f287_in(x26) :|: TRUE f287_out(x27) -> f284_out(x27) :|: TRUE f291_in(s(T94)) -> f325_in(T94) :|: TRUE f325_out(x30) -> f291_out(s(x30)) :|: TRUE f89_in(x31) -> f236_in(x31) :|: TRUE f89_in(x33) -> f237_in(x33) :|: TRUE f285_in(x35) -> f14_in(x35) :|: TRUE f238_in(x37) -> f240_in(x37) :|: TRUE f240_out(x39) -> f243_in(x39) :|: TRUE f325_in(x40) -> f284_in(x40) :|: TRUE f284_out(x41) -> f325_out(x41) :|: TRUE f251_in -> f251_out :|: TRUE f17_in(x45) -> f89_in(x45) :|: TRUE f240_in(x46) -> f248_in(x46) :|: TRUE f248_out(x47) -> f240_out(x47) :|: TRUE f248_in(x48) -> f249_in(x48) :|: TRUE f249_out(x49) -> f248_out(x49) :|: TRUE f250_out(x50) -> f248_out(x50) :|: TRUE f248_in(x51) -> f250_in(x51) :|: TRUE ---------------------------------------- (122) Obligation: Rules: f255_in(T54) -> f240_in(T54) :|: TRUE f240_out(x) -> f255_out(x) :|: TRUE f322_in -> f322_out :|: TRUE f14_in(T1) -> f17_in(T1) :|: TRUE f237_in(T73) -> f279_in(T73) :|: TRUE f250_in(s(x5)) -> f255_in(x5) :|: TRUE f255_out(x6) -> f250_out(s(x6)) :|: TRUE f236_in(x8) -> f238_in(x8) :|: TRUE f279_in(x12) -> f284_in(x12) :|: TRUE f284_out(x13) -> f285_in(x13) :|: TRUE f322_out -> f290_out(s(T88)) :|: TRUE f290_in(s(x17)) -> f322_in :|: TRUE f290_out(x18) -> f287_out(x18) :|: TRUE f287_in(x19) -> f291_in(x19) :|: TRUE f291_out(x20) -> f287_out(x20) :|: TRUE f287_in(x21) -> f290_in(x21) :|: TRUE f249_in(0) -> f251_in :|: TRUE f251_out -> f249_out(0) :|: TRUE f243_in(x24) -> f14_in(x24) :|: TRUE f284_in(x26) -> f287_in(x26) :|: TRUE f287_out(x27) -> f284_out(x27) :|: TRUE f291_in(s(T94)) -> f325_in(T94) :|: TRUE f325_out(x30) -> f291_out(s(x30)) :|: TRUE f89_in(x31) -> f236_in(x31) :|: TRUE f89_in(x33) -> f237_in(x33) :|: TRUE f285_in(x35) -> f14_in(x35) :|: TRUE f238_in(x37) -> f240_in(x37) :|: TRUE f240_out(x39) -> f243_in(x39) :|: TRUE f325_in(x40) -> f284_in(x40) :|: TRUE f284_out(x41) -> f325_out(x41) :|: TRUE f251_in -> f251_out :|: TRUE f17_in(x45) -> f89_in(x45) :|: TRUE f240_in(x46) -> f248_in(x46) :|: TRUE f248_out(x47) -> f240_out(x47) :|: TRUE f248_in(x48) -> f249_in(x48) :|: TRUE f249_out(x49) -> f248_out(x49) :|: TRUE f250_out(x50) -> f248_out(x50) :|: TRUE f248_in(x51) -> f250_in(x51) :|: TRUE ---------------------------------------- (123) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (124) Obligation: Rules: f284_out(x41:0) -> f284_out(s(x41:0)) :|: TRUE f284_out(x13:0) -> f89_in(x13:0) :|: TRUE f89_in(x31:0) -> f248_in(x31:0) :|: TRUE f287_in(s(T94:0)) -> f287_in(T94:0) :|: TRUE f89_in(x33:0) -> f287_in(x33:0) :|: TRUE f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 f287_in(s(x17:0)) -> f284_out(s(T88:0)) :|: TRUE f248_out(x47:0) -> f248_out(s(x47:0)) :|: TRUE f248_out(x) -> f89_in(x) :|: TRUE f248_in(s(x5:0)) -> f248_in(x5:0) :|: TRUE ---------------------------------------- (125) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (126) Obligation: Rules: f284_out(x41:0) -> f284_out(s(x41:0)) :|: TRUE f284_out(x13:0) -> f89_in(x13:0) :|: TRUE f89_in(x31:0) -> f248_in(x31:0) :|: TRUE f287_in(s(T94:0)) -> f287_in(T94:0) :|: TRUE f89_in(x33:0) -> f287_in(x33:0) :|: TRUE f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 f287_in(s(x17:0)) -> f284_out(s(T88:0)) :|: TRUE f248_out(x47:0) -> f248_out(s(x47:0)) :|: TRUE f248_out(x) -> f89_in(x) :|: TRUE f248_in(s(x5:0)) -> f248_in(x5:0) :|: TRUE ---------------------------------------- (127) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f284_out(x41:0) -> f284_out(s(x41:0)) :|: TRUE (2) f284_out(x13:0) -> f89_in(x13:0) :|: TRUE (3) f89_in(x31:0) -> f248_in(x31:0) :|: TRUE (4) f287_in(s(T94:0)) -> f287_in(T94:0) :|: TRUE (5) f89_in(x33:0) -> f287_in(x33:0) :|: TRUE (6) f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 (7) f287_in(s(x17:0)) -> f284_out(s(T88:0)) :|: TRUE (8) f248_out(x47:0) -> f248_out(s(x47:0)) :|: TRUE (9) f248_out(x) -> f89_in(x) :|: TRUE (10) f248_in(s(x5:0)) -> f248_in(x5:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (3), (5) (3) -> (6), (10) (4) -> (4), (7) (5) -> (4), (7) (6) -> (8), (9) (7) -> (1), (2) (8) -> (8), (9) (9) -> (3), (5) (10) -> (6), (10) This digraph is fully evaluated! ---------------------------------------- (128) Obligation: Termination digraph: Nodes: (1) f284_out(x41:0) -> f284_out(s(x41:0)) :|: TRUE (2) f287_in(s(x17:0)) -> f284_out(s(T88:0)) :|: TRUE (3) f287_in(s(T94:0)) -> f287_in(T94:0) :|: TRUE (4) f89_in(x33:0) -> f287_in(x33:0) :|: TRUE (5) f248_out(x) -> f89_in(x) :|: TRUE (6) f248_out(x47:0) -> f248_out(s(x47:0)) :|: TRUE (7) f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 (8) f248_in(s(x5:0)) -> f248_in(x5:0) :|: TRUE (9) f89_in(x31:0) -> f248_in(x31:0) :|: TRUE (10) f284_out(x13:0) -> f89_in(x13:0) :|: TRUE Arcs: (1) -> (1), (10) (2) -> (1), (10) (3) -> (2), (3) (4) -> (2), (3) (5) -> (4), (9) (6) -> (5), (6) (7) -> (5), (6) (8) -> (7), (8) (9) -> (7), (8) (10) -> (4), (9) This digraph is fully evaluated! ---------------------------------------- (129) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (130) Obligation: Rules: f89_in(x31:0:0) -> f248_in(x31:0:0) :|: TRUE f284_out(x41:0:0) -> f284_out(s(x41:0:0)) :|: TRUE f284_out(x13:0:0) -> f89_in(x13:0:0) :|: TRUE f287_in(s(T94:0:0)) -> f287_in(T94:0:0) :|: TRUE f287_in(s(x17:0:0)) -> f284_out(s(T88:0:0)) :|: TRUE f248_out(x:0) -> f89_in(x:0) :|: TRUE f248_in(s(x5:0:0)) -> f248_in(x5:0:0) :|: TRUE f89_in(x33:0:0) -> f287_in(x33:0:0) :|: TRUE f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 f248_out(x47:0:0) -> f248_out(s(x47:0:0)) :|: TRUE ---------------------------------------- (131) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (132) Obligation: Rules: f89_in(x) -> f248_in(x) :|: TRUE f284_out(x1) -> f284_out(s(x1)) :|: TRUE f284_out(x2) -> f89_in(x2) :|: TRUE f287_in(s(x3)) -> f287_in(x3) :|: TRUE f287_in(s(x4)) -> f284_out(s(x5)) :|: TRUE f248_out(x6) -> f89_in(x6) :|: TRUE f248_in(s(x7)) -> f248_in(x7) :|: TRUE f89_in(x8) -> f287_in(x8) :|: TRUE f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 f248_out(x10) -> f248_out(s(x10)) :|: TRUE ---------------------------------------- (133) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (134) Obligation: Rules: f89_in(x:0) -> f248_in(x:0) :|: TRUE f284_out(x1:0) -> f284_out(s(x1:0)) :|: TRUE f284_out(x2:0) -> f89_in(x2:0) :|: TRUE f287_in(s(x3:0)) -> f287_in(x3:0) :|: TRUE f287_in(s(x4:0)) -> f284_out(s(x5:0)) :|: TRUE f248_out(x6:0) -> f89_in(x6:0) :|: TRUE f248_in(s(x7:0)) -> f248_in(x7:0) :|: TRUE f89_in(x8:0) -> f287_in(x8:0) :|: TRUE f248_in(cons_0) -> f248_out(0) :|: TRUE && cons_0 = 0 f248_out(x10:0) -> f248_out(s(x10:0)) :|: TRUE ---------------------------------------- (135) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 15, "program": { "directives": [], "clauses": [ [ "(in X (tree X X1 X2))", null ], [ "(in X (tree Y Left X3))", "(',' (less X Y) (in X Left))" ], [ "(in X (tree Y X4 Right))", "(',' (less Y X) (in X Right))" ], [ "(less (0) (s X5))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "type": "Nodes", "350": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (less T151 T155) (in T151 T156))" }, { "clause": 2, "scope": 1, "term": "(in T151 T2)" } ], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "230": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(in T6 T2)" }, { "clause": 2, "scope": 1, "term": "(in T6 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "351": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [[ "(in T1 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "231": { "goal": [ { "clause": 1, "scope": 1, "term": "(in T1 T2)" }, { "clause": 2, "scope": 1, "term": "(in T1 T2)" } ], "kb": { "nonunifying": [[ "(in T1 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "352": { "goal": [ { "clause": 3, "scope": 6, "term": "(',' (less T151 T155) (in T151 T156))" }, { "clause": 4, "scope": 6, "term": "(',' (less T151 T155) (in T151 T156))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": 2, "scope": 1, "term": "(in T151 T2)" } ], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "232": { "goal": [ { "clause": 1, "scope": 1, "term": "(in T6 T2)" }, { "clause": 2, "scope": 1, "term": "(in T6 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": 3, "scope": 6, "term": "(',' (less T151 T155) (in T151 T156))" }], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "233": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (less T13 T17) (in T13 T18))" }, { "clause": 2, "scope": 1, "term": "(in T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "310": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (s T37) T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "354": { "goal": [ { "clause": 4, "scope": 6, "term": "(',' (less T151 T155) (in T151 T156))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": 2, "scope": 1, "term": "(in T151 T2)" } ], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "234": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T6 T2)" }], "kb": { "nonunifying": [[ "(in T6 T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "355": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (0) T162)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "235": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }, { "clause": 4, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(in T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "356": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [ { "clause": 3, "scope": 3, "term": "(less T37 T39)" }, { "clause": 4, "scope": 3, "term": "(less T37 T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "357": { "goal": [{ "clause": 4, "scope": 6, "term": "(',' (less T151 T155) (in T151 T156))" }], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "314": { "goal": [{ "clause": 3, "scope": 3, "term": "(less T37 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "358": { "goal": [ { "clause": -1, "scope": 6, "term": null }, { "clause": 2, "scope": 1, "term": "(in T151 T2)" } ], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "315": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T37 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "359": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T175 T177) (in (s T175) T178))" }], "kb": { "nonunifying": [[ "(in (s T175) T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T175"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "316": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "317": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "318": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T55 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "16": { "goal": [ { "clause": 0, "scope": 1, "term": "(in T1 T2)" }, { "clause": 1, "scope": 1, "term": "(in T1 T2)" }, { "clause": 2, "scope": 1, "term": "(in T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "360": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "361": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T151 T2)" }], "kb": { "nonunifying": [[ "(in T151 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T151"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "362": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T193 T189) (in T189 T194))" }], "kb": { "nonunifying": [[ "(in T189 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T189"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "363": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "320": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "364": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T205 T201) (in T201 T206))" }], "kb": { "nonunifying": [[ "(in T201 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T201"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "244": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "321": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T13 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "365": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "245": { "goal": [ { "clause": 4, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(in T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "366": { "goal": [ { "clause": 3, "scope": 7, "term": "(',' (less T205 T201) (in T201 T206))" }, { "clause": 4, "scope": 7, "term": "(',' (less T205 T201) (in T201 T206))" } ], "kb": { "nonunifying": [[ "(in T201 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T201"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "246": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (0) T24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "367": { "goal": [{ "clause": 3, "scope": 7, "term": "(',' (less T205 T201) (in T201 T206))" }], "kb": { "nonunifying": [[ "(in T201 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T201"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "247": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "368": { "goal": [{ "clause": 4, "scope": 7, "term": "(',' (less T205 T201) (in T201 T206))" }], "kb": { "nonunifying": [[ "(in T201 T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T201"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "369": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (s T211) T212)" }], "kb": { "nonunifying": [[ "(in (s T211) T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T211"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "327": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T78 T74) (in T74 T79))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "328": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "329": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T78 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "370": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "294": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T37 T39) (in (s T37) T40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "371": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T225 T224) (in (s T224) T226))" }], "kb": { "nonunifying": [[ "(in (s T224) T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T224"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "372": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "296": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "373": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T225 T224)" }], "kb": { "nonunifying": [[ "(in (s T224) T2)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T224"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "330": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T74 T82)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "374": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (s T224) T229)" }], "kb": { "nonunifying": [[ "(in (s T224) T230)", "(in X9 (tree X9 X10 X11))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T224"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "331": { "goal": [ { "clause": 3, "scope": 4, "term": "(less T78 T74)" }, { "clause": 4, "scope": 4, "term": "(less T78 T74)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "332": { "goal": [{ "clause": 3, "scope": 4, "term": "(less T78 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "333": { "goal": [{ "clause": 4, "scope": 4, "term": "(less T78 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "334": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "336": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T96 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T95"], "free": [], "exprvars": [] } }, "338": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T113 T109) (in T109 T114))" }], "kb": { "nonunifying": [[ "(in T109 T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "340": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "341": { "goal": [ { "clause": 3, "scope": 5, "term": "(',' (less T113 T109) (in T109 T114))" }, { "clause": 4, "scope": 5, "term": "(',' (less T113 T109) (in T109 T114))" } ], "kb": { "nonunifying": [[ "(in T109 T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "265": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(in T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "342": { "goal": [{ "clause": 3, "scope": 5, "term": "(',' (less T113 T109) (in T109 T114))" }], "kb": { "nonunifying": [[ "(in T109 T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "343": { "goal": [{ "clause": 4, "scope": 5, "term": "(',' (less T113 T109) (in T109 T114))" }], "kb": { "nonunifying": [[ "(in T109 T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "344": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (s T119) T120)" }], "kb": { "nonunifying": [[ "(in (s T119) T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T119"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "345": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T133 T132) (in (s T132) T134))" }], "kb": { "nonunifying": [[ "(in (s T132) T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T132"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "347": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "348": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T133 T132)" }], "kb": { "nonunifying": [[ "(in (s T132) T2)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T132"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "349": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (s T132) T137)" }], "kb": { "nonunifying": [[ "(in (s T132) T138)", "(in X16 (tree X17 X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T132"], "free": [ "X16", "X17", "X18", "X19" ], "exprvars": [] } }, "309": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T37 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 15, "to": 16, "label": "CASE" }, { "from": 16, "to": 230, "label": "EVAL with clause\nin(X9, tree(X9, X10, X11)).\nand substitutionT1 -> T6,\nX9 -> T6,\nX10 -> T7,\nX11 -> T8,\nT2 -> tree(T6, T7, T8)" }, { "from": 16, "to": 231, "label": "EVAL-BACKTRACK" }, { "from": 230, "to": 232, "label": "SUCCESS" }, { "from": 231, "to": 350, "label": "EVAL with clause\nin(X138, tree(X139, X140, X141)) :- ','(less(X138, X139), in(X138, X140)).\nand substitutionT1 -> T151,\nX138 -> T151,\nX139 -> T155,\nX140 -> T156,\nX141 -> T154,\nT2 -> tree(T155, T156, T154),\nT152 -> T155,\nT153 -> T156" }, { "from": 231, "to": 351, "label": "EVAL-BACKTRACK" }, { "from": 232, "to": 233, "label": "EVAL with clause\nin(X16, tree(X17, X18, X19)) :- ','(less(X16, X17), in(X16, X18)).\nand substitutionT6 -> T13,\nX16 -> T13,\nX17 -> T17,\nX18 -> T18,\nX19 -> T16,\nT2 -> tree(T17, T18, T16),\nT14 -> T17,\nT15 -> T18" }, { "from": 232, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 233, "to": 235, "label": "CASE" }, { "from": 234, "to": 339, "label": "EVAL with clause\nin(X103, tree(X104, X105, X106)) :- ','(less(X104, X103), in(X103, X106)).\nand substitutionT6 -> T109,\nX103 -> T109,\nX104 -> T113,\nX105 -> T111,\nX106 -> T114,\nT2 -> tree(T113, T111, T114),\nT110 -> T113,\nT112 -> T114" }, { "from": 234, "to": 340, "label": "EVAL-BACKTRACK" }, { "from": 235, "to": 244, "label": "PARALLEL" }, { "from": 235, "to": 245, "label": "PARALLEL" }, { "from": 244, "to": 246, "label": "EVAL with clause\nless(0, s(X24)).\nand substitutionT13 -> 0,\nX24 -> T23,\nT17 -> s(T23),\nT18 -> T24" }, { "from": 244, "to": 247, "label": "EVAL-BACKTRACK" }, { "from": 245, "to": 264, "label": "PARALLEL" }, { "from": 245, "to": 265, "label": "PARALLEL" }, { "from": 246, "to": 15, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T24" }, { "from": 264, "to": 294, "label": "EVAL with clause\nless(s(X39), s(X40)) :- less(X39, X40).\nand substitutionX39 -> T37,\nT13 -> s(T37),\nX40 -> T39,\nT17 -> s(T39),\nT38 -> T39,\nT18 -> T40" }, { "from": 264, "to": 296, "label": "EVAL-BACKTRACK" }, { "from": 265, "to": 321, "label": "FAILURE" }, { "from": 294, "to": 309, "label": "SPLIT 1" }, { "from": 294, "to": 310, "label": "SPLIT 2\nnew knowledge:\nT37 is ground\nreplacements:T40 -> T43" }, { "from": 309, "to": 313, "label": "CASE" }, { "from": 310, "to": 15, "label": "INSTANCE with matching:\nT1 -> s(T37)\nT2 -> T43" }, { "from": 313, "to": 314, "label": "PARALLEL" }, { "from": 313, "to": 315, "label": "PARALLEL" }, { "from": 314, "to": 316, "label": "EVAL with clause\nless(0, s(X49)).\nand substitutionT37 -> 0,\nX49 -> T50,\nT39 -> s(T50)" }, { "from": 314, "to": 317, "label": "EVAL-BACKTRACK" }, { "from": 315, "to": 319, "label": "EVAL with clause\nless(s(X54), s(X55)) :- less(X54, X55).\nand substitutionX54 -> T55,\nT37 -> s(T55),\nX55 -> T57,\nT39 -> s(T57),\nT56 -> T57" }, { "from": 315, "to": 320, "label": "EVAL-BACKTRACK" }, { "from": 316, "to": 318, "label": "SUCCESS" }, { "from": 319, "to": 309, "label": "INSTANCE with matching:\nT37 -> T55\nT39 -> T57" }, { "from": 321, "to": 327, "label": "EVAL with clause\nin(X72, tree(X73, X74, X75)) :- ','(less(X73, X72), in(X72, X75)).\nand substitutionT13 -> T74,\nX72 -> T74,\nX73 -> T78,\nX74 -> T76,\nX75 -> T79,\nT2 -> tree(T78, T76, T79),\nT75 -> T78,\nT77 -> T79" }, { "from": 321, "to": 328, "label": "EVAL-BACKTRACK" }, { "from": 327, "to": 329, "label": "SPLIT 1" }, { "from": 327, "to": 330, "label": "SPLIT 2\nnew knowledge:\nT78 is ground\nT74 is ground\nreplacements:T79 -> T82" }, { "from": 329, "to": 331, "label": "CASE" }, { "from": 330, "to": 15, "label": "INSTANCE with matching:\nT1 -> T74\nT2 -> T82" }, { "from": 331, "to": 332, "label": "PARALLEL" }, { "from": 331, "to": 333, "label": "PARALLEL" }, { "from": 332, "to": 334, "label": "EVAL with clause\nless(0, s(X84)).\nand substitutionT78 -> 0,\nX84 -> T89,\nT74 -> s(T89)" }, { "from": 332, "to": 335, "label": "EVAL-BACKTRACK" }, { "from": 333, "to": 337, "label": "EVAL with clause\nless(s(X89), s(X90)) :- less(X89, X90).\nand substitutionX89 -> T96,\nT78 -> s(T96),\nX90 -> T95,\nT74 -> s(T95),\nT94 -> T96" }, { "from": 333, "to": 338, "label": "EVAL-BACKTRACK" }, { "from": 334, "to": 336, "label": "SUCCESS" }, { "from": 337, "to": 329, "label": "INSTANCE with matching:\nT78 -> T96\nT74 -> T95" }, { "from": 339, "to": 341, "label": "CASE" }, { "from": 341, "to": 342, "label": "PARALLEL" }, { "from": 341, "to": 343, "label": "PARALLEL" }, { "from": 342, "to": 344, "label": "EVAL with clause\nless(0, s(X111)).\nand substitutionT113 -> 0,\nX111 -> T119,\nT109 -> s(T119),\nT114 -> T120" }, { "from": 342, "to": 345, "label": "EVAL-BACKTRACK" }, { "from": 343, "to": 346, "label": "EVAL with clause\nless(s(X122), s(X123)) :- less(X122, X123).\nand substitutionX122 -> T133,\nT113 -> s(T133),\nX123 -> T132,\nT109 -> s(T132),\nT131 -> T133,\nT114 -> T134" }, { "from": 343, "to": 347, "label": "EVAL-BACKTRACK" }, { "from": 344, "to": 15, "label": "INSTANCE with matching:\nT1 -> s(T119)\nT2 -> T120" }, { "from": 346, "to": 348, "label": "SPLIT 1" }, { "from": 346, "to": 349, "label": "SPLIT 2\nnew knowledge:\nT133 is ground\nT132 is ground\nreplacements:T134 -> T137,\nT2 -> T138" }, { "from": 348, "to": 329, "label": "INSTANCE with matching:\nT78 -> T133\nT74 -> T132" }, { "from": 349, "to": 15, "label": "INSTANCE with matching:\nT1 -> s(T132)\nT2 -> T137" }, { "from": 350, "to": 352, "label": "CASE" }, { "from": 351, "to": 364, "label": "EVAL with clause\nin(X183, tree(X184, X185, X186)) :- ','(less(X184, X183), in(X183, X186)).\nand substitutionT1 -> T201,\nX183 -> T201,\nX184 -> T205,\nX185 -> T203,\nX186 -> T206,\nT2 -> tree(T205, T203, T206),\nT202 -> T205,\nT204 -> T206" }, { "from": 351, "to": 365, "label": "EVAL-BACKTRACK" }, { "from": 352, "to": 353, "label": "PARALLEL" }, { "from": 352, "to": 354, "label": "PARALLEL" }, { "from": 353, "to": 355, "label": "EVAL with clause\nless(0, s(X146)).\nand substitutionT151 -> 0,\nX146 -> T161,\nT155 -> s(T161),\nT156 -> T162" }, { "from": 353, "to": 356, "label": "EVAL-BACKTRACK" }, { "from": 354, "to": 357, "label": "PARALLEL" }, { "from": 354, "to": 358, "label": "PARALLEL" }, { "from": 355, "to": 15, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T162" }, { "from": 357, "to": 359, "label": "EVAL with clause\nless(s(X161), s(X162)) :- less(X161, X162).\nand substitutionX161 -> T175,\nT151 -> s(T175),\nX162 -> T177,\nT155 -> s(T177),\nT176 -> T177,\nT156 -> T178" }, { "from": 357, "to": 360, "label": "EVAL-BACKTRACK" }, { "from": 358, "to": 361, "label": "FAILURE" }, { "from": 359, "to": 294, "label": "INSTANCE with matching:\nT37 -> T175\nT39 -> T177\nT40 -> T178" }, { "from": 361, "to": 362, "label": "EVAL with clause\nin(X173, tree(X174, X175, X176)) :- ','(less(X174, X173), in(X173, X176)).\nand substitutionT151 -> T189,\nX173 -> T189,\nX174 -> T193,\nX175 -> T191,\nX176 -> T194,\nT2 -> tree(T193, T191, T194),\nT190 -> T193,\nT192 -> T194" }, { "from": 361, "to": 363, "label": "EVAL-BACKTRACK" }, { "from": 362, "to": 327, "label": "INSTANCE with matching:\nT78 -> T193\nT74 -> T189\nT79 -> T194" }, { "from": 364, "to": 366, "label": "CASE" }, { "from": 366, "to": 367, "label": "PARALLEL" }, { "from": 366, "to": 368, "label": "PARALLEL" }, { "from": 367, "to": 369, "label": "EVAL with clause\nless(0, s(X191)).\nand substitutionT205 -> 0,\nX191 -> T211,\nT201 -> s(T211),\nT206 -> T212" }, { "from": 367, "to": 370, "label": "EVAL-BACKTRACK" }, { "from": 368, "to": 371, "label": "EVAL with clause\nless(s(X202), s(X203)) :- less(X202, X203).\nand substitutionX202 -> T225,\nT205 -> s(T225),\nX203 -> T224,\nT201 -> s(T224),\nT223 -> T225,\nT206 -> T226" }, { "from": 368, "to": 372, "label": "EVAL-BACKTRACK" }, { "from": 369, "to": 15, "label": "INSTANCE with matching:\nT1 -> s(T211)\nT2 -> T212" }, { "from": 371, "to": 373, "label": "SPLIT 1" }, { "from": 371, "to": 374, "label": "SPLIT 2\nnew knowledge:\nT225 is ground\nT224 is ground\nreplacements:T226 -> T229,\nT2 -> T230" }, { "from": 373, "to": 329, "label": "INSTANCE with matching:\nT78 -> T225\nT74 -> T224" }, { "from": 374, "to": 15, "label": "INSTANCE with matching:\nT1 -> s(T224)\nT2 -> T229" } ], "type": "Graph" } } ---------------------------------------- (136) Obligation: Triples: lessE(s(X1), s(X2)) :- lessE(X1, X2). lessD(s(X1), s(X2)) :- lessD(X1, X2). pB(X1, X2, X3) :- lessE(X1, X2). pB(X1, X2, X3) :- ','(lesscE(X1, X2), inA(s(X1), X3)). pC(X1, X2, X3) :- lessD(X1, X2). pC(X1, X2, X3) :- ','(lesscD(X1, X2), inA(X2, X3)). inA(0, tree(s(X1), X2, X3)) :- inA(0, X2). inA(s(X1), tree(s(X2), X3, X4)) :- pB(X1, X2, X3). inA(X1, tree(X2, X3, X4)) :- pC(X2, X1, X4). inA(s(X1), tree(0, X2, X3)) :- inA(s(X1), X3). inA(s(X1), tree(s(X2), X3, X4)) :- lessD(X2, X1). inA(s(X1), tree(s(X2), X3, X4)) :- ','(lesscD(X2, X1), inA(s(X1), X4)). inA(0, tree(s(X1), X2, X3)) :- inA(0, X2). inA(s(X1), tree(s(X2), X3, X4)) :- pB(X1, X2, X3). inA(X1, tree(X2, X3, X4)) :- pC(X2, X1, X4). inA(s(X1), tree(0, X2, X3)) :- inA(s(X1), X3). inA(s(X1), tree(s(X2), X3, X4)) :- lessD(X2, X1). inA(s(X1), tree(s(X2), X3, X4)) :- ','(lesscD(X2, X1), inA(s(X1), X4)). Clauses: incA(X1, tree(X1, X2, X3)). incA(0, tree(s(X1), X2, X3)) :- incA(0, X2). incA(s(X1), tree(s(X2), X3, X4)) :- qcB(X1, X2, X3). incA(X1, tree(X2, X3, X4)) :- qcC(X2, X1, X4). incA(s(X1), tree(0, X2, X3)) :- incA(s(X1), X3). incA(s(X1), tree(s(X2), X3, X4)) :- ','(lesscD(X2, X1), incA(s(X1), X4)). incA(0, tree(s(X1), X2, X3)) :- incA(0, X2). incA(s(X1), tree(s(X2), X3, X4)) :- qcB(X1, X2, X3). incA(X1, tree(X2, X3, X4)) :- qcC(X2, X1, X4). incA(s(X1), tree(0, X2, X3)) :- incA(s(X1), X3). incA(s(X1), tree(s(X2), X3, X4)) :- ','(lesscD(X2, X1), incA(s(X1), X4)). lesscE(0, s(X1)). lesscE(s(X1), s(X2)) :- lesscE(X1, X2). lesscD(0, s(X1)). lesscD(s(X1), s(X2)) :- lesscD(X1, X2). qcB(X1, X2, X3) :- ','(lesscE(X1, X2), incA(s(X1), X3)). qcC(X1, X2, X3) :- ','(lesscD(X1, X2), incA(X2, X3)). Afs: inA(x1, x2) = inA(x1) ---------------------------------------- (137) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: inA_in_2: (b,f) pB_in_3: (b,f,f) lessE_in_2: (b,f) lesscE_in_2: (b,f) pC_in_3: (f,b,f) lessD_in_2: (f,b) lesscD_in_2: (f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: INA_IN_GA(0, tree(s(X1), X2, X3)) -> U9_GA(X1, X2, X3, inA_in_ga(0, X2)) INA_IN_GA(0, tree(s(X1), X2, X3)) -> INA_IN_GA(0, X2) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U10_GA(X1, X2, X3, X4, pB_in_gaa(X1, X2, X3)) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> PB_IN_GAA(X1, X2, X3) PB_IN_GAA(X1, X2, X3) -> U3_GAA(X1, X2, X3, lessE_in_ga(X1, X2)) PB_IN_GAA(X1, X2, X3) -> LESSE_IN_GA(X1, X2) LESSE_IN_GA(s(X1), s(X2)) -> U1_GA(X1, X2, lessE_in_ga(X1, X2)) LESSE_IN_GA(s(X1), s(X2)) -> LESSE_IN_GA(X1, X2) PB_IN_GAA(X1, X2, X3) -> U4_GAA(X1, X2, X3, lesscE_in_ga(X1, X2)) U4_GAA(X1, X2, X3, lesscE_out_ga(X1, X2)) -> U5_GAA(X1, X2, X3, inA_in_ga(s(X1), X3)) U4_GAA(X1, X2, X3, lesscE_out_ga(X1, X2)) -> INA_IN_GA(s(X1), X3) INA_IN_GA(X1, tree(X2, X3, X4)) -> U11_GA(X1, X2, X3, X4, pC_in_aga(X2, X1, X4)) INA_IN_GA(X1, tree(X2, X3, X4)) -> PC_IN_AGA(X2, X1, X4) PC_IN_AGA(X1, X2, X3) -> U6_AGA(X1, X2, X3, lessD_in_ag(X1, X2)) PC_IN_AGA(X1, X2, X3) -> LESSD_IN_AG(X1, X2) LESSD_IN_AG(s(X1), s(X2)) -> U2_AG(X1, X2, lessD_in_ag(X1, X2)) LESSD_IN_AG(s(X1), s(X2)) -> LESSD_IN_AG(X1, X2) PC_IN_AGA(X1, X2, X3) -> U7_AGA(X1, X2, X3, lesscD_in_ag(X1, X2)) U7_AGA(X1, X2, X3, lesscD_out_ag(X1, X2)) -> U8_AGA(X1, X2, X3, inA_in_ga(X2, X3)) U7_AGA(X1, X2, X3, lesscD_out_ag(X1, X2)) -> INA_IN_GA(X2, X3) INA_IN_GA(s(X1), tree(0, X2, X3)) -> U12_GA(X1, X2, X3, inA_in_ga(s(X1), X3)) INA_IN_GA(s(X1), tree(0, X2, X3)) -> INA_IN_GA(s(X1), X3) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U13_GA(X1, X2, X3, X4, lessD_in_ag(X2, X1)) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> LESSD_IN_AG(X2, X1) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U14_GA(X1, X2, X3, X4, lesscD_in_ag(X2, X1)) U14_GA(X1, X2, X3, X4, lesscD_out_ag(X2, X1)) -> U15_GA(X1, X2, X3, X4, inA_in_ga(s(X1), X4)) U14_GA(X1, X2, X3, X4, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1), X4) The TRS R consists of the following rules: lesscE_in_ga(0, s(X1)) -> lesscE_out_ga(0, s(X1)) lesscE_in_ga(s(X1), s(X2)) -> U23_ga(X1, X2, lesscE_in_ga(X1, X2)) U23_ga(X1, X2, lesscE_out_ga(X1, X2)) -> lesscE_out_ga(s(X1), s(X2)) lesscD_in_ag(0, s(X1)) -> lesscD_out_ag(0, s(X1)) lesscD_in_ag(s(X1), s(X2)) -> U24_ag(X1, X2, lesscD_in_ag(X1, X2)) U24_ag(X1, X2, lesscD_out_ag(X1, X2)) -> lesscD_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: inA_in_ga(x1, x2) = inA_in_ga(x1) 0 = 0 s(x1) = s(x1) pB_in_gaa(x1, x2, x3) = pB_in_gaa(x1) lessE_in_ga(x1, x2) = lessE_in_ga(x1) lesscE_in_ga(x1, x2) = lesscE_in_ga(x1) lesscE_out_ga(x1, x2) = lesscE_out_ga(x1) U23_ga(x1, x2, x3) = U23_ga(x1, x3) pC_in_aga(x1, x2, x3) = pC_in_aga(x2) lessD_in_ag(x1, x2) = lessD_in_ag(x2) lesscD_in_ag(x1, x2) = lesscD_in_ag(x2) lesscD_out_ag(x1, x2) = lesscD_out_ag(x1, x2) U24_ag(x1, x2, x3) = U24_ag(x2, x3) INA_IN_GA(x1, x2) = INA_IN_GA(x1) U9_GA(x1, x2, x3, x4) = U9_GA(x4) U10_GA(x1, x2, x3, x4, x5) = U10_GA(x1, x5) PB_IN_GAA(x1, x2, x3) = PB_IN_GAA(x1) U3_GAA(x1, x2, x3, x4) = U3_GAA(x1, x4) LESSE_IN_GA(x1, x2) = LESSE_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) U5_GAA(x1, x2, x3, x4) = U5_GAA(x1, x4) U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x5) PC_IN_AGA(x1, x2, x3) = PC_IN_AGA(x2) U6_AGA(x1, x2, x3, x4) = U6_AGA(x2, x4) LESSD_IN_AG(x1, x2) = LESSD_IN_AG(x2) U2_AG(x1, x2, x3) = U2_AG(x2, x3) U7_AGA(x1, x2, x3, x4) = U7_AGA(x2, x4) U8_AGA(x1, x2, x3, x4) = U8_AGA(x1, x2, x4) U12_GA(x1, x2, x3, x4) = U12_GA(x1, x4) U13_GA(x1, x2, x3, x4, x5) = U13_GA(x1, x5) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x5) U15_GA(x1, x2, x3, x4, x5) = U15_GA(x1, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (138) Obligation: Pi DP problem: The TRS P consists of the following rules: INA_IN_GA(0, tree(s(X1), X2, X3)) -> U9_GA(X1, X2, X3, inA_in_ga(0, X2)) INA_IN_GA(0, tree(s(X1), X2, X3)) -> INA_IN_GA(0, X2) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U10_GA(X1, X2, X3, X4, pB_in_gaa(X1, X2, X3)) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> PB_IN_GAA(X1, X2, X3) PB_IN_GAA(X1, X2, X3) -> U3_GAA(X1, X2, X3, lessE_in_ga(X1, X2)) PB_IN_GAA(X1, X2, X3) -> LESSE_IN_GA(X1, X2) LESSE_IN_GA(s(X1), s(X2)) -> U1_GA(X1, X2, lessE_in_ga(X1, X2)) LESSE_IN_GA(s(X1), s(X2)) -> LESSE_IN_GA(X1, X2) PB_IN_GAA(X1, X2, X3) -> U4_GAA(X1, X2, X3, lesscE_in_ga(X1, X2)) U4_GAA(X1, X2, X3, lesscE_out_ga(X1, X2)) -> U5_GAA(X1, X2, X3, inA_in_ga(s(X1), X3)) U4_GAA(X1, X2, X3, lesscE_out_ga(X1, X2)) -> INA_IN_GA(s(X1), X3) INA_IN_GA(X1, tree(X2, X3, X4)) -> U11_GA(X1, X2, X3, X4, pC_in_aga(X2, X1, X4)) INA_IN_GA(X1, tree(X2, X3, X4)) -> PC_IN_AGA(X2, X1, X4) PC_IN_AGA(X1, X2, X3) -> U6_AGA(X1, X2, X3, lessD_in_ag(X1, X2)) PC_IN_AGA(X1, X2, X3) -> LESSD_IN_AG(X1, X2) LESSD_IN_AG(s(X1), s(X2)) -> U2_AG(X1, X2, lessD_in_ag(X1, X2)) LESSD_IN_AG(s(X1), s(X2)) -> LESSD_IN_AG(X1, X2) PC_IN_AGA(X1, X2, X3) -> U7_AGA(X1, X2, X3, lesscD_in_ag(X1, X2)) U7_AGA(X1, X2, X3, lesscD_out_ag(X1, X2)) -> U8_AGA(X1, X2, X3, inA_in_ga(X2, X3)) U7_AGA(X1, X2, X3, lesscD_out_ag(X1, X2)) -> INA_IN_GA(X2, X3) INA_IN_GA(s(X1), tree(0, X2, X3)) -> U12_GA(X1, X2, X3, inA_in_ga(s(X1), X3)) INA_IN_GA(s(X1), tree(0, X2, X3)) -> INA_IN_GA(s(X1), X3) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U13_GA(X1, X2, X3, X4, lessD_in_ag(X2, X1)) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> LESSD_IN_AG(X2, X1) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U14_GA(X1, X2, X3, X4, lesscD_in_ag(X2, X1)) U14_GA(X1, X2, X3, X4, lesscD_out_ag(X2, X1)) -> U15_GA(X1, X2, X3, X4, inA_in_ga(s(X1), X4)) U14_GA(X1, X2, X3, X4, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1), X4) The TRS R consists of the following rules: lesscE_in_ga(0, s(X1)) -> lesscE_out_ga(0, s(X1)) lesscE_in_ga(s(X1), s(X2)) -> U23_ga(X1, X2, lesscE_in_ga(X1, X2)) U23_ga(X1, X2, lesscE_out_ga(X1, X2)) -> lesscE_out_ga(s(X1), s(X2)) lesscD_in_ag(0, s(X1)) -> lesscD_out_ag(0, s(X1)) lesscD_in_ag(s(X1), s(X2)) -> U24_ag(X1, X2, lesscD_in_ag(X1, X2)) U24_ag(X1, X2, lesscD_out_ag(X1, X2)) -> lesscD_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: inA_in_ga(x1, x2) = inA_in_ga(x1) 0 = 0 s(x1) = s(x1) pB_in_gaa(x1, x2, x3) = pB_in_gaa(x1) lessE_in_ga(x1, x2) = lessE_in_ga(x1) lesscE_in_ga(x1, x2) = lesscE_in_ga(x1) lesscE_out_ga(x1, x2) = lesscE_out_ga(x1) U23_ga(x1, x2, x3) = U23_ga(x1, x3) pC_in_aga(x1, x2, x3) = pC_in_aga(x2) lessD_in_ag(x1, x2) = lessD_in_ag(x2) lesscD_in_ag(x1, x2) = lesscD_in_ag(x2) lesscD_out_ag(x1, x2) = lesscD_out_ag(x1, x2) U24_ag(x1, x2, x3) = U24_ag(x2, x3) INA_IN_GA(x1, x2) = INA_IN_GA(x1) U9_GA(x1, x2, x3, x4) = U9_GA(x4) U10_GA(x1, x2, x3, x4, x5) = U10_GA(x1, x5) PB_IN_GAA(x1, x2, x3) = PB_IN_GAA(x1) U3_GAA(x1, x2, x3, x4) = U3_GAA(x1, x4) LESSE_IN_GA(x1, x2) = LESSE_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) U5_GAA(x1, x2, x3, x4) = U5_GAA(x1, x4) U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x5) PC_IN_AGA(x1, x2, x3) = PC_IN_AGA(x2) U6_AGA(x1, x2, x3, x4) = U6_AGA(x2, x4) LESSD_IN_AG(x1, x2) = LESSD_IN_AG(x2) U2_AG(x1, x2, x3) = U2_AG(x2, x3) U7_AGA(x1, x2, x3, x4) = U7_AGA(x2, x4) U8_AGA(x1, x2, x3, x4) = U8_AGA(x1, x2, x4) U12_GA(x1, x2, x3, x4) = U12_GA(x1, x4) U13_GA(x1, x2, x3, x4, x5) = U13_GA(x1, x5) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x5) U15_GA(x1, x2, x3, x4, x5) = U15_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (139) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 15 less nodes. ---------------------------------------- (140) Complex Obligation (AND) ---------------------------------------- (141) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSD_IN_AG(s(X1), s(X2)) -> LESSD_IN_AG(X1, X2) The TRS R consists of the following rules: lesscE_in_ga(0, s(X1)) -> lesscE_out_ga(0, s(X1)) lesscE_in_ga(s(X1), s(X2)) -> U23_ga(X1, X2, lesscE_in_ga(X1, X2)) U23_ga(X1, X2, lesscE_out_ga(X1, X2)) -> lesscE_out_ga(s(X1), s(X2)) lesscD_in_ag(0, s(X1)) -> lesscD_out_ag(0, s(X1)) lesscD_in_ag(s(X1), s(X2)) -> U24_ag(X1, X2, lesscD_in_ag(X1, X2)) U24_ag(X1, X2, lesscD_out_ag(X1, X2)) -> lesscD_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: 0 = 0 s(x1) = s(x1) lesscE_in_ga(x1, x2) = lesscE_in_ga(x1) lesscE_out_ga(x1, x2) = lesscE_out_ga(x1) U23_ga(x1, x2, x3) = U23_ga(x1, x3) lesscD_in_ag(x1, x2) = lesscD_in_ag(x2) lesscD_out_ag(x1, x2) = lesscD_out_ag(x1, x2) U24_ag(x1, x2, x3) = U24_ag(x2, x3) LESSD_IN_AG(x1, x2) = LESSD_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (142) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (143) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSD_IN_AG(s(X1), s(X2)) -> LESSD_IN_AG(X1, X2) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESSD_IN_AG(x1, x2) = LESSD_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (144) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (145) Obligation: Q DP problem: The TRS P consists of the following rules: LESSD_IN_AG(s(X2)) -> LESSD_IN_AG(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (146) 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: *LESSD_IN_AG(s(X2)) -> LESSD_IN_AG(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (147) YES ---------------------------------------- (148) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSE_IN_GA(s(X1), s(X2)) -> LESSE_IN_GA(X1, X2) The TRS R consists of the following rules: lesscE_in_ga(0, s(X1)) -> lesscE_out_ga(0, s(X1)) lesscE_in_ga(s(X1), s(X2)) -> U23_ga(X1, X2, lesscE_in_ga(X1, X2)) U23_ga(X1, X2, lesscE_out_ga(X1, X2)) -> lesscE_out_ga(s(X1), s(X2)) lesscD_in_ag(0, s(X1)) -> lesscD_out_ag(0, s(X1)) lesscD_in_ag(s(X1), s(X2)) -> U24_ag(X1, X2, lesscD_in_ag(X1, X2)) U24_ag(X1, X2, lesscD_out_ag(X1, X2)) -> lesscD_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: 0 = 0 s(x1) = s(x1) lesscE_in_ga(x1, x2) = lesscE_in_ga(x1) lesscE_out_ga(x1, x2) = lesscE_out_ga(x1) U23_ga(x1, x2, x3) = U23_ga(x1, x3) lesscD_in_ag(x1, x2) = lesscD_in_ag(x2) lesscD_out_ag(x1, x2) = lesscD_out_ag(x1, x2) U24_ag(x1, x2, x3) = U24_ag(x2, x3) LESSE_IN_GA(x1, x2) = LESSE_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (149) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (150) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSE_IN_GA(s(X1), s(X2)) -> LESSE_IN_GA(X1, X2) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LESSE_IN_GA(x1, x2) = LESSE_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (151) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (152) Obligation: Q DP problem: The TRS P consists of the following rules: LESSE_IN_GA(s(X1)) -> LESSE_IN_GA(X1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (153) 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: *LESSE_IN_GA(s(X1)) -> LESSE_IN_GA(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (154) YES ---------------------------------------- (155) Obligation: Pi DP problem: The TRS P consists of the following rules: INA_IN_GA(X1, tree(X2, X3, X4)) -> PC_IN_AGA(X2, X1, X4) PC_IN_AGA(X1, X2, X3) -> U7_AGA(X1, X2, X3, lesscD_in_ag(X1, X2)) U7_AGA(X1, X2, X3, lesscD_out_ag(X1, X2)) -> INA_IN_GA(X2, X3) INA_IN_GA(0, tree(s(X1), X2, X3)) -> INA_IN_GA(0, X2) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> PB_IN_GAA(X1, X2, X3) PB_IN_GAA(X1, X2, X3) -> U4_GAA(X1, X2, X3, lesscE_in_ga(X1, X2)) U4_GAA(X1, X2, X3, lesscE_out_ga(X1, X2)) -> INA_IN_GA(s(X1), X3) INA_IN_GA(s(X1), tree(0, X2, X3)) -> INA_IN_GA(s(X1), X3) INA_IN_GA(s(X1), tree(s(X2), X3, X4)) -> U14_GA(X1, X2, X3, X4, lesscD_in_ag(X2, X1)) U14_GA(X1, X2, X3, X4, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1), X4) The TRS R consists of the following rules: lesscE_in_ga(0, s(X1)) -> lesscE_out_ga(0, s(X1)) lesscE_in_ga(s(X1), s(X2)) -> U23_ga(X1, X2, lesscE_in_ga(X1, X2)) U23_ga(X1, X2, lesscE_out_ga(X1, X2)) -> lesscE_out_ga(s(X1), s(X2)) lesscD_in_ag(0, s(X1)) -> lesscD_out_ag(0, s(X1)) lesscD_in_ag(s(X1), s(X2)) -> U24_ag(X1, X2, lesscD_in_ag(X1, X2)) U24_ag(X1, X2, lesscD_out_ag(X1, X2)) -> lesscD_out_ag(s(X1), s(X2)) The argument filtering Pi contains the following mapping: 0 = 0 s(x1) = s(x1) lesscE_in_ga(x1, x2) = lesscE_in_ga(x1) lesscE_out_ga(x1, x2) = lesscE_out_ga(x1) U23_ga(x1, x2, x3) = U23_ga(x1, x3) lesscD_in_ag(x1, x2) = lesscD_in_ag(x2) lesscD_out_ag(x1, x2) = lesscD_out_ag(x1, x2) U24_ag(x1, x2, x3) = U24_ag(x2, x3) INA_IN_GA(x1, x2) = INA_IN_GA(x1) PB_IN_GAA(x1, x2, x3) = PB_IN_GAA(x1) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) PC_IN_AGA(x1, x2, x3) = PC_IN_AGA(x2) U7_AGA(x1, x2, x3, x4) = U7_AGA(x2, x4) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (156) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (157) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(X1) -> PC_IN_AGA(X1) PC_IN_AGA(X2) -> U7_AGA(X2, lesscD_in_ag(X2)) U7_AGA(X2, lesscD_out_ag(X1, X2)) -> INA_IN_GA(X2) INA_IN_GA(0) -> INA_IN_GA(0) INA_IN_GA(s(X1)) -> PB_IN_GAA(X1) PB_IN_GAA(X1) -> U4_GAA(X1, lesscE_in_ga(X1)) U4_GAA(X1, lesscE_out_ga(X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(X1)) -> U14_GA(X1, lesscD_in_ag(X1)) U14_GA(X1, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1)) The TRS R consists of the following rules: lesscE_in_ga(0) -> lesscE_out_ga(0) lesscE_in_ga(s(X1)) -> U23_ga(X1, lesscE_in_ga(X1)) U23_ga(X1, lesscE_out_ga(X1)) -> lesscE_out_ga(s(X1)) lesscD_in_ag(s(X1)) -> lesscD_out_ag(0, s(X1)) lesscD_in_ag(s(X2)) -> U24_ag(X2, lesscD_in_ag(X2)) U24_ag(X2, lesscD_out_ag(X1, X2)) -> lesscD_out_ag(s(X1), s(X2)) The set Q consists of the following terms: lesscE_in_ga(x0) U23_ga(x0, x1) lesscD_in_ag(x0) U24_ag(x0, x1) We have to consider all (P,Q,R)-chains.