/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern 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, 6 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) TransformationProof [SOUND, 0 ms] (27) QDP (28) TransformationProof [SOUND, 0 ms] (29) QDP (30) PrologToTRSTransformerProof [SOUND, 0 ms] (31) QTRS (32) DependencyPairsProof [EQUIVALENT, 0 ms] (33) QDP (34) DependencyGraphProof [EQUIVALENT, 0 ms] (35) AND (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] (40) YES (41) QDP (42) UsableRulesProof [EQUIVALENT, 0 ms] (43) QDP (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] (45) YES (46) QDP (47) NonTerminationLoopProof [COMPLETE, 0 ms] (48) NO (49) PrologToPiTRSProof [SOUND, 0 ms] (50) PiTRS (51) DependencyPairsProof [EQUIVALENT, 0 ms] (52) PiDP (53) DependencyGraphProof [EQUIVALENT, 0 ms] (54) AND (55) PiDP (56) UsableRulesProof [EQUIVALENT, 0 ms] (57) PiDP (58) PiDPToQDPProof [SOUND, 0 ms] (59) QDP (60) QDPSizeChangeProof [EQUIVALENT, 0 ms] (61) YES (62) PiDP (63) UsableRulesProof [EQUIVALENT, 0 ms] (64) PiDP (65) PiDPToQDPProof [SOUND, 0 ms] (66) QDP (67) QDPSizeChangeProof [EQUIVALENT, 0 ms] (68) YES (69) PiDP (70) UsableRulesProof [EQUIVALENT, 0 ms] (71) PiDP (72) PiDPToQDPProof [SOUND, 0 ms] (73) QDP (74) TransformationProof [SOUND, 0 ms] (75) QDP (76) TransformationProof [SOUND, 0 ms] (77) QDP (78) TransformationProof [EQUIVALENT, 0 ms] (79) QDP (80) DependencyGraphProof [EQUIVALENT, 0 ms] (81) AND (82) QDP (83) UsableRulesProof [EQUIVALENT, 0 ms] (84) QDP (85) QReductionProof [EQUIVALENT, 0 ms] (86) QDP (87) NonTerminationLoopProof [COMPLETE, 0 ms] (88) NO (89) QDP (90) TransformationProof [EQUIVALENT, 0 ms] (91) QDP (92) PrologToIRSwTTransformerProof [SOUND, 36 ms] (93) AND (94) IRSwT (95) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (96) IRSwT (97) IntTRSCompressionProof [EQUIVALENT, 19 ms] (98) IRSwT (99) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (100) IRSwT (101) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (102) IRSwT (103) TempFilterProof [SOUND, 2 ms] (104) IRSwT (105) IRSwTToQDPProof [SOUND, 0 ms] (106) QDP (107) QDPSizeChangeProof [EQUIVALENT, 0 ms] (108) YES (109) IRSwT (110) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (111) IRSwT (112) IntTRSCompressionProof [EQUIVALENT, 0 ms] (113) IRSwT (114) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (115) IRSwT (116) IRSwTTerminationDigraphProof [EQUIVALENT, 1 ms] (117) IRSwT (118) TempFilterProof [SOUND, 1 ms] (119) IRSwT (120) IRSwTToQDPProof [SOUND, 0 ms] (121) QDP (122) QDPSizeChangeProof [EQUIVALENT, 0 ms] (123) YES (124) IRSwT (125) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (126) IRSwT (127) IntTRSCompressionProof [EQUIVALENT, 22 ms] (128) IRSwT (129) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (130) IRSwT (131) IRSwTTerminationDigraphProof [EQUIVALENT, 48 ms] (132) IRSwT (133) IntTRSCompressionProof [EQUIVALENT, 12 ms] (134) IRSwT (135) IRSwTToIntTRSProof [SOUND, 21 ms] (136) IRSwT (137) PrologToDTProblemTransformerProof [SOUND, 60 ms] (138) TRIPLES (139) TriplesToPiDPProof [SOUND, 8 ms] (140) PiDP (141) DependencyGraphProof [EQUIVALENT, 0 ms] (142) AND (143) PiDP (144) UsableRulesProof [EQUIVALENT, 0 ms] (145) PiDP (146) PiDPToQDPProof [SOUND, 0 ms] (147) QDP (148) QDPSizeChangeProof [EQUIVALENT, 0 ms] (149) YES (150) PiDP (151) UsableRulesProof [EQUIVALENT, 0 ms] (152) PiDP (153) PiDPToQDPProof [SOUND, 0 ms] (154) QDP (155) QDPSizeChangeProof [EQUIVALENT, 0 ms] (156) YES (157) PiDP (158) PiDPToQDPProof [SOUND, 0 ms] (159) QDP (160) TransformationProof [SOUND, 0 ms] (161) QDP (162) TransformationProof [SOUND, 0 ms] (163) QDP (164) TransformationProof [SOUND, 0 ms] (165) QDP (166) TransformationProof [EQUIVALENT, 0 ms] (167) QDP (168) DependencyGraphProof [EQUIVALENT, 0 ms] (169) AND (170) QDP (171) TransformationProof [EQUIVALENT, 0 ms] (172) QDP (173) TransformationProof [EQUIVALENT, 0 ms] (174) QDP (175) QDP (176) UsableRulesProof [EQUIVALENT, 0 ms] (177) QDP (178) QReductionProof [EQUIVALENT, 0 ms] (179) 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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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. ---------------------------------------- (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(0)),IN_IN_GA(0) -> U1_GA(0, less_out_ga(0))) (IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(x0, less_in_ga(x0))),IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(x0, less_in_ga(x0)))) ---------------------------------------- (27) 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) -> U3_GA(X, less_in_ag(X)) U3_GA(X, less_out_ag(Y, X)) -> IN_IN_GA(X) IN_IN_GA(0) -> U1_GA(0, less_out_ga(0)) IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(x0, less_in_ga(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(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. ---------------------------------------- (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, s(x0))),IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0, s(x0)))) (IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(x0, less_in_ag(x0))),IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(x0, less_in_ag(x0)))) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(X, less_out_ga(X)) -> IN_IN_GA(X) U3_GA(X, less_out_ag(Y, X)) -> IN_IN_GA(X) IN_IN_GA(0) -> U1_GA(0, less_out_ga(0)) IN_IN_GA(s(x0)) -> U1_GA(s(x0), U5_ga(x0, less_in_ga(x0))) IN_IN_GA(s(x0)) -> U3_GA(s(x0), less_out_ag(0, s(x0))) IN_IN_GA(s(x0)) -> U3_GA(s(x0), U5_ag(x0, less_in_ag(x0))) The TRS R consists of the following rules: less_in_ga(0) -> less_out_ga(0) less_in_ga(s(X)) -> U5_ga(X, less_in_ga(X)) less_in_ag(s(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. ---------------------------------------- (30) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 5, "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": { "270": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "272": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "273": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "110": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [{ "clause": 1, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "212": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "213": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T34 T38) (in T34 T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "258": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T77 T73) (in T73 T78))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "215": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "259": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T34 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T54 T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "219": { "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": [] } }, "13": { "goal": [{ "clause": 0, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "14": { "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": [] } }, "261": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T73 T81)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": 3, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "242": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "221": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "266": { "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": [] } }, "267": { "goal": [{ "clause": 3, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "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": [] } }, "226": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 6, "label": "CASE" }, { "from": 6, "to": 13, "label": "PARALLEL" }, { "from": 6, "to": 14, "label": "PARALLEL" }, { "from": 13, "to": 109, "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": 13, "to": 110, "label": "EVAL-BACKTRACK" }, { "from": 14, "to": 211, "label": "PARALLEL" }, { "from": 14, "to": 212, "label": "PARALLEL" }, { "from": 109, "to": 208, "label": "SUCCESS" }, { "from": 211, "to": 213, "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": 211, "to": 214, "label": "EVAL-BACKTRACK" }, { "from": 212, "to": 258, "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": 212, "to": 259, "label": "EVAL-BACKTRACK" }, { "from": 213, "to": 215, "label": "SPLIT 1" }, { "from": 213, "to": 216, "label": "SPLIT 2\nnew knowledge:\nT34 is ground\nreplacements:T39 -> T42" }, { "from": 215, "to": 219, "label": "CASE" }, { "from": 216, "to": 5, "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T42" }, { "from": 219, "to": 220, "label": "PARALLEL" }, { "from": 219, "to": 221, "label": "PARALLEL" }, { "from": 220, "to": 222, "label": "EVAL with clause\nless(0, s(X49)).\nand substitutionT34 -> 0,\nX49 -> T49,\nT38 -> s(T49)" }, { "from": 220, "to": 223, "label": "EVAL-BACKTRACK" }, { "from": 221, "to": 239, "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": 221, "to": 242, "label": "EVAL-BACKTRACK" }, { "from": 222, "to": 226, "label": "SUCCESS" }, { "from": 239, "to": 215, "label": "INSTANCE with matching:\nT34 -> T54\nT38 -> T56" }, { "from": 258, "to": 261, "label": "SPLIT 1" }, { "from": 258, "to": 263, "label": "SPLIT 2\nnew knowledge:\nT77 is ground\nT73 is ground\nreplacements:T78 -> T81" }, { "from": 261, "to": 266, "label": "CASE" }, { "from": 263, "to": 5, "label": "INSTANCE with matching:\nT1 -> T73\nT2 -> T81" }, { "from": 266, "to": 267, "label": "PARALLEL" }, { "from": 266, "to": 268, "label": "PARALLEL" }, { "from": 267, "to": 269, "label": "EVAL with clause\nless(0, s(X84)).\nand substitutionT77 -> 0,\nX84 -> T88,\nT73 -> s(T88)" }, { "from": 267, "to": 270, "label": "EVAL-BACKTRACK" }, { "from": 268, "to": 272, "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": 268, "to": 273, "label": "EVAL-BACKTRACK" }, { "from": 269, "to": 271, "label": "SUCCESS" }, { "from": 272, "to": 261, "label": "INSTANCE with matching:\nT77 -> T95\nT73 -> T94" } ], "type": "Graph" } } ---------------------------------------- (31) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in(T15) -> f5_out1 f5_in(T34) -> U1(f213_in(T34), T34) U1(f213_out1, T34) -> f5_out1 f5_in(T73) -> U2(f258_in(T73), T73) U2(f258_out1(T77), T73) -> f5_out1 f215_in(0) -> f215_out1 f215_in(s(T54)) -> U3(f215_in(T54), s(T54)) U3(f215_out1, s(T54)) -> f215_out1 f261_in(s(T88)) -> f261_out1(0) f261_in(s(T94)) -> U4(f261_in(T94), s(T94)) U4(f261_out1(T95), s(T94)) -> f261_out1(s(T95)) f213_in(T34) -> U5(f215_in(T34), T34) U5(f215_out1, T34) -> U6(f5_in(T34), T34) U6(f5_out1, T34) -> f213_out1 f258_in(T73) -> U7(f261_in(T73), T73) U7(f261_out1(T77), T73) -> U8(f5_in(T73), T73, T77) U8(f5_out1, T73, T77) -> f258_out1(T77) Q is empty. ---------------------------------------- (32) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN(T34) -> U1^1(f213_in(T34), T34) F5_IN(T34) -> F213_IN(T34) F5_IN(T73) -> U2^1(f258_in(T73), T73) F5_IN(T73) -> F258_IN(T73) F215_IN(s(T54)) -> U3^1(f215_in(T54), s(T54)) F215_IN(s(T54)) -> F215_IN(T54) F261_IN(s(T94)) -> U4^1(f261_in(T94), s(T94)) F261_IN(s(T94)) -> F261_IN(T94) F213_IN(T34) -> U5^1(f215_in(T34), T34) F213_IN(T34) -> F215_IN(T34) U5^1(f215_out1, T34) -> U6^1(f5_in(T34), T34) U5^1(f215_out1, T34) -> F5_IN(T34) F258_IN(T73) -> U7^1(f261_in(T73), T73) F258_IN(T73) -> F261_IN(T73) U7^1(f261_out1(T77), T73) -> U8^1(f5_in(T73), T73, T77) U7^1(f261_out1(T77), T73) -> F5_IN(T73) The TRS R consists of the following rules: f5_in(T15) -> f5_out1 f5_in(T34) -> U1(f213_in(T34), T34) U1(f213_out1, T34) -> f5_out1 f5_in(T73) -> U2(f258_in(T73), T73) U2(f258_out1(T77), T73) -> f5_out1 f215_in(0) -> f215_out1 f215_in(s(T54)) -> U3(f215_in(T54), s(T54)) U3(f215_out1, s(T54)) -> f215_out1 f261_in(s(T88)) -> f261_out1(0) f261_in(s(T94)) -> U4(f261_in(T94), s(T94)) U4(f261_out1(T95), s(T94)) -> f261_out1(s(T95)) f213_in(T34) -> U5(f215_in(T34), T34) U5(f215_out1, T34) -> U6(f5_in(T34), T34) U6(f5_out1, T34) -> f213_out1 f258_in(T73) -> U7(f261_in(T73), T73) U7(f261_out1(T77), T73) -> U8(f5_in(T73), T73, T77) U8(f5_out1, T73, T77) -> f258_out1(T77) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 8 less nodes. ---------------------------------------- (35) Complex Obligation (AND) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: F261_IN(s(T94)) -> F261_IN(T94) The TRS R consists of the following rules: f5_in(T15) -> f5_out1 f5_in(T34) -> U1(f213_in(T34), T34) U1(f213_out1, T34) -> f5_out1 f5_in(T73) -> U2(f258_in(T73), T73) U2(f258_out1(T77), T73) -> f5_out1 f215_in(0) -> f215_out1 f215_in(s(T54)) -> U3(f215_in(T54), s(T54)) U3(f215_out1, s(T54)) -> f215_out1 f261_in(s(T88)) -> f261_out1(0) f261_in(s(T94)) -> U4(f261_in(T94), s(T94)) U4(f261_out1(T95), s(T94)) -> f261_out1(s(T95)) f213_in(T34) -> U5(f215_in(T34), T34) U5(f215_out1, T34) -> U6(f5_in(T34), T34) U6(f5_out1, T34) -> f213_out1 f258_in(T73) -> U7(f261_in(T73), T73) U7(f261_out1(T77), T73) -> U8(f5_in(T73), T73, T77) U8(f5_out1, T73, T77) -> f258_out1(T77) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: F261_IN(s(T94)) -> F261_IN(T94) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) 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: *F261_IN(s(T94)) -> F261_IN(T94) The graph contains the following edges 1 > 1 ---------------------------------------- (40) YES ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: F215_IN(s(T54)) -> F215_IN(T54) The TRS R consists of the following rules: f5_in(T15) -> f5_out1 f5_in(T34) -> U1(f213_in(T34), T34) U1(f213_out1, T34) -> f5_out1 f5_in(T73) -> U2(f258_in(T73), T73) U2(f258_out1(T77), T73) -> f5_out1 f215_in(0) -> f215_out1 f215_in(s(T54)) -> U3(f215_in(T54), s(T54)) U3(f215_out1, s(T54)) -> f215_out1 f261_in(s(T88)) -> f261_out1(0) f261_in(s(T94)) -> U4(f261_in(T94), s(T94)) U4(f261_out1(T95), s(T94)) -> f261_out1(s(T95)) f213_in(T34) -> U5(f215_in(T34), T34) U5(f215_out1, T34) -> U6(f5_in(T34), T34) U6(f5_out1, T34) -> f213_out1 f258_in(T73) -> U7(f261_in(T73), T73) U7(f261_out1(T77), T73) -> U8(f5_in(T73), T73, T77) U8(f5_out1, T73, T77) -> f258_out1(T77) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) 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. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: F215_IN(s(T54)) -> F215_IN(T54) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F215_IN(s(T54)) -> F215_IN(T54) The graph contains the following edges 1 > 1 ---------------------------------------- (45) YES ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN(T34) -> F213_IN(T34) F213_IN(T34) -> U5^1(f215_in(T34), T34) U5^1(f215_out1, T34) -> F5_IN(T34) F5_IN(T73) -> F258_IN(T73) F258_IN(T73) -> U7^1(f261_in(T73), T73) U7^1(f261_out1(T77), T73) -> F5_IN(T73) The TRS R consists of the following rules: f5_in(T15) -> f5_out1 f5_in(T34) -> U1(f213_in(T34), T34) U1(f213_out1, T34) -> f5_out1 f5_in(T73) -> U2(f258_in(T73), T73) U2(f258_out1(T77), T73) -> f5_out1 f215_in(0) -> f215_out1 f215_in(s(T54)) -> U3(f215_in(T54), s(T54)) U3(f215_out1, s(T54)) -> f215_out1 f261_in(s(T88)) -> f261_out1(0) f261_in(s(T94)) -> U4(f261_in(T94), s(T94)) U4(f261_out1(T95), s(T94)) -> f261_out1(s(T95)) f213_in(T34) -> U5(f215_in(T34), T34) U5(f215_out1, T34) -> U6(f5_in(T34), T34) U6(f5_out1, T34) -> f213_out1 f258_in(T73) -> U7(f261_in(T73), T73) U7(f261_out1(T77), T73) -> U8(f5_in(T73), T73, T77) U8(f5_out1, T73, T77) -> f258_out1(T77) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) 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 = F213_IN(0) evaluates to t =F213_IN(0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F213_IN(0) -> U5^1(f215_in(0), 0) with rule F213_IN(T34) -> U5^1(f215_in(T34), T34) at position [] and matcher [T34 / 0] U5^1(f215_in(0), 0) -> U5^1(f215_out1, 0) with rule f215_in(0) -> f215_out1 at position [0] and matcher [ ] U5^1(f215_out1, 0) -> F5_IN(0) with rule U5^1(f215_out1, T34') -> F5_IN(T34') at position [] and matcher [T34' / 0] F5_IN(0) -> F213_IN(0) with rule F5_IN(T34) -> F213_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. ---------------------------------------- (48) NO ---------------------------------------- (49) 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 ---------------------------------------- (50) 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) ---------------------------------------- (51) 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 ---------------------------------------- (52) 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 ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (54) Complex Obligation (AND) ---------------------------------------- (55) 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 ---------------------------------------- (56) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (57) 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 ---------------------------------------- (58) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (59) 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. ---------------------------------------- (60) 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 ---------------------------------------- (61) YES ---------------------------------------- (62) 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 ---------------------------------------- (63) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (64) 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 ---------------------------------------- (65) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (66) 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. ---------------------------------------- (67) 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 ---------------------------------------- (68) YES ---------------------------------------- (69) 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 ---------------------------------------- (70) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (71) 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 ---------------------------------------- (72) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (73) 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. ---------------------------------------- (74) 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)))) ---------------------------------------- (75) 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. ---------------------------------------- (76) 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)))) ---------------------------------------- (77) 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. ---------------------------------------- (78) 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))) ---------------------------------------- (79) 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. ---------------------------------------- (80) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (81) Complex Obligation (AND) ---------------------------------------- (82) 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. ---------------------------------------- (83) 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. ---------------------------------------- (84) 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. ---------------------------------------- (85) 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) ---------------------------------------- (86) 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. ---------------------------------------- (87) 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. ---------------------------------------- (88) NO ---------------------------------------- (89) 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. ---------------------------------------- (90) 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))) ---------------------------------------- (91) 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. ---------------------------------------- (92) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 7, "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": { "191": { "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": [] } }, "type": "Nodes", "111": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "310": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "113": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "311": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "114": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "312": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "115": { "goal": [{ "clause": 1, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "313": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T95 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T94"], "free": [], "exprvars": [] } }, "116": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "314": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": 0, "scope": 1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "12": { "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": [] } }, "122": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T34 T38) (in T34 T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "123": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": 3, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T34 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "204": { "goal": [{ "clause": 4, "scope": 2, "term": "(less T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "303": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T77 T73) (in T73 T78))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "205": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "304": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "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": [] } }, "206": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "305": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "207": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "306": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T73 T81)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "307": { "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": [] } }, "209": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T54 T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "308": { "goal": [{ "clause": 3, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } }, "309": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T77 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T73"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 7, "to": 8, "label": "CASE" }, { "from": 8, "to": 11, "label": "PARALLEL" }, { "from": 8, "to": 12, "label": "PARALLEL" }, { "from": 11, "to": 111, "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": 11, "to": 113, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 115, "label": "PARALLEL" }, { "from": 12, "to": 116, "label": "PARALLEL" }, { "from": 111, "to": 114, "label": "SUCCESS" }, { "from": 115, "to": 122, "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": 115, "to": 123, "label": "EVAL-BACKTRACK" }, { "from": 116, "to": 303, "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": 116, "to": 304, "label": "EVAL-BACKTRACK" }, { "from": 122, "to": 126, "label": "SPLIT 1" }, { "from": 122, "to": 127, "label": "SPLIT 2\nnew knowledge:\nT34 is ground\nreplacements:T39 -> T42" }, { "from": 126, "to": 191, "label": "CASE" }, { "from": 127, "to": 7, "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T42" }, { "from": 191, "to": 203, "label": "PARALLEL" }, { "from": 191, "to": 204, "label": "PARALLEL" }, { "from": 203, "to": 205, "label": "EVAL with clause\nless(0, s(X49)).\nand substitutionT34 -> 0,\nX49 -> T49,\nT38 -> s(T49)" }, { "from": 203, "to": 206, "label": "EVAL-BACKTRACK" }, { "from": 204, "to": 209, "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": 204, "to": 210, "label": "EVAL-BACKTRACK" }, { "from": 205, "to": 207, "label": "SUCCESS" }, { "from": 209, "to": 126, "label": "INSTANCE with matching:\nT34 -> T54\nT38 -> T56" }, { "from": 303, "to": 305, "label": "SPLIT 1" }, { "from": 303, "to": 306, "label": "SPLIT 2\nnew knowledge:\nT77 is ground\nT73 is ground\nreplacements:T78 -> T81" }, { "from": 305, "to": 307, "label": "CASE" }, { "from": 306, "to": 7, "label": "INSTANCE with matching:\nT1 -> T73\nT2 -> T81" }, { "from": 307, "to": 308, "label": "PARALLEL" }, { "from": 307, "to": 309, "label": "PARALLEL" }, { "from": 308, "to": 310, "label": "EVAL with clause\nless(0, s(X84)).\nand substitutionT77 -> 0,\nX84 -> T88,\nT73 -> s(T88)" }, { "from": 308, "to": 311, "label": "EVAL-BACKTRACK" }, { "from": 309, "to": 313, "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": 309, "to": 314, "label": "EVAL-BACKTRACK" }, { "from": 310, "to": 312, "label": "SUCCESS" }, { "from": 313, "to": 305, "label": "INSTANCE with matching:\nT77 -> T95\nT73 -> T94" } ], "type": "Graph" } } ---------------------------------------- (93) Complex Obligation (AND) ---------------------------------------- (94) Obligation: Rules: f307_out(T73) -> f305_out(T73) :|: TRUE f305_in(x) -> f307_in(x) :|: TRUE f309_in(x1) -> f314_in :|: TRUE f309_in(s(T94)) -> f313_in(T94) :|: TRUE f313_out(x2) -> f309_out(s(x2)) :|: TRUE f314_out -> f309_out(x3) :|: TRUE f313_in(x4) -> f305_in(x4) :|: TRUE f305_out(x5) -> f313_out(x5) :|: TRUE f308_out(x6) -> f307_out(x6) :|: TRUE f309_out(x7) -> f307_out(x7) :|: TRUE f307_in(x8) -> f309_in(x8) :|: TRUE f307_in(x9) -> f308_in(x9) :|: TRUE f7_in(T1) -> f8_in(T1) :|: TRUE f8_out(x10) -> f7_out(x10) :|: TRUE f8_in(x11) -> f12_in(x11) :|: TRUE f11_out(x12) -> f8_out(x12) :|: TRUE f8_in(x13) -> f11_in(x13) :|: TRUE f12_out(x14) -> f8_out(x14) :|: TRUE f12_in(x15) -> f115_in(x15) :|: TRUE f115_out(x16) -> f12_out(x16) :|: TRUE f12_in(x17) -> f116_in(x17) :|: TRUE f116_out(x18) -> f12_out(x18) :|: TRUE f303_out(x19) -> f116_out(x19) :|: TRUE f116_in(x20) -> f304_in :|: TRUE f116_in(x21) -> f303_in(x21) :|: TRUE f304_out -> f116_out(x22) :|: TRUE f305_out(x23) -> f306_in(x23) :|: TRUE f303_in(x24) -> f305_in(x24) :|: TRUE f306_out(x25) -> f303_out(x25) :|: TRUE Start term: f7_in(T1) ---------------------------------------- (95) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f305_in(x) -> f307_in(x) :|: TRUE f309_in(s(T94)) -> f313_in(T94) :|: TRUE f313_in(x4) -> f305_in(x4) :|: TRUE f307_in(x8) -> f309_in(x8) :|: TRUE ---------------------------------------- (96) Obligation: Rules: f305_in(x) -> f307_in(x) :|: TRUE f309_in(s(T94)) -> f313_in(T94) :|: TRUE f313_in(x4) -> f305_in(x4) :|: TRUE f307_in(x8) -> f309_in(x8) :|: TRUE ---------------------------------------- (97) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (98) Obligation: Rules: f309_in(s(T94:0)) -> f309_in(T94:0) :|: TRUE ---------------------------------------- (99) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (100) Obligation: Rules: f309_in(s(T94:0)) -> f309_in(T94:0) :|: TRUE ---------------------------------------- (101) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f309_in(s(T94:0)) -> f309_in(T94:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (102) Obligation: Termination digraph: Nodes: (1) f309_in(s(T94:0)) -> f309_in(T94:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (103) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f309_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (104) Obligation: Rules: f309_in(s(T94:0)) -> f309_in(T94:0) ---------------------------------------- (105) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: f309_in(s(T94:0)) -> f309_in(T94:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (107) 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: *f309_in(s(T94:0)) -> f309_in(T94:0) The graph contains the following edges 1 > 1 ---------------------------------------- (108) YES ---------------------------------------- (109) Obligation: Rules: f126_out(T54) -> f209_out(T54) :|: TRUE f209_in(x) -> f126_in(x) :|: TRUE f191_out(T34) -> f126_out(T34) :|: TRUE f126_in(x1) -> f191_in(x1) :|: TRUE f191_in(x2) -> f203_in(x2) :|: TRUE f203_out(x3) -> f191_out(x3) :|: TRUE f191_in(x4) -> f204_in(x4) :|: TRUE f204_out(x5) -> f191_out(x5) :|: TRUE f204_in(s(x6)) -> f209_in(x6) :|: TRUE f210_out -> f204_out(x7) :|: TRUE f209_out(x8) -> f204_out(s(x8)) :|: TRUE f204_in(x9) -> f210_in :|: TRUE f7_in(T1) -> f8_in(T1) :|: TRUE f8_out(x10) -> f7_out(x10) :|: TRUE f8_in(x11) -> f12_in(x11) :|: TRUE f11_out(x12) -> f8_out(x12) :|: TRUE f8_in(x13) -> f11_in(x13) :|: TRUE f12_out(x14) -> f8_out(x14) :|: TRUE f12_in(x15) -> f115_in(x15) :|: TRUE f115_out(x16) -> f12_out(x16) :|: TRUE f12_in(x17) -> f116_in(x17) :|: TRUE f116_out(x18) -> f12_out(x18) :|: TRUE f122_out(x19) -> f115_out(x19) :|: TRUE f123_out -> f115_out(x20) :|: TRUE f115_in(x21) -> f122_in(x21) :|: TRUE f115_in(x22) -> f123_in :|: TRUE f127_out(x23) -> f122_out(x23) :|: TRUE f126_out(x24) -> f127_in(x24) :|: TRUE f122_in(x25) -> f126_in(x25) :|: TRUE Start term: f7_in(T1) ---------------------------------------- (110) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f209_in(x) -> f126_in(x) :|: TRUE f126_in(x1) -> f191_in(x1) :|: TRUE f191_in(x4) -> f204_in(x4) :|: TRUE f204_in(s(x6)) -> f209_in(x6) :|: TRUE ---------------------------------------- (111) Obligation: Rules: f209_in(x) -> f126_in(x) :|: TRUE f126_in(x1) -> f191_in(x1) :|: TRUE f191_in(x4) -> f204_in(x4) :|: TRUE f204_in(s(x6)) -> f209_in(x6) :|: TRUE ---------------------------------------- (112) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (113) Obligation: Rules: f209_in(s(x6:0)) -> f209_in(x6:0) :|: TRUE ---------------------------------------- (114) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (115) Obligation: Rules: f209_in(s(x6:0)) -> f209_in(x6:0) :|: TRUE ---------------------------------------- (116) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f209_in(s(x6:0)) -> f209_in(x6:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (117) Obligation: Termination digraph: Nodes: (1) f209_in(s(x6:0)) -> f209_in(x6:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (118) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f209_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (119) Obligation: Rules: f209_in(s(x6:0)) -> f209_in(x6:0) ---------------------------------------- (120) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (121) Obligation: Q DP problem: The TRS P consists of the following rules: f209_in(s(x6:0)) -> f209_in(x6:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (122) 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: *f209_in(s(x6:0)) -> f209_in(x6:0) The graph contains the following edges 1 > 1 ---------------------------------------- (123) YES ---------------------------------------- (124) Obligation: Rules: f307_out(T73) -> f305_out(T73) :|: TRUE f305_in(x) -> f307_in(x) :|: TRUE f191_out(T34) -> f126_out(T34) :|: TRUE f126_in(x1) -> f191_in(x1) :|: TRUE f127_out(x2) -> f122_out(x2) :|: TRUE f126_out(x3) -> f127_in(x3) :|: TRUE f122_in(x4) -> f126_in(x4) :|: TRUE f204_in(s(T54)) -> f209_in(T54) :|: TRUE f210_out -> f204_out(x5) :|: TRUE f209_out(x6) -> f204_out(s(x6)) :|: TRUE f204_in(x7) -> f210_in :|: TRUE f7_out(x8) -> f127_out(x8) :|: TRUE f127_in(x9) -> f7_in(x9) :|: TRUE f305_out(x10) -> f306_in(x10) :|: TRUE f303_in(x11) -> f305_in(x11) :|: TRUE f306_out(x12) -> f303_out(x12) :|: TRUE f308_in(x13) -> f311_in :|: TRUE f310_out -> f308_out(s(T88)) :|: TRUE f308_in(s(x14)) -> f310_in :|: TRUE f311_out -> f308_out(x15) :|: TRUE f308_out(x16) -> f307_out(x16) :|: TRUE f309_out(x17) -> f307_out(x17) :|: TRUE f307_in(x18) -> f309_in(x18) :|: TRUE f307_in(x19) -> f308_in(x19) :|: TRUE f7_in(T1) -> f8_in(T1) :|: TRUE f8_out(x20) -> f7_out(x20) :|: TRUE f205_in -> f205_out :|: TRUE f203_in(x21) -> f206_in :|: TRUE f206_out -> f203_out(x22) :|: TRUE f203_in(0) -> f205_in :|: TRUE f205_out -> f203_out(0) :|: TRUE f313_in(T94) -> f305_in(T94) :|: TRUE f305_out(x23) -> f313_out(x23) :|: TRUE f191_in(x24) -> f203_in(x24) :|: TRUE f203_out(x25) -> f191_out(x25) :|: TRUE f191_in(x26) -> f204_in(x26) :|: TRUE f204_out(x27) -> f191_out(x27) :|: TRUE f310_in -> f310_out :|: TRUE f306_in(x28) -> f7_in(x28) :|: TRUE f7_out(x29) -> f306_out(x29) :|: TRUE f122_out(x30) -> f115_out(x30) :|: TRUE f123_out -> f115_out(x31) :|: TRUE f115_in(x32) -> f122_in(x32) :|: TRUE f115_in(x33) -> f123_in :|: TRUE f309_in(x34) -> f314_in :|: TRUE f309_in(s(x35)) -> f313_in(x35) :|: TRUE f313_out(x36) -> f309_out(s(x36)) :|: TRUE f314_out -> f309_out(x37) :|: TRUE f8_in(x38) -> f12_in(x38) :|: TRUE f11_out(x39) -> f8_out(x39) :|: TRUE f8_in(x40) -> f11_in(x40) :|: TRUE f12_out(x41) -> f8_out(x41) :|: TRUE f126_out(x42) -> f209_out(x42) :|: TRUE f209_in(x43) -> f126_in(x43) :|: TRUE f12_in(x44) -> f115_in(x44) :|: TRUE f115_out(x45) -> f12_out(x45) :|: TRUE f12_in(x46) -> f116_in(x46) :|: TRUE f116_out(x47) -> f12_out(x47) :|: TRUE f303_out(x48) -> f116_out(x48) :|: TRUE f116_in(x49) -> f304_in :|: TRUE f116_in(x50) -> f303_in(x50) :|: TRUE f304_out -> f116_out(x51) :|: TRUE Start term: f7_in(T1) ---------------------------------------- (125) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f307_out(T73) -> f305_out(T73) :|: TRUE f305_in(x) -> f307_in(x) :|: TRUE f191_out(T34) -> f126_out(T34) :|: TRUE f126_in(x1) -> f191_in(x1) :|: TRUE f126_out(x3) -> f127_in(x3) :|: TRUE f122_in(x4) -> f126_in(x4) :|: TRUE f204_in(s(T54)) -> f209_in(T54) :|: TRUE f209_out(x6) -> f204_out(s(x6)) :|: TRUE f127_in(x9) -> f7_in(x9) :|: TRUE f305_out(x10) -> f306_in(x10) :|: TRUE f303_in(x11) -> f305_in(x11) :|: TRUE f310_out -> f308_out(s(T88)) :|: TRUE f308_in(s(x14)) -> f310_in :|: TRUE f308_out(x16) -> f307_out(x16) :|: TRUE f309_out(x17) -> f307_out(x17) :|: TRUE f307_in(x18) -> f309_in(x18) :|: TRUE f307_in(x19) -> f308_in(x19) :|: TRUE f7_in(T1) -> f8_in(T1) :|: TRUE f205_in -> f205_out :|: TRUE f203_in(0) -> f205_in :|: TRUE f205_out -> f203_out(0) :|: TRUE f313_in(T94) -> f305_in(T94) :|: TRUE f305_out(x23) -> f313_out(x23) :|: TRUE f191_in(x24) -> f203_in(x24) :|: TRUE f203_out(x25) -> f191_out(x25) :|: TRUE f191_in(x26) -> f204_in(x26) :|: TRUE f204_out(x27) -> f191_out(x27) :|: TRUE f310_in -> f310_out :|: TRUE f306_in(x28) -> f7_in(x28) :|: TRUE f115_in(x32) -> f122_in(x32) :|: TRUE f309_in(s(x35)) -> f313_in(x35) :|: TRUE f313_out(x36) -> f309_out(s(x36)) :|: TRUE f8_in(x38) -> f12_in(x38) :|: TRUE f126_out(x42) -> f209_out(x42) :|: TRUE f209_in(x43) -> f126_in(x43) :|: TRUE f12_in(x44) -> f115_in(x44) :|: TRUE f12_in(x46) -> f116_in(x46) :|: TRUE f116_in(x50) -> f303_in(x50) :|: TRUE ---------------------------------------- (126) Obligation: Rules: f307_out(T73) -> f305_out(T73) :|: TRUE f305_in(x) -> f307_in(x) :|: TRUE f191_out(T34) -> f126_out(T34) :|: TRUE f126_in(x1) -> f191_in(x1) :|: TRUE f126_out(x3) -> f127_in(x3) :|: TRUE f122_in(x4) -> f126_in(x4) :|: TRUE f204_in(s(T54)) -> f209_in(T54) :|: TRUE f209_out(x6) -> f204_out(s(x6)) :|: TRUE f127_in(x9) -> f7_in(x9) :|: TRUE f305_out(x10) -> f306_in(x10) :|: TRUE f303_in(x11) -> f305_in(x11) :|: TRUE f310_out -> f308_out(s(T88)) :|: TRUE f308_in(s(x14)) -> f310_in :|: TRUE f308_out(x16) -> f307_out(x16) :|: TRUE f309_out(x17) -> f307_out(x17) :|: TRUE f307_in(x18) -> f309_in(x18) :|: TRUE f307_in(x19) -> f308_in(x19) :|: TRUE f7_in(T1) -> f8_in(T1) :|: TRUE f205_in -> f205_out :|: TRUE f203_in(0) -> f205_in :|: TRUE f205_out -> f203_out(0) :|: TRUE f313_in(T94) -> f305_in(T94) :|: TRUE f305_out(x23) -> f313_out(x23) :|: TRUE f191_in(x24) -> f203_in(x24) :|: TRUE f203_out(x25) -> f191_out(x25) :|: TRUE f191_in(x26) -> f204_in(x26) :|: TRUE f204_out(x27) -> f191_out(x27) :|: TRUE f310_in -> f310_out :|: TRUE f306_in(x28) -> f7_in(x28) :|: TRUE f115_in(x32) -> f122_in(x32) :|: TRUE f309_in(s(x35)) -> f313_in(x35) :|: TRUE f313_out(x36) -> f309_out(s(x36)) :|: TRUE f8_in(x38) -> f12_in(x38) :|: TRUE f126_out(x42) -> f209_out(x42) :|: TRUE f209_in(x43) -> f126_in(x43) :|: TRUE f12_in(x44) -> f115_in(x44) :|: TRUE f12_in(x46) -> f116_in(x46) :|: TRUE f116_in(x50) -> f303_in(x50) :|: TRUE ---------------------------------------- (127) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (128) Obligation: Rules: f191_out(T34:0) -> f12_in(T34:0) :|: TRUE f12_in(x44:0) -> f126_in(x44:0) :|: TRUE f305_in(s(x14:0)) -> f307_out(s(T88:0)) :|: TRUE f305_in(s(x35:0)) -> f305_in(x35:0) :|: TRUE f307_out(T73:0) -> f307_out(s(T73:0)) :|: TRUE f12_in(x46:0) -> f305_in(x46:0) :|: TRUE f126_in(s(T54:0)) -> f126_in(T54:0) :|: TRUE f307_out(x) -> f12_in(x) :|: TRUE f126_in(cons_0) -> f191_out(0) :|: TRUE && cons_0 = 0 f191_out(x1) -> f191_out(s(x1)) :|: TRUE ---------------------------------------- (129) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (130) Obligation: Rules: f191_out(T34:0) -> f12_in(T34:0) :|: TRUE f12_in(x44:0) -> f126_in(x44:0) :|: TRUE f305_in(s(x14:0)) -> f307_out(s(T88:0)) :|: TRUE f305_in(s(x35:0)) -> f305_in(x35:0) :|: TRUE f307_out(T73:0) -> f307_out(s(T73:0)) :|: TRUE f12_in(x46:0) -> f305_in(x46:0) :|: TRUE f126_in(s(T54:0)) -> f126_in(T54:0) :|: TRUE f307_out(x) -> f12_in(x) :|: TRUE f126_in(cons_0) -> f191_out(0) :|: TRUE && cons_0 = 0 f191_out(x1) -> f191_out(s(x1)) :|: TRUE ---------------------------------------- (131) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f191_out(T34:0) -> f12_in(T34:0) :|: TRUE (2) f12_in(x44:0) -> f126_in(x44:0) :|: TRUE (3) f305_in(s(x14:0)) -> f307_out(s(T88:0)) :|: TRUE (4) f305_in(s(x35:0)) -> f305_in(x35:0) :|: TRUE (5) f307_out(T73:0) -> f307_out(s(T73:0)) :|: TRUE (6) f12_in(x46:0) -> f305_in(x46:0) :|: TRUE (7) f126_in(s(T54:0)) -> f126_in(T54:0) :|: TRUE (8) f307_out(x) -> f12_in(x) :|: TRUE (9) f126_in(cons_0) -> f191_out(0) :|: TRUE && cons_0 = 0 (10) f191_out(x1) -> f191_out(s(x1)) :|: TRUE Arcs: (1) -> (2), (6) (2) -> (7), (9) (3) -> (5), (8) (4) -> (3), (4) (5) -> (5), (8) (6) -> (3), (4) (7) -> (7), (9) (8) -> (2), (6) (9) -> (1), (10) (10) -> (1), (10) This digraph is fully evaluated! ---------------------------------------- (132) Obligation: Termination digraph: Nodes: (1) f191_out(T34:0) -> f12_in(T34:0) :|: TRUE (2) f191_out(x1) -> f191_out(s(x1)) :|: TRUE (3) f126_in(cons_0) -> f191_out(0) :|: TRUE && cons_0 = 0 (4) f126_in(s(T54:0)) -> f126_in(T54:0) :|: TRUE (5) f12_in(x44:0) -> f126_in(x44:0) :|: TRUE (6) f307_out(x) -> f12_in(x) :|: TRUE (7) f307_out(T73:0) -> f307_out(s(T73:0)) :|: TRUE (8) f305_in(s(x14:0)) -> f307_out(s(T88:0)) :|: TRUE (9) f305_in(s(x35:0)) -> f305_in(x35:0) :|: TRUE (10) f12_in(x46:0) -> f305_in(x46:0) :|: TRUE Arcs: (1) -> (5), (10) (2) -> (1), (2) (3) -> (1), (2) (4) -> (3), (4) (5) -> (3), (4) (6) -> (5), (10) (7) -> (6), (7) (8) -> (6), (7) (9) -> (8), (9) (10) -> (8), (9) This digraph is fully evaluated! ---------------------------------------- (133) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (134) Obligation: Rules: f305_in(s(x35:0:0)) -> f305_in(x35:0:0) :|: TRUE f126_in(s(T54:0:0)) -> f126_in(T54:0:0) :|: TRUE f307_out(T73:0:0) -> f307_out(s(T73:0:0)) :|: TRUE f126_in(cons_0) -> f191_out(0) :|: TRUE && cons_0 = 0 f307_out(x:0) -> f12_in(x:0) :|: TRUE f305_in(s(x14:0:0)) -> f307_out(s(T88:0:0)) :|: TRUE f12_in(x46:0:0) -> f305_in(x46:0:0) :|: TRUE f191_out(T34:0:0) -> f12_in(T34:0:0) :|: TRUE f191_out(x1:0) -> f191_out(s(x1:0)) :|: TRUE f12_in(x44:0:0) -> f126_in(x44:0:0) :|: TRUE ---------------------------------------- (135) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (136) Obligation: Rules: f305_in(s(x)) -> f305_in(x) :|: TRUE f126_in(s(x1)) -> f126_in(x1) :|: TRUE f307_out(x2) -> f307_out(s(x2)) :|: TRUE f126_in(cons_0) -> f191_out(0) :|: TRUE && cons_0 = 0 f307_out(x4) -> f12_in(x4) :|: TRUE f305_in(s(x5)) -> f307_out(s(x6)) :|: TRUE f12_in(x7) -> f305_in(x7) :|: TRUE f191_out(x8) -> f12_in(x8) :|: TRUE f191_out(x9) -> f191_out(s(x9)) :|: TRUE f12_in(x10) -> f126_in(x10) :|: TRUE ---------------------------------------- (137) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "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 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": [] } }, "274": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "351": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "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": [] } }, "352": { "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": [] } }, "276": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T37 T39) (in (s T37) T40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "353": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "112": { "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": [] } }, "277": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "354": { "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": [] } }, "278": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T37 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "355": { "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": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (s T37) T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "356": { "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": [] } }, "357": { "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": [] } }, "358": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "117": { "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": [] } }, "315": { "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": [] } }, "359": { "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": [] } }, "118": { "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": [] } }, "316": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "119": { "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": [] } }, "317": { "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": [] } }, "318": { "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": [] } }, "319": { "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": [] } }, "97": { "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": [] } }, "280": { "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": [] } }, "281": { "goal": [{ "clause": 3, "scope": 3, "term": "(less T37 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "282": { "goal": [{ "clause": 4, "scope": 3, "term": "(less T37 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "360": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "284": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "361": { "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": [] } }, "120": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (less T13 T17) (in T13 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "285": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "362": { "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": [] } }, "121": { "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": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T55 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "287": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "320": { "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": [] } }, "288": { "goal": [{ "clause": 2, "scope": 1, "term": "(in T13 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "321": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (0) T24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "289": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T78 T74) (in T74 T79))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "4": { "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": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "290": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T78 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "292": { "goal": [{ "clause": -1, "scope": -1, "term": "(in T74 T82)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "293": { "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": [] } }, "294": { "goal": [{ "clause": 3, "scope": 4, "term": "(less T78 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "295": { "goal": [{ "clause": 4, "scope": 4, "term": "(less T78 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T74"], "free": [], "exprvars": [] } }, "298": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "299": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "334": { "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": [] } }, "335": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "336": { "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": [] } }, "337": { "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": [] } }, "338": { "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": [] } }, "339": { "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": [] } }, "340": { "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": [] } }, "341": { "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": [] } }, "342": { "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": [] } }, "343": { "goal": [{ "clause": -1, "scope": -1, "term": "(in (0) T162)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "300": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "344": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "301": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T96 T95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T95"], "free": [], "exprvars": [] } }, "345": { "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": [] } }, "302": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "346": { "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": [] } }, "347": { "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": [] } }, "348": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "349": { "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": [] } }, "108": { "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": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 97, "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": 4, "to": 108, "label": "EVAL-BACKTRACK" }, { "from": 97, "to": 112, "label": "SUCCESS" }, { "from": 108, "to": 338, "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": 108, "to": 339, "label": "EVAL-BACKTRACK" }, { "from": 112, "to": 117, "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": 112, "to": 118, "label": "EVAL-BACKTRACK" }, { "from": 117, "to": 119, "label": "CASE" }, { "from": 118, "to": 315, "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": 118, "to": 316, "label": "EVAL-BACKTRACK" }, { "from": 119, "to": 120, "label": "PARALLEL" }, { "from": 119, "to": 121, "label": "PARALLEL" }, { "from": 120, "to": 124, "label": "EVAL with clause\nless(0, s(X24)).\nand substitutionT13 -> 0,\nX24 -> T23,\nT17 -> s(T23),\nT18 -> T24" }, { "from": 120, "to": 125, "label": "EVAL-BACKTRACK" }, { "from": 121, "to": 274, "label": "PARALLEL" }, { "from": 121, "to": 275, "label": "PARALLEL" }, { "from": 124, "to": 1, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T24" }, { "from": 274, "to": 276, "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": 274, "to": 277, "label": "EVAL-BACKTRACK" }, { "from": 275, "to": 288, "label": "FAILURE" }, { "from": 276, "to": 278, "label": "SPLIT 1" }, { "from": 276, "to": 279, "label": "SPLIT 2\nnew knowledge:\nT37 is ground\nreplacements:T40 -> T43" }, { "from": 278, "to": 280, "label": "CASE" }, { "from": 279, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T37)\nT2 -> T43" }, { "from": 280, "to": 281, "label": "PARALLEL" }, { "from": 280, "to": 282, "label": "PARALLEL" }, { "from": 281, "to": 283, "label": "EVAL with clause\nless(0, s(X49)).\nand substitutionT37 -> 0,\nX49 -> T50,\nT39 -> s(T50)" }, { "from": 281, "to": 284, "label": "EVAL-BACKTRACK" }, { "from": 282, "to": 286, "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": 282, "to": 287, "label": "EVAL-BACKTRACK" }, { "from": 283, "to": 285, "label": "SUCCESS" }, { "from": 286, "to": 278, "label": "INSTANCE with matching:\nT37 -> T55\nT39 -> T57" }, { "from": 288, "to": 289, "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": 288, "to": 290, "label": "EVAL-BACKTRACK" }, { "from": 289, "to": 291, "label": "SPLIT 1" }, { "from": 289, "to": 292, "label": "SPLIT 2\nnew knowledge:\nT78 is ground\nT74 is ground\nreplacements:T79 -> T82" }, { "from": 291, "to": 293, "label": "CASE" }, { "from": 292, "to": 1, "label": "INSTANCE with matching:\nT1 -> T74\nT2 -> T82" }, { "from": 293, "to": 294, "label": "PARALLEL" }, { "from": 293, "to": 295, "label": "PARALLEL" }, { "from": 294, "to": 298, "label": "EVAL with clause\nless(0, s(X84)).\nand substitutionT78 -> 0,\nX84 -> T89,\nT74 -> s(T89)" }, { "from": 294, "to": 299, "label": "EVAL-BACKTRACK" }, { "from": 295, "to": 301, "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": 295, "to": 302, "label": "EVAL-BACKTRACK" }, { "from": 298, "to": 300, "label": "SUCCESS" }, { "from": 301, "to": 291, "label": "INSTANCE with matching:\nT78 -> T96\nT74 -> T95" }, { "from": 315, "to": 317, "label": "CASE" }, { "from": 317, "to": 318, "label": "PARALLEL" }, { "from": 317, "to": 319, "label": "PARALLEL" }, { "from": 318, "to": 320, "label": "EVAL with clause\nless(0, s(X111)).\nand substitutionT113 -> 0,\nX111 -> T119,\nT109 -> s(T119),\nT114 -> T120" }, { "from": 318, "to": 321, "label": "EVAL-BACKTRACK" }, { "from": 319, "to": 334, "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": 319, "to": 335, "label": "EVAL-BACKTRACK" }, { "from": 320, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T119)\nT2 -> T120" }, { "from": 334, "to": 336, "label": "SPLIT 1" }, { "from": 334, "to": 337, "label": "SPLIT 2\nnew knowledge:\nT133 is ground\nT132 is ground\nreplacements:T134 -> T137,\nT2 -> T138" }, { "from": 336, "to": 291, "label": "INSTANCE with matching:\nT78 -> T133\nT74 -> T132" }, { "from": 337, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T132)\nT2 -> T137" }, { "from": 338, "to": 340, "label": "CASE" }, { "from": 339, "to": 352, "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": 339, "to": 353, "label": "EVAL-BACKTRACK" }, { "from": 340, "to": 341, "label": "PARALLEL" }, { "from": 340, "to": 342, "label": "PARALLEL" }, { "from": 341, "to": 343, "label": "EVAL with clause\nless(0, s(X146)).\nand substitutionT151 -> 0,\nX146 -> T161,\nT155 -> s(T161),\nT156 -> T162" }, { "from": 341, "to": 344, "label": "EVAL-BACKTRACK" }, { "from": 342, "to": 345, "label": "PARALLEL" }, { "from": 342, "to": 346, "label": "PARALLEL" }, { "from": 343, "to": 1, "label": "INSTANCE with matching:\nT1 -> 0\nT2 -> T162" }, { "from": 345, "to": 347, "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": 345, "to": 348, "label": "EVAL-BACKTRACK" }, { "from": 346, "to": 349, "label": "FAILURE" }, { "from": 347, "to": 276, "label": "INSTANCE with matching:\nT37 -> T175\nT39 -> T177\nT40 -> T178" }, { "from": 349, "to": 350, "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": 349, "to": 351, "label": "EVAL-BACKTRACK" }, { "from": 350, "to": 289, "label": "INSTANCE with matching:\nT78 -> T193\nT74 -> T189\nT79 -> T194" }, { "from": 352, "to": 354, "label": "CASE" }, { "from": 354, "to": 355, "label": "PARALLEL" }, { "from": 354, "to": 356, "label": "PARALLEL" }, { "from": 355, "to": 357, "label": "EVAL with clause\nless(0, s(X191)).\nand substitutionT205 -> 0,\nX191 -> T211,\nT201 -> s(T211),\nT206 -> T212" }, { "from": 355, "to": 358, "label": "EVAL-BACKTRACK" }, { "from": 356, "to": 359, "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": 356, "to": 360, "label": "EVAL-BACKTRACK" }, { "from": 357, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T211)\nT2 -> T212" }, { "from": 359, "to": 361, "label": "SPLIT 1" }, { "from": 359, "to": 362, "label": "SPLIT 2\nnew knowledge:\nT225 is ground\nT224 is ground\nreplacements:T226 -> T229,\nT2 -> T230" }, { "from": 361, "to": 291, "label": "INSTANCE with matching:\nT78 -> T225\nT74 -> T224" }, { "from": 362, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T224)\nT2 -> T229" } ], "type": "Graph" } } ---------------------------------------- (138) 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) ---------------------------------------- (139) 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 ---------------------------------------- (140) 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 ---------------------------------------- (141) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 15 less nodes. ---------------------------------------- (142) Complex Obligation (AND) ---------------------------------------- (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) 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 ---------------------------------------- (144) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (145) 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 ---------------------------------------- (146) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (147) 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. ---------------------------------------- (148) 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 ---------------------------------------- (149) YES ---------------------------------------- (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) 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 ---------------------------------------- (151) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (152) 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 ---------------------------------------- (153) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (154) 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. ---------------------------------------- (155) 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 ---------------------------------------- (156) YES ---------------------------------------- (157) 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 ---------------------------------------- (158) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (159) 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. ---------------------------------------- (160) TransformationProof (SOUND) By narrowing [LPAR04] the rule PC_IN_AGA(X2) -> U7_AGA(X2, lesscD_in_ag(X2)) at position [1] we obtained the following new rules [LPAR04]: (PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))),PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0)))) (PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))),PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0)))) ---------------------------------------- (161) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(X1) -> PC_IN_AGA(X1) 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)) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) 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. ---------------------------------------- (162) TransformationProof (SOUND) By narrowing [LPAR04] the rule PB_IN_GAA(X1) -> U4_GAA(X1, lesscE_in_ga(X1)) at position [1] we obtained the following new rules [LPAR04]: (PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)),PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0))) (PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))),PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0)))) ---------------------------------------- (163) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(X1) -> PC_IN_AGA(X1) 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) 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)) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)) PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))) 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. ---------------------------------------- (164) TransformationProof (SOUND) By narrowing [LPAR04] the rule INA_IN_GA(s(X1)) -> U14_GA(X1, lesscD_in_ag(X1)) at position [1] we obtained the following new rules [LPAR04]: (INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0))),INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0)))) (INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0))),INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0)))) ---------------------------------------- (165) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(X1) -> PC_IN_AGA(X1) 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) U4_GAA(X1, lesscE_out_ga(X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(X1)) -> INA_IN_GA(s(X1)) U14_GA(X1, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1)) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)) PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0))) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) 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. ---------------------------------------- (166) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U7_AGA(X2, lesscD_out_ag(X1, X2)) -> INA_IN_GA(X2) we obtained the following new rules [LPAR04]: (U7_AGA(s(z0), lesscD_out_ag(0, s(z0))) -> INA_IN_GA(s(z0)),U7_AGA(s(z0), lesscD_out_ag(0, s(z0))) -> INA_IN_GA(s(z0))) (U7_AGA(s(z0), lesscD_out_ag(x1, s(z0))) -> INA_IN_GA(s(z0)),U7_AGA(s(z0), lesscD_out_ag(x1, s(z0))) -> INA_IN_GA(s(z0))) ---------------------------------------- (167) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(X1) -> PC_IN_AGA(X1) INA_IN_GA(0) -> INA_IN_GA(0) INA_IN_GA(s(X1)) -> PB_IN_GAA(X1) U4_GAA(X1, lesscE_out_ga(X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(X1)) -> INA_IN_GA(s(X1)) U14_GA(X1, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1)) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)) PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0))) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) U7_AGA(s(z0), lesscD_out_ag(0, s(z0))) -> INA_IN_GA(s(z0)) U7_AGA(s(z0), lesscD_out_ag(x1, s(z0))) -> INA_IN_GA(s(z0)) 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. ---------------------------------------- (168) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (169) Complex Obligation (AND) ---------------------------------------- (170) Obligation: Q DP problem: The TRS P consists of the following rules: PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) U7_AGA(s(z0), lesscD_out_ag(0, s(z0))) -> INA_IN_GA(s(z0)) INA_IN_GA(X1) -> PC_IN_AGA(X1) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) U7_AGA(s(z0), lesscD_out_ag(x1, s(z0))) -> INA_IN_GA(s(z0)) INA_IN_GA(s(X1)) -> PB_IN_GAA(X1) PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)) 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(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0))) U14_GA(X1, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))) 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. ---------------------------------------- (171) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule INA_IN_GA(X1) -> PC_IN_AGA(X1) we obtained the following new rules [LPAR04]: (INA_IN_GA(s(z0)) -> PC_IN_AGA(s(z0)),INA_IN_GA(s(z0)) -> PC_IN_AGA(s(z0))) ---------------------------------------- (172) Obligation: Q DP problem: The TRS P consists of the following rules: PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) U7_AGA(s(z0), lesscD_out_ag(0, s(z0))) -> INA_IN_GA(s(z0)) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) U7_AGA(s(z0), lesscD_out_ag(x1, s(z0))) -> INA_IN_GA(s(z0)) INA_IN_GA(s(X1)) -> PB_IN_GAA(X1) PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)) 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(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0))) U14_GA(X1, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))) INA_IN_GA(s(z0)) -> PC_IN_AGA(s(z0)) 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. ---------------------------------------- (173) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U4_GAA(X1, lesscE_out_ga(X1)) -> INA_IN_GA(s(X1)) we obtained the following new rules [LPAR04]: (U4_GAA(0, lesscE_out_ga(0)) -> INA_IN_GA(s(0)),U4_GAA(0, lesscE_out_ga(0)) -> INA_IN_GA(s(0))) (U4_GAA(s(z0), lesscE_out_ga(s(z0))) -> INA_IN_GA(s(s(z0))),U4_GAA(s(z0), lesscE_out_ga(s(z0))) -> INA_IN_GA(s(s(z0)))) ---------------------------------------- (174) Obligation: Q DP problem: The TRS P consists of the following rules: PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), lesscD_out_ag(0, s(x0))) U7_AGA(s(z0), lesscD_out_ag(0, s(z0))) -> INA_IN_GA(s(z0)) PC_IN_AGA(s(x0)) -> U7_AGA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) U7_AGA(s(z0), lesscD_out_ag(x1, s(z0))) -> INA_IN_GA(s(z0)) INA_IN_GA(s(X1)) -> PB_IN_GAA(X1) PB_IN_GAA(0) -> U4_GAA(0, lesscE_out_ga(0)) INA_IN_GA(s(X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), lesscD_out_ag(0, s(x0))) U14_GA(X1, lesscD_out_ag(X2, X1)) -> INA_IN_GA(s(X1)) INA_IN_GA(s(s(x0))) -> U14_GA(s(x0), U24_ag(x0, lesscD_in_ag(x0))) PB_IN_GAA(s(x0)) -> U4_GAA(s(x0), U23_ga(x0, lesscE_in_ga(x0))) INA_IN_GA(s(z0)) -> PC_IN_AGA(s(z0)) U4_GAA(0, lesscE_out_ga(0)) -> INA_IN_GA(s(0)) U4_GAA(s(z0), lesscE_out_ga(s(z0))) -> INA_IN_GA(s(s(z0))) 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. ---------------------------------------- (175) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(0) -> INA_IN_GA(0) 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. ---------------------------------------- (176) 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. ---------------------------------------- (177) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(0) -> INA_IN_GA(0) R is empty. 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. ---------------------------------------- (178) 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]. lesscE_in_ga(x0) U23_ga(x0, x1) lesscD_in_ag(x0) U24_ag(x0, x1) ---------------------------------------- (179) Obligation: Q DP problem: The TRS P consists of the following rules: INA_IN_GA(0) -> INA_IN_GA(0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains.