/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 my_divide(a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) IntegerArithmeticTransformerProof [SOUND, 0 ms] (2) Prolog (3) UnifyTransformerProof [EQUIVALENT, 0 ms] (4) Prolog (5) PrologToPiTRSProof [SOUND, 0 ms] (6) PiTRS (7) DependencyPairsProof [EQUIVALENT, 0 ms] (8) PiDP (9) DependencyGraphProof [EQUIVALENT, 0 ms] (10) AND (11) PiDP (12) UsableRulesProof [EQUIVALENT, 0 ms] (13) PiDP (14) PiDPToQDPProof [SOUND, 0 ms] (15) QDP (16) QDPSizeChangeProof [EQUIVALENT, 0 ms] (17) YES (18) PiDP (19) UsableRulesProof [EQUIVALENT, 0 ms] (20) PiDP (21) PiDPToQDPProof [SOUND, 0 ms] (22) QDP (23) UsableRulesReductionPairsProof [EQUIVALENT, 23 ms] (24) QDP (25) UsableRulesProof [EQUIVALENT, 0 ms] (26) QDP (27) QReductionProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) QDP (33) QReductionProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) QReductionProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [SOUND, 0 ms] (42) QDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) QDP (45) QReductionProof [EQUIVALENT, 0 ms] (46) QDP (47) NonTerminationLoopProof [COMPLETE, 0 ms] (48) NO (49) PrologToPiTRSProof [SOUND, 22 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) MRRProof [EQUIVALENT, 26 ms] (68) QDP (69) UsableRulesProof [EQUIVALENT, 0 ms] (70) QDP (71) QReductionProof [EQUIVALENT, 0 ms] (72) QDP (73) MRRProof [EQUIVALENT, 11 ms] (74) QDP (75) UsableRulesProof [EQUIVALENT, 0 ms] (76) QDP (77) QReductionProof [EQUIVALENT, 0 ms] (78) QDP (79) TransformationProof [EQUIVALENT, 0 ms] (80) QDP (81) UsableRulesProof [EQUIVALENT, 0 ms] (82) QDP (83) QReductionProof [EQUIVALENT, 0 ms] (84) QDP (85) TransformationProof [EQUIVALENT, 0 ms] (86) QDP (87) UsableRulesProof [EQUIVALENT, 0 ms] (88) QDP (89) QReductionProof [EQUIVALENT, 0 ms] (90) QDP (91) TransformationProof [SOUND, 0 ms] (92) QDP (93) UsableRulesProof [EQUIVALENT, 0 ms] (94) QDP (95) QReductionProof [EQUIVALENT, 0 ms] (96) QDP (97) TransformationProof [EQUIVALENT, 0 ms] (98) QDP (99) NonTerminationLoopProof [COMPLETE, 0 ms] (100) NO (101) UndefinedPredicateHandlerProof [SOUND, 0 ms] (102) Prolog (103) PrologToPiTRSProof [SOUND, 0 ms] (104) PiTRS (105) DependencyPairsProof [EQUIVALENT, 4 ms] (106) PiDP (107) DependencyGraphProof [EQUIVALENT, 0 ms] (108) PiDP (109) UsableRulesProof [EQUIVALENT, 0 ms] (110) PiDP (111) PiDPToQDPProof [SOUND, 0 ms] (112) QDP (113) TransformationProof [EQUIVALENT, 0 ms] (114) QDP (115) UsableRulesProof [EQUIVALENT, 0 ms] (116) QDP (117) QReductionProof [EQUIVALENT, 0 ms] (118) QDP (119) NonTerminationLoopProof [COMPLETE, 0 ms] (120) NO (121) PrologToPiTRSProof [SOUND, 0 ms] (122) PiTRS (123) DependencyPairsProof [EQUIVALENT, 7 ms] (124) PiDP (125) DependencyGraphProof [EQUIVALENT, 0 ms] (126) PiDP (127) UsableRulesProof [EQUIVALENT, 0 ms] (128) PiDP (129) PiDPToQDPProof [SOUND, 0 ms] (130) QDP (131) TransformationProof [EQUIVALENT, 0 ms] (132) QDP (133) UsableRulesProof [EQUIVALENT, 0 ms] (134) QDP (135) QReductionProof [EQUIVALENT, 0 ms] (136) QDP (137) NonTerminationLoopProof [COMPLETE, 0 ms] (138) NO ---------------------------------------- (0) Obligation: Clauses: my_divide(X) :- ','(>(X, 0), my_divide(//(X, 2))). my_divide(X) :- is(0, X). Query: my_divide(a) ---------------------------------------- (1) IntegerArithmeticTransformerProof (SOUND) Added definitions of predefined predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: my_divide(X) :- ','(=(X1, X), ','(=(X2, zero), ','(isGreater(X1, X2), my_divide(//(X, succ(succ(zero))))))). my_divide(X) :- =(zero, X). isPlus(zero, X, X). isPlus(succ(X), zero, succ(X)). isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z). isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), zero, pred(X)). isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z). isMinus(X, zero, X). isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z). isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z). isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z). isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z). isTimes(X, zero, zero). isTimes(zero, succ(Y), zero). isTimes(zero, pred(Y), zero). isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)). isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)). isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)). isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)). isDiv(zero, succ(Y), zero). isDiv(zero, pred(Y), zero). isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)). isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)). isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))). isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)). isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)). isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))). isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))). isGreater(succ(X), zero). isGreater(succ(X), pred(Y)). isGreater(succ(X), succ(Y)) :- isGreater(X, Y). isGreater(zero, pred(Y)). isGreater(pred(X), pred(Y)) :- isGreater(X, Y). Query: my_divide(a) ---------------------------------------- (3) UnifyTransformerProof (EQUIVALENT) Added a fact for the built-in = predicate [PROLOG]. ---------------------------------------- (4) Obligation: Clauses: my_divide(X) :- ','(=(X1, X), ','(=(X2, zero), ','(isGreater(X1, X2), my_divide(//(X, succ(succ(zero))))))). my_divide(X) :- =(zero, X). isPlus(zero, X, X). isPlus(succ(X), zero, succ(X)). isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z). isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), zero, pred(X)). isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z). isMinus(X, zero, X). isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z). isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z). isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z). isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z). isTimes(X, zero, zero). isTimes(zero, succ(Y), zero). isTimes(zero, pred(Y), zero). isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)). isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)). isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)). isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)). isDiv(zero, succ(Y), zero). isDiv(zero, pred(Y), zero). isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)). isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)). isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))). isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)). isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)). isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))). isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))). isGreater(succ(X), zero). isGreater(succ(X), pred(Y)). isGreater(succ(X), succ(Y)) :- isGreater(X, Y). isGreater(zero, pred(Y)). isGreater(pred(X), pred(Y)) :- isGreater(X, Y). =(X, X). Query: my_divide(a) ---------------------------------------- (5) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_divide_in_1: (f) isGreater_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (6) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) ---------------------------------------- (7) 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: MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) MY_DIVIDE_IN_A(X) -> =_IN_AA(X1, X) U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U1_A(X, =_out_aa(X1, X)) -> =_IN_AG(X2, zero) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> ISGREATER_IN_AG(X1, X2) ISGREATER_IN_AG(succ(X), succ(Y)) -> U39_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(pred(X), pred(Y)) -> U40_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) U3_A(X, isGreater_out_ag(X1, X2)) -> U4_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U5_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) =_IN_AA(x1, x2) = =_IN_AA U2_A(x1, x2, x3) = U2_A(x3) =_IN_AG(x1, x2) = =_IN_AG(x2) U3_A(x1, x2) = U3_A(x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) U39_AG(x1, x2, x3) = U39_AG(x3) U40_AG(x1, x2, x3) = U40_AG(x3) U4_A(x1, x2) = U4_A(x2) U5_A(x1, x2) = U5_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) MY_DIVIDE_IN_A(X) -> =_IN_AA(X1, X) U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U1_A(X, =_out_aa(X1, X)) -> =_IN_AG(X2, zero) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> ISGREATER_IN_AG(X1, X2) ISGREATER_IN_AG(succ(X), succ(Y)) -> U39_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(pred(X), pred(Y)) -> U40_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) U3_A(X, isGreater_out_ag(X1, X2)) -> U4_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U5_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) =_IN_AA(x1, x2) = =_IN_AA U2_A(x1, x2, x3) = U2_A(x3) =_IN_AG(x1, x2) = =_IN_AG(x2) U3_A(x1, x2) = U3_A(x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) U39_AG(x1, x2, x3) = U39_AG(x3) U40_AG(x1, x2, x3) = U40_AG(x3) U4_A(x1, x2) = U4_A(x2) U5_A(x1, x2) = U5_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes. ---------------------------------------- (10) Complex Obligation (AND) ---------------------------------------- (11) Obligation: Pi DP problem: The TRS P consists of the following rules: ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (12) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (13) Obligation: Pi DP problem: The TRS P consists of the following rules: ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) R is empty. The argument filtering Pi contains the following mapping: pred(x1) = pred(x1) succ(x1) = succ(x1) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (14) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: ISGREATER_IN_AG(pred(Y)) -> ISGREATER_IN_AG(Y) ISGREATER_IN_AG(succ(Y)) -> ISGREATER_IN_AG(Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (16) 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: *ISGREATER_IN_AG(pred(Y)) -> ISGREATER_IN_AG(Y) The graph contains the following edges 1 > 1 *ISGREATER_IN_AG(succ(Y)) -> ISGREATER_IN_AG(Y) The graph contains the following edges 1 > 1 ---------------------------------------- (17) YES ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2) = U3_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) The TRS R consists of the following rules: =_in_ag(X, X) -> =_out_ag(X, X) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) =_in_aa(X, X) -> =_out_aa(X, X) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) The argument filtering Pi contains the following mapping: =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1) zero = zero isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x3) U40_ag(x1, x2, x3) = U40_ag(x3) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2) = U3_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X) isGreater_in_ag(zero) -> isGreater_out_ag isGreater_in_ag(pred(Y)) -> isGreater_out_ag isGreater_in_ag(succ(Y)) -> U39_ag(isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(isGreater_in_ag(Y)) =_in_aa -> =_out_aa U39_ag(isGreater_out_ag) -> isGreater_out_ag U40_ag(isGreater_out_ag) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U39_ag(x0) U40_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: isGreater_in_ag(pred(Y)) -> isGreater_out_ag isGreater_in_ag(succ(Y)) -> U39_ag(isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(isGreater_in_ag(Y)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(=_in_aa) = 0 POL(=_in_ag(x_1)) = 2*x_1 POL(=_out_aa) = 0 POL(=_out_ag(x_1)) = 2*x_1 POL(MY_DIVIDE_IN_A) = 0 POL(U1_A(x_1)) = x_1 POL(U2_A(x_1)) = 2*x_1 POL(U39_ag(x_1)) = 2*x_1 POL(U3_A(x_1)) = x_1 POL(U40_ag(x_1)) = x_1 POL(isGreater_in_ag(x_1)) = 2*x_1 POL(isGreater_out_ag) = 0 POL(pred(x_1)) = 2*x_1 POL(succ(x_1)) = 2*x_1 POL(zero) = 0 ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag U40_ag(isGreater_out_ag) -> isGreater_out_ag U39_ag(isGreater_out_ag) -> isGreater_out_ag =_in_ag(X) -> =_out_ag(X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U39_ag(x0) U40_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) 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. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag =_in_ag(X) -> =_out_ag(X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U39_ag(x0) U40_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) 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]. U39_ag(x0) U40_ag(x0) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag =_in_ag(X) -> =_out_ag(X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) at position [0] we obtained the following new rules [LPAR04]: (U1_A(=_out_aa) -> U2_A(=_out_ag(zero)),U1_A(=_out_aa) -> U2_A(=_out_ag(zero))) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag =_in_ag(X) -> =_out_ag(X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (31) 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. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) 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]. =_in_ag(x0) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule MY_DIVIDE_IN_A -> U1_A(=_in_aa) at position [0] we obtained the following new rules [LPAR04]: (MY_DIVIDE_IN_A -> U1_A(=_out_aa),MY_DIVIDE_IN_A -> U1_A(=_out_aa)) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) 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]. =_in_aa ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (SOUND) By narrowing [LPAR04] the rule U2_A(=_out_ag(X2)) -> U3_A(isGreater_in_ag(X2)) at position [0] we obtained the following new rules [LPAR04]: (U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag),U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag)) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) 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. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag) R is empty. The set Q consists of the following terms: isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (45) 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]. isGreater_in_ag(x0) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag) R is empty. Q is empty. We have to consider all (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 = MY_DIVIDE_IN_A evaluates to t =MY_DIVIDE_IN_A Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence MY_DIVIDE_IN_A -> U1_A(=_out_aa) with rule MY_DIVIDE_IN_A -> U1_A(=_out_aa) at position [] and matcher [ ] U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) with rule U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) at position [] and matcher [ ] U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag) with rule U2_A(=_out_ag(zero)) -> U3_A(isGreater_out_ag) at position [] and matcher [ ] U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A with rule U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A 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: my_divide_in_1: (f) isGreater_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x1, x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (50) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x1, x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) ---------------------------------------- (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: MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) MY_DIVIDE_IN_A(X) -> =_IN_AA(X1, X) U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U1_A(X, =_out_aa(X1, X)) -> =_IN_AG(X2, zero) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> ISGREATER_IN_AG(X1, X2) ISGREATER_IN_AG(succ(X), succ(Y)) -> U39_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(pred(X), pred(Y)) -> U40_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) U3_A(X, isGreater_out_ag(X1, X2)) -> U4_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U5_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x1, x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) =_IN_AA(x1, x2) = =_IN_AA U2_A(x1, x2, x3) = U2_A(x3) =_IN_AG(x1, x2) = =_IN_AG(x2) U3_A(x1, x2) = U3_A(x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) U39_AG(x1, x2, x3) = U39_AG(x2, x3) U40_AG(x1, x2, x3) = U40_AG(x2, x3) U4_A(x1, x2) = U4_A(x2) U5_A(x1, x2) = U5_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) MY_DIVIDE_IN_A(X) -> =_IN_AA(X1, X) U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U1_A(X, =_out_aa(X1, X)) -> =_IN_AG(X2, zero) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> ISGREATER_IN_AG(X1, X2) ISGREATER_IN_AG(succ(X), succ(Y)) -> U39_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(pred(X), pred(Y)) -> U40_AG(X, Y, isGreater_in_ag(X, Y)) ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) U3_A(X, isGreater_out_ag(X1, X2)) -> U4_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U5_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x1, x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) =_IN_AA(x1, x2) = =_IN_AA U2_A(x1, x2, x3) = U2_A(x3) =_IN_AG(x1, x2) = =_IN_AG(x2) U3_A(x1, x2) = U3_A(x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) U39_AG(x1, x2, x3) = U39_AG(x2, x3) U40_AG(x1, x2, x3) = U40_AG(x2, x3) U4_A(x1, x2) = U4_A(x2) U5_A(x1, x2) = U5_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes. ---------------------------------------- (54) Complex Obligation (AND) ---------------------------------------- (55) Obligation: Pi DP problem: The TRS P consists of the following rules: ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x1, x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_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: ISGREATER_IN_AG(pred(X), pred(Y)) -> ISGREATER_IN_AG(X, Y) ISGREATER_IN_AG(succ(X), succ(Y)) -> ISGREATER_IN_AG(X, Y) R is empty. The argument filtering Pi contains the following mapping: pred(x1) = pred(x1) succ(x1) = succ(x1) ISGREATER_IN_AG(x1, x2) = ISGREATER_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: ISGREATER_IN_AG(pred(Y)) -> ISGREATER_IN_AG(Y) ISGREATER_IN_AG(succ(Y)) -> ISGREATER_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: *ISGREATER_IN_AG(pred(Y)) -> ISGREATER_IN_AG(Y) The graph contains the following edges 1 > 1 *ISGREATER_IN_AG(succ(Y)) -> ISGREATER_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: U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, =_in_aa(X1, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_a(X, =_out_aa(X1, X)) -> U2_a(X, X1, =_in_ag(X2, zero)) =_in_ag(X, X) -> =_out_ag(X, X) U2_a(X, X1, =_out_ag(X2, zero)) -> U3_a(X, isGreater_in_ag(X1, X2)) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U3_a(X, isGreater_out_ag(X1, X2)) -> U4_a(X, my_divide_in_a(//(X, succ(succ(zero))))) my_divide_in_a(X) -> U5_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U5_a(X, =_out_ga(zero, X)) -> my_divide_out_a(X) U4_a(X, my_divide_out_a(//(X, succ(succ(zero))))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa U2_a(x1, x2, x3) = U2_a(x3) =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero U3_a(x1, x2) = U3_a(x2) isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U5_a(x1, x2) = U5_a(x2) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x1, x2) my_divide_out_a(x1) = my_divide_out_a(x1) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2) = U3_A(x2) 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: U1_A(X, =_out_aa(X1, X)) -> U2_A(X, X1, =_in_ag(X2, zero)) U2_A(X, X1, =_out_ag(X2, zero)) -> U3_A(X, isGreater_in_ag(X1, X2)) U3_A(X, isGreater_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) MY_DIVIDE_IN_A(X) -> U1_A(X, =_in_aa(X1, X)) The TRS R consists of the following rules: =_in_ag(X, X) -> =_out_ag(X, X) isGreater_in_ag(succ(X), zero) -> isGreater_out_ag(succ(X), zero) isGreater_in_ag(succ(X), pred(Y)) -> isGreater_out_ag(succ(X), pred(Y)) isGreater_in_ag(succ(X), succ(Y)) -> U39_ag(X, Y, isGreater_in_ag(X, Y)) isGreater_in_ag(zero, pred(Y)) -> isGreater_out_ag(zero, pred(Y)) isGreater_in_ag(pred(X), pred(Y)) -> U40_ag(X, Y, isGreater_in_ag(X, Y)) =_in_aa(X, X) -> =_out_aa(X, X) U39_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U40_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) The argument filtering Pi contains the following mapping: =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa =_in_ag(x1, x2) = =_in_ag(x2) =_out_ag(x1, x2) = =_out_ag(x1, x2) zero = zero isGreater_in_ag(x1, x2) = isGreater_in_ag(x2) isGreater_out_ag(x1, x2) = isGreater_out_ag(x2) pred(x1) = pred(x1) succ(x1) = succ(x1) U39_ag(x1, x2, x3) = U39_ag(x2, x3) U40_ag(x1, x2, x3) = U40_ag(x2, x3) //(x1, x2) = //(x1, x2) MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2) = U3_A(x2) 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: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X, X) isGreater_in_ag(zero) -> isGreater_out_ag(zero) isGreater_in_ag(pred(Y)) -> isGreater_out_ag(pred(Y)) isGreater_in_ag(succ(Y)) -> U39_ag(Y, isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(Y, isGreater_in_ag(Y)) =_in_aa -> =_out_aa U39_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(succ(Y)) U40_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(pred(Y)) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U39_ag(x0, x1) U40_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (67) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: isGreater_in_ag(succ(Y)) -> U39_ag(Y, isGreater_in_ag(Y)) Used ordering: Polynomial interpretation [POLO]: POL(=_in_aa) = 0 POL(=_in_ag(x_1)) = 2*x_1 POL(=_out_aa) = 0 POL(=_out_ag(x_1, x_2)) = x_1 + x_2 POL(MY_DIVIDE_IN_A) = 0 POL(U1_A(x_1)) = x_1 POL(U2_A(x_1)) = 2*x_1 POL(U39_ag(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U3_A(x_1)) = x_1 POL(U40_ag(x_1, x_2)) = x_1 + x_2 POL(isGreater_in_ag(x_1)) = 2*x_1 POL(isGreater_out_ag(x_1)) = x_1 POL(pred(x_1)) = 2*x_1 POL(succ(x_1)) = 1 + 2*x_1 POL(zero) = 0 ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X, X) isGreater_in_ag(zero) -> isGreater_out_ag(zero) isGreater_in_ag(pred(Y)) -> isGreater_out_ag(pred(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(Y, isGreater_in_ag(Y)) =_in_aa -> =_out_aa U39_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(succ(Y)) U40_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(pred(Y)) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U39_ag(x0, x1) U40_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (69) 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. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) isGreater_in_ag(pred(Y)) -> isGreater_out_ag(pred(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(Y, isGreater_in_ag(Y)) U40_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(pred(Y)) =_in_ag(X) -> =_out_ag(X, X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U39_ag(x0, x1) U40_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (71) 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]. U39_ag(x0, x1) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) isGreater_in_ag(pred(Y)) -> isGreater_out_ag(pred(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(Y, isGreater_in_ag(Y)) U40_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(pred(Y)) =_in_ag(X) -> =_out_ag(X, X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U40_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (73) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: isGreater_in_ag(pred(Y)) -> isGreater_out_ag(pred(Y)) isGreater_in_ag(pred(Y)) -> U40_ag(Y, isGreater_in_ag(Y)) Used ordering: Polynomial interpretation [POLO]: POL(=_in_aa) = 0 POL(=_in_ag(x_1)) = 2*x_1 POL(=_out_aa) = 0 POL(=_out_ag(x_1, x_2)) = x_1 + x_2 POL(MY_DIVIDE_IN_A) = 0 POL(U1_A(x_1)) = 2*x_1 POL(U2_A(x_1)) = 2*x_1 POL(U3_A(x_1)) = x_1 POL(U40_ag(x_1, x_2)) = 2 + x_1 + x_2 POL(isGreater_in_ag(x_1)) = 2*x_1 POL(isGreater_out_ag(x_1)) = x_1 POL(pred(x_1)) = 2 + 2*x_1 POL(zero) = 0 ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) U40_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(pred(Y)) =_in_ag(X) -> =_out_ag(X, X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U40_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (75) 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. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) =_in_ag(X) -> =_out_ag(X, X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U40_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (77) 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]. U40_ag(x0, x1) ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) =_in_ag(X) -> =_out_ag(X, X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (79) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U1_A(=_out_aa) -> U2_A(=_in_ag(zero)) at position [0] we obtained the following new rules [LPAR04]: (U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)),U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero))) ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) =_in_ag(X) -> =_out_ag(X, X) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (81) 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. ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (83) 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]. =_in_ag(x0) ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (85) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule MY_DIVIDE_IN_A -> U1_A(=_in_aa) at position [0] we obtained the following new rules [LPAR04]: (MY_DIVIDE_IN_A -> U1_A(=_out_aa),MY_DIVIDE_IN_A -> U1_A(=_out_aa)) ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) The TRS R consists of the following rules: =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (87) 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. ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: isGreater_in_ag(x0) =_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (89) 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]. =_in_aa ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (91) TransformationProof (SOUND) By narrowing [LPAR04] the rule U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) at position [0] we obtained the following new rules [LPAR04]: (U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)),U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero))) ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (93) 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. ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) R is empty. The set Q consists of the following terms: isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (95) 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]. isGreater_in_ag(x0) ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (97) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A we obtained the following new rules [LPAR04]: (U3_A(isGreater_out_ag(zero)) -> MY_DIVIDE_IN_A,U3_A(isGreater_out_ag(zero)) -> MY_DIVIDE_IN_A) ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) MY_DIVIDE_IN_A -> U1_A(=_out_aa) U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) U3_A(isGreater_out_ag(zero)) -> MY_DIVIDE_IN_A R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (99) 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 = U2_A(=_out_ag(zero, zero)) evaluates to t =U2_A(=_out_ag(zero, zero)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) with rule U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) at position [] and matcher [ ] U3_A(isGreater_out_ag(zero)) -> MY_DIVIDE_IN_A with rule U3_A(isGreater_out_ag(zero)) -> MY_DIVIDE_IN_A at position [] and matcher [ ] MY_DIVIDE_IN_A -> U1_A(=_out_aa) with rule MY_DIVIDE_IN_A -> U1_A(=_out_aa) at position [] and matcher [ ] U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) with rule U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) 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. ---------------------------------------- (100) NO ---------------------------------------- (101) UndefinedPredicateHandlerProof (SOUND) Added facts for all undefined predicates [PROLOG]. ---------------------------------------- (102) Obligation: Clauses: my_divide(X) :- ','(>(X, 0), my_divide(//(X, 2))). my_divide(X) :- is(0, X). >(X0, X1). is(X0, X1). Query: my_divide(a) ---------------------------------------- (103) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_divide_in_1: (f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga my_divide_out_a(x1) = my_divide_out_a Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (104) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga my_divide_out_a(x1) = my_divide_out_a ---------------------------------------- (105) 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: MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) MY_DIVIDE_IN_A(X) -> >_IN_AG(X, 0) U1_A(X, >_out_ag(X, 0)) -> U2_A(X, my_divide_in_a(//(X, 2))) U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U3_A(X, is_in_ga(0, X)) MY_DIVIDE_IN_A(X) -> IS_IN_GA(0, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga my_divide_out_a(x1) = my_divide_out_a MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) >_IN_AG(x1, x2) = >_IN_AG(x2) U2_A(x1, x2) = U2_A(x2) U3_A(x1, x2) = U3_A(x2) IS_IN_GA(x1, x2) = IS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (106) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) MY_DIVIDE_IN_A(X) -> >_IN_AG(X, 0) U1_A(X, >_out_ag(X, 0)) -> U2_A(X, my_divide_in_a(//(X, 2))) U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U3_A(X, is_in_ga(0, X)) MY_DIVIDE_IN_A(X) -> IS_IN_GA(0, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga my_divide_out_a(x1) = my_divide_out_a MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) >_IN_AG(x1, x2) = >_IN_AG(x2) U2_A(x1, x2) = U2_A(x2) U3_A(x1, x2) = U3_A(x2) IS_IN_GA(x1, x2) = IS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (107) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (108) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga my_divide_out_a(x1) = my_divide_out_a MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (109) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (110) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) The TRS R consists of the following rules: >_in_ag(X0, X1) -> >_out_ag(X0, X1) The argument filtering Pi contains the following mapping: >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag 0 = 0 MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (111) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (112) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_in_ag(0)) The TRS R consists of the following rules: >_in_ag(X1) -> >_out_ag The set Q consists of the following terms: >_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (113) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule MY_DIVIDE_IN_A -> U1_A(>_in_ag(0)) at position [0] we obtained the following new rules [LPAR04]: (MY_DIVIDE_IN_A -> U1_A(>_out_ag),MY_DIVIDE_IN_A -> U1_A(>_out_ag)) ---------------------------------------- (114) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_out_ag) The TRS R consists of the following rules: >_in_ag(X1) -> >_out_ag The set Q consists of the following terms: >_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (115) 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. ---------------------------------------- (116) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_out_ag) R is empty. The set Q consists of the following terms: >_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (117) 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]. >_in_ag(x0) ---------------------------------------- (118) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_out_ag) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (119) 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 = MY_DIVIDE_IN_A evaluates to t =MY_DIVIDE_IN_A Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence MY_DIVIDE_IN_A -> U1_A(>_out_ag) with rule MY_DIVIDE_IN_A -> U1_A(>_out_ag) at position [] and matcher [ ] U1_A(>_out_ag) -> MY_DIVIDE_IN_A with rule U1_A(>_out_ag) -> MY_DIVIDE_IN_A 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. ---------------------------------------- (120) NO ---------------------------------------- (121) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_divide_in_1: (f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag(x2) 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga(x1) my_divide_out_a(x1) = my_divide_out_a Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (122) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag(x2) 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga(x1) my_divide_out_a(x1) = my_divide_out_a ---------------------------------------- (123) 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: MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) MY_DIVIDE_IN_A(X) -> >_IN_AG(X, 0) U1_A(X, >_out_ag(X, 0)) -> U2_A(X, my_divide_in_a(//(X, 2))) U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U3_A(X, is_in_ga(0, X)) MY_DIVIDE_IN_A(X) -> IS_IN_GA(0, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag(x2) 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga(x1) my_divide_out_a(x1) = my_divide_out_a MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) >_IN_AG(x1, x2) = >_IN_AG(x2) U2_A(x1, x2) = U2_A(x2) U3_A(x1, x2) = U3_A(x2) IS_IN_GA(x1, x2) = IS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (124) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) MY_DIVIDE_IN_A(X) -> >_IN_AG(X, 0) U1_A(X, >_out_ag(X, 0)) -> U2_A(X, my_divide_in_a(//(X, 2))) U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U3_A(X, is_in_ga(0, X)) MY_DIVIDE_IN_A(X) -> IS_IN_GA(0, X) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag(x2) 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga(x1) my_divide_out_a(x1) = my_divide_out_a MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) >_IN_AG(x1, x2) = >_IN_AG(x2) U2_A(x1, x2) = U2_A(x2) U3_A(x1, x2) = U3_A(x2) IS_IN_GA(x1, x2) = IS_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (125) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (126) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) The TRS R consists of the following rules: my_divide_in_a(X) -> U1_a(X, >_in_ag(X, 0)) >_in_ag(X0, X1) -> >_out_ag(X0, X1) U1_a(X, >_out_ag(X, 0)) -> U2_a(X, my_divide_in_a(//(X, 2))) my_divide_in_a(X) -> U3_a(X, is_in_ga(0, X)) is_in_ga(X0, X1) -> is_out_ga(X0, X1) U3_a(X, is_out_ga(0, X)) -> my_divide_out_a(X) U2_a(X, my_divide_out_a(//(X, 2))) -> my_divide_out_a(X) The argument filtering Pi contains the following mapping: my_divide_in_a(x1) = my_divide_in_a U1_a(x1, x2) = U1_a(x2) >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag(x2) 0 = 0 U2_a(x1, x2) = U2_a(x2) U3_a(x1, x2) = U3_a(x2) is_in_ga(x1, x2) = is_in_ga(x1) is_out_ga(x1, x2) = is_out_ga(x1) my_divide_out_a(x1) = my_divide_out_a MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (127) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (128) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_A(X, >_out_ag(X, 0)) -> MY_DIVIDE_IN_A(//(X, 2)) MY_DIVIDE_IN_A(X) -> U1_A(X, >_in_ag(X, 0)) The TRS R consists of the following rules: >_in_ag(X0, X1) -> >_out_ag(X0, X1) The argument filtering Pi contains the following mapping: >_in_ag(x1, x2) = >_in_ag(x2) >_out_ag(x1, x2) = >_out_ag(x2) 0 = 0 MY_DIVIDE_IN_A(x1) = MY_DIVIDE_IN_A U1_A(x1, x2) = U1_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (129) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (130) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag(0)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_in_ag(0)) The TRS R consists of the following rules: >_in_ag(X1) -> >_out_ag(X1) The set Q consists of the following terms: >_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (131) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule MY_DIVIDE_IN_A -> U1_A(>_in_ag(0)) at position [0] we obtained the following new rules [LPAR04]: (MY_DIVIDE_IN_A -> U1_A(>_out_ag(0)),MY_DIVIDE_IN_A -> U1_A(>_out_ag(0))) ---------------------------------------- (132) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag(0)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_out_ag(0)) The TRS R consists of the following rules: >_in_ag(X1) -> >_out_ag(X1) The set Q consists of the following terms: >_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (133) 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. ---------------------------------------- (134) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag(0)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_out_ag(0)) R is empty. The set Q consists of the following terms: >_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (135) 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]. >_in_ag(x0) ---------------------------------------- (136) Obligation: Q DP problem: The TRS P consists of the following rules: U1_A(>_out_ag(0)) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(>_out_ag(0)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (137) 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 = MY_DIVIDE_IN_A evaluates to t =MY_DIVIDE_IN_A Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence MY_DIVIDE_IN_A -> U1_A(>_out_ag(0)) with rule MY_DIVIDE_IN_A -> U1_A(>_out_ag(0)) at position [] and matcher [ ] U1_A(>_out_ag(0)) -> MY_DIVIDE_IN_A with rule U1_A(>_out_ag(0)) -> MY_DIVIDE_IN_A 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. ---------------------------------------- (138) NO