/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/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) OrTransformerProof [EQUIVALENT, 0 ms] (6) Prolog (7) PrologToPiTRSProof [SOUND, 13 ms] (8) PiTRS (9) DependencyPairsProof [EQUIVALENT, 0 ms] (10) PiDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) AND (13) PiDP (14) UsableRulesProof [EQUIVALENT, 0 ms] (15) PiDP (16) PiDPToQDPProof [SOUND, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) PiDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) PiDP (23) PiDPToQDPProof [SOUND, 0 ms] (24) QDP (25) MRRProof [EQUIVALENT, 37 ms] (26) QDP (27) UsableRulesReductionPairsProof [EQUIVALENT, 17 ms] (28) QDP (29) QReductionProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) QDP (37) QReductionProof [EQUIVALENT, 0 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) QReductionProof [EQUIVALENT, 0 ms] (44) QDP (45) TransformationProof [SOUND, 0 ms] (46) QDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) QDP (49) QReductionProof [EQUIVALENT, 0 ms] (50) QDP (51) TransformationProof [EQUIVALENT, 0 ms] (52) QDP (53) TransformationProof [EQUIVALENT, 0 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 0 ms] (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) NonTerminationLoopProof [COMPLETE, 0 ms] (60) NO (61) PrologToPiTRSProof [SOUND, 4 ms] (62) PiTRS (63) DependencyPairsProof [EQUIVALENT, 0 ms] (64) PiDP (65) DependencyGraphProof [EQUIVALENT, 0 ms] (66) AND (67) PiDP (68) UsableRulesProof [EQUIVALENT, 0 ms] (69) PiDP (70) PiDPToQDPProof [SOUND, 0 ms] (71) QDP (72) QDPSizeChangeProof [EQUIVALENT, 0 ms] (73) YES (74) PiDP (75) UsableRulesProof [EQUIVALENT, 0 ms] (76) PiDP (77) PiDPToQDPProof [SOUND, 0 ms] (78) QDP (79) UsableRulesReductionPairsProof [EQUIVALENT, 30 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) TransformationProof [EQUIVALENT, 0 ms] (88) QDP (89) UsableRulesProof [EQUIVALENT, 0 ms] (90) QDP (91) QReductionProof [EQUIVALENT, 0 ms] (92) QDP (93) TransformationProof [EQUIVALENT, 0 ms] (94) QDP (95) UsableRulesProof [EQUIVALENT, 0 ms] (96) QDP (97) QReductionProof [EQUIVALENT, 0 ms] (98) QDP (99) TransformationProof [SOUND, 0 ms] (100) QDP (101) UsableRulesProof [EQUIVALENT, 0 ms] (102) QDP (103) QReductionProof [EQUIVALENT, 0 ms] (104) QDP (105) TransformationProof [EQUIVALENT, 0 ms] (106) QDP (107) TransformationProof [EQUIVALENT, 0 ms] (108) QDP (109) NonTerminationLoopProof [COMPLETE, 0 ms] (110) NO (111) UndefinedPredicateHandlerProof [SOUND, 0 ms] (112) Prolog (113) PrologToPiTRSProof [SOUND, 0 ms] (114) PiTRS (115) DependencyPairsProof [EQUIVALENT, 1 ms] (116) PiDP (117) DependencyGraphProof [EQUIVALENT, 0 ms] (118) PiDP (119) UsableRulesProof [EQUIVALENT, 0 ms] (120) PiDP (121) PiDPToQDPProof [SOUND, 0 ms] (122) QDP (123) TransformationProof [EQUIVALENT, 0 ms] (124) QDP (125) UsableRulesProof [EQUIVALENT, 0 ms] (126) QDP (127) QReductionProof [EQUIVALENT, 0 ms] (128) QDP (129) NonTerminationLoopProof [COMPLETE, 0 ms] (130) NO (131) PrologToPiTRSProof [SOUND, 0 ms] (132) PiTRS (133) DependencyPairsProof [EQUIVALENT, 1 ms] (134) PiDP (135) DependencyGraphProof [EQUIVALENT, 0 ms] (136) PiDP (137) UsableRulesProof [EQUIVALENT, 0 ms] (138) PiDP (139) PiDPToQDPProof [SOUND, 0 ms] (140) QDP (141) TransformationProof [EQUIVALENT, 0 ms] (142) QDP (143) UsableRulesProof [EQUIVALENT, 0 ms] (144) QDP (145) QReductionProof [EQUIVALENT, 0 ms] (146) QDP (147) NonTerminationLoopProof [COMPLETE, 0 ms] (148) 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), =(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), =(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) OrTransformerProof (EQUIVALENT) Transformed all or-constructs[PROLOG]. ---------------------------------------- (6) Obligation: Clauses: my_divide(X) :- ','(=(X1, X), ','(=(X2, zero), ','(isGreater(X1, X2), my_divide(//(X, succ(succ(zero))))))). my_divide(X) :- ','(=(X1, X), ','(=(X2, zero), ','(=(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) ---------------------------------------- (7) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (8) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(x2) ---------------------------------------- (9) 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)) -> U41_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)) -> U42_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) -> U7_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> =_IN_AG(X1, X2) U5_A(X, =_out_ag(X1, X2)) -> U6_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(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) U41_AG(x1, x2, x3) = U41_AG(x2, x3) U42_AG(x1, x2, x3) = U42_AG(x2, x3) U4_A(x1, x2) = U4_A(x2) U7_A(x1, x2) = U7_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) U5_A(x1, x2) = U5_A(x2) U6_A(x1, x2) = U6_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) 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)) -> U41_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)) -> U42_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) -> U7_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> =_IN_AG(X1, X2) U5_A(X, =_out_ag(X1, X2)) -> U6_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(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) U41_AG(x1, x2, x3) = U41_AG(x2, x3) U42_AG(x1, x2, x3) = U42_AG(x2, x3) U4_A(x1, x2) = U4_A(x2) U7_A(x1, x2) = U7_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) U5_A(x1, x2) = U5_A(x2) U6_A(x1, x2) = U6_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 10 less nodes. ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (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) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (14) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (15) 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 ---------------------------------------- (16) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (17) 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. ---------------------------------------- (18) 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 ---------------------------------------- (19) YES ---------------------------------------- (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)) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_ag(x2, x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(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) U5_A(x1, x2) = U5_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (22) 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)) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) =_in_aa(X, X) -> =_out_aa(X, X) U41_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U42_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) U41_ag(x1, x2, x3) = U41_ag(x2, x3) U42_ag(x1, x2, x3) = U42_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) U5_A(x1, x2) = U5_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (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, 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) U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, X2)) -> MY_DIVIDE_IN_A 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)) -> U41_ag(Y, isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U42_ag(Y, isGreater_in_ag(Y)) =_in_aa -> =_out_aa U41_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(succ(Y)) U42_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 U41_ag(x0, x1) U42_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) 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)) U41_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(succ(Y)) U42_ag(Y, isGreater_out_ag(Y)) -> isGreater_out_ag(pred(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(U3_A(x_1)) = x_1 POL(U41_ag(x_1, x_2)) = 2 + x_1 + x_2 POL(U42_ag(x_1, x_2)) = 2 + x_1 + x_2 POL(U5_A(x_1)) = x_1 POL(isGreater_in_ag(x_1)) = 2*x_1 POL(isGreater_out_ag(x_1)) = x_1 POL(pred(x_1)) = 1 + 2*x_1 POL(succ(x_1)) = 1 + 2*x_1 POL(zero) = 0 ---------------------------------------- (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, 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) U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, X2)) -> MY_DIVIDE_IN_A 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(succ(Y)) -> U41_ag(Y, isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U42_ag(Y, isGreater_in_ag(Y)) =_in_aa -> =_out_aa The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U41_ag(x0, x1) U42_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) 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(succ(Y)) -> U41_ag(Y, isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U42_ag(Y, 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, 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(U3_A(x_1)) = x_1 POL(U41_ag(x_1, x_2)) = x_1 + x_2 POL(U42_ag(x_1, x_2)) = x_1 + x_2 POL(U5_A(x_1)) = x_1 POL(isGreater_in_ag(x_1)) = x_1 POL(isGreater_out_ag(x_1)) = 2*x_1 POL(pred(x_1)) = 2*x_1 POL(succ(x_1)) = 2*x_1 POL(zero) = 0 ---------------------------------------- (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, 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) U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, X2)) -> MY_DIVIDE_IN_A The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X, X) =_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 U41_ag(x0, x1) U42_ag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (29) 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]. U41_ag(x0, x1) U42_ag(x0, x1) ---------------------------------------- (30) 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) U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, X2)) -> MY_DIVIDE_IN_A The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X, X) =_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. ---------------------------------------- (31) 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))) ---------------------------------------- (32) 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) U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, X2)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero, zero)) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X, X) =_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. ---------------------------------------- (33) 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)) ---------------------------------------- (34) 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 U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, 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_ag(X) -> =_out_ag(X, X) =_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. ---------------------------------------- (35) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U2_A(=_out_ag(X2, zero)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, 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_ag(X) -> =_out_ag(X, X) 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. ---------------------------------------- (37) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. =_in_aa ---------------------------------------- (38) 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 U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1, 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_ag(X) -> =_out_ag(X, X) isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2_A(=_out_ag(X2, zero)) -> U5_A(=_in_ag(X2)) at position [0] we obtained the following new rules [LPAR04]: (U2_A(=_out_ag(X2, zero)) -> U5_A(=_out_ag(X2, X2)),U2_A(=_out_ag(X2, zero)) -> U5_A(=_out_ag(X2, X2))) ---------------------------------------- (40) 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 U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X, X) isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (41) 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. ---------------------------------------- (42) 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 U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag(zero) The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) 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) ---------------------------------------- (44) 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 U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) 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. ---------------------------------------- (45) 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))) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) 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. ---------------------------------------- (47) 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. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) 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. ---------------------------------------- (49) 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) ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag(X2)) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) 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. ---------------------------------------- (51) 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) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: U5_A(=_out_ag(X1, 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) 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. ---------------------------------------- (53) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U5_A(=_out_ag(X1, X2)) -> MY_DIVIDE_IN_A we obtained the following new rules [LPAR04]: (U5_A(=_out_ag(z0, z0)) -> MY_DIVIDE_IN_A,U5_A(=_out_ag(z0, z0)) -> MY_DIVIDE_IN_A) ---------------------------------------- (54) 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(X2, zero)) -> U5_A(=_out_ag(X2, X2)) U2_A(=_out_ag(zero, zero)) -> U3_A(isGreater_out_ag(zero)) U3_A(isGreater_out_ag(zero)) -> MY_DIVIDE_IN_A U5_A(=_out_ag(z0, z0)) -> MY_DIVIDE_IN_A R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (55) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U2_A(=_out_ag(X2, zero)) -> U5_A(=_out_ag(X2, X2)) we obtained the following new rules [LPAR04]: (U2_A(=_out_ag(zero, zero)) -> U5_A(=_out_ag(zero, zero)),U2_A(=_out_ag(zero, zero)) -> U5_A(=_out_ag(zero, zero))) ---------------------------------------- (56) 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 U5_A(=_out_ag(z0, z0)) -> MY_DIVIDE_IN_A U2_A(=_out_ag(zero, zero)) -> U5_A(=_out_ag(zero, zero)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U5_A(=_out_ag(z0, z0)) -> MY_DIVIDE_IN_A we obtained the following new rules [LPAR04]: (U5_A(=_out_ag(zero, zero)) -> MY_DIVIDE_IN_A,U5_A(=_out_ag(zero, zero)) -> MY_DIVIDE_IN_A) ---------------------------------------- (58) 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 U2_A(=_out_ag(zero, zero)) -> U5_A(=_out_ag(zero, zero)) U5_A(=_out_ag(zero, zero)) -> MY_DIVIDE_IN_A R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (59) 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. ---------------------------------------- (60) NO ---------------------------------------- (61) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_ag(x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (62) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_ag(x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(x2) ---------------------------------------- (63) 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)) -> U41_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)) -> U42_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) -> U7_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> =_IN_AG(X1, X2) U5_A(X, =_out_ag(X1, X2)) -> U6_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_ag(x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(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) U41_AG(x1, x2, x3) = U41_AG(x3) U42_AG(x1, x2, x3) = U42_AG(x3) U4_A(x1, x2) = U4_A(x2) U7_A(x1, x2) = U7_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) U5_A(x1, x2) = U5_A(x2) U6_A(x1, x2) = U6_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (64) 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)) -> U41_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)) -> U42_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) -> U7_A(X, =_in_ga(zero, X)) MY_DIVIDE_IN_A(X) -> =_IN_GA(zero, X) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U2_A(X, X1, =_out_ag(X2, zero)) -> =_IN_AG(X1, X2) U5_A(X, =_out_ag(X1, X2)) -> U6_A(X, my_divide_in_a(//(X, succ(succ(zero))))) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_ag(x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(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) U41_AG(x1, x2, x3) = U41_AG(x3) U42_AG(x1, x2, x3) = U42_AG(x3) U4_A(x1, x2) = U4_A(x2) U7_A(x1, x2) = U7_A(x2) =_IN_GA(x1, x2) = =_IN_GA(x1) U5_A(x1, x2) = U5_A(x2) U6_A(x1, x2) = U6_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (65) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 10 less nodes. ---------------------------------------- (66) Complex Obligation (AND) ---------------------------------------- (67) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_ag(x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(x2) ISGREATER_IN_AG(x1, x2) = ISGREATER_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (68) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (69) 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 ---------------------------------------- (70) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (71) 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. ---------------------------------------- (72) 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 ---------------------------------------- (73) YES ---------------------------------------- (74) 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)) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) U42_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(pred(X), pred(Y)) U41_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) -> U7_a(X, =_in_ga(zero, X)) =_in_ga(X, X) -> =_out_ga(X, X) U7_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) U2_a(X, X1, =_out_ag(X2, zero)) -> U5_a(X, =_in_ag(X1, X2)) U5_a(X, =_out_ag(X1, X2)) -> U6_a(X, my_divide_in_a(//(X, succ(succ(zero))))) U6_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_ag(x3) U4_a(x1, x2) = U4_a(x2) U7_a(x1, x2) = U7_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) U5_a(x1, x2) = U5_a(x2) U6_a(x1, x2) = U6_a(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) U5_A(x1, x2) = U5_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (75) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (76) 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)) U2_A(X, X1, =_out_ag(X2, zero)) -> U5_A(X, =_in_ag(X1, X2)) U5_A(X, =_out_ag(X1, X2)) -> MY_DIVIDE_IN_A(//(X, succ(succ(zero)))) 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)) -> U41_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)) -> U42_ag(X, Y, isGreater_in_ag(X, Y)) =_in_aa(X, X) -> =_out_aa(X, X) U41_ag(X, Y, isGreater_out_ag(X, Y)) -> isGreater_out_ag(succ(X), succ(Y)) U42_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) U41_ag(x1, x2, x3) = U41_ag(x3) U42_ag(x1, x2, x3) = U42_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) U5_A(x1, x2) = U5_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (77) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (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)) -> U3_A(isGreater_in_ag(X2)) U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A MY_DIVIDE_IN_A -> U1_A(=_in_aa) U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> MY_DIVIDE_IN_A 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)) -> U41_ag(isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U42_ag(isGreater_in_ag(Y)) =_in_aa -> =_out_aa U41_ag(isGreater_out_ag) -> isGreater_out_ag U42_ag(isGreater_out_ag) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U41_ag(x0) U42_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (79) 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)) -> U41_ag(isGreater_in_ag(Y)) isGreater_in_ag(pred(Y)) -> U42_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(U3_A(x_1)) = x_1 POL(U41_ag(x_1)) = x_1 POL(U42_ag(x_1)) = 2*x_1 POL(U5_A(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 ---------------------------------------- (80) 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) U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> MY_DIVIDE_IN_A The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X) =_in_aa -> =_out_aa isGreater_in_ag(zero) -> isGreater_out_ag U42_ag(isGreater_out_ag) -> isGreater_out_ag U41_ag(isGreater_out_ag) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) =_in_aa U41_ag(x0) U42_ag(x0) 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: 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) U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> MY_DIVIDE_IN_A The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X) =_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 U41_ag(x0) U42_ag(x0) 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]. U41_ag(x0) U42_ag(x0) ---------------------------------------- (84) 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) U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> MY_DIVIDE_IN_A The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X) =_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. ---------------------------------------- (85) 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))) ---------------------------------------- (86) 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) U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> MY_DIVIDE_IN_A U1_A(=_out_aa) -> U2_A(=_out_ag(zero)) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X) =_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. ---------------------------------------- (87) 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)) ---------------------------------------- (88) 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 U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> 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_ag(X) -> =_out_ag(X) =_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. ---------------------------------------- (89) 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. ---------------------------------------- (90) 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 U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> 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_ag(X) -> =_out_ag(X) 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. ---------------------------------------- (91) 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 ---------------------------------------- (92) 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 U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) U5_A(=_out_ag(X1)) -> 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_ag(X) -> =_out_ag(X) isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (93) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2_A(=_out_ag(X2)) -> U5_A(=_in_ag(X2)) at position [0] we obtained the following new rules [LPAR04]: (U2_A(=_out_ag(X2)) -> U5_A(=_out_ag(X2)),U2_A(=_out_ag(X2)) -> U5_A(=_out_ag(X2))) ---------------------------------------- (94) 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 U5_A(=_out_ag(X1)) -> 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(X2)) -> U5_A(=_out_ag(X2)) The TRS R consists of the following rules: =_in_ag(X) -> =_out_ag(X) isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (95) 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. ---------------------------------------- (96) 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 U5_A(=_out_ag(X1)) -> 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(X2)) -> U5_A(=_out_ag(X2)) The TRS R consists of the following rules: isGreater_in_ag(zero) -> isGreater_out_ag The set Q consists of the following terms: =_in_ag(x0) isGreater_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (97) 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) ---------------------------------------- (98) 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 U5_A(=_out_ag(X1)) -> 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(X2)) -> U5_A(=_out_ag(X2)) 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. ---------------------------------------- (99) 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)) ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1)) -> 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(X2)) -> U5_A(=_out_ag(X2)) 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. ---------------------------------------- (101) 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. ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1)) -> 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(X2)) -> U5_A(=_out_ag(X2)) 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. ---------------------------------------- (103) 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) ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1)) -> 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(X2)) -> U5_A(=_out_ag(X2)) 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. ---------------------------------------- (105) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U2_A(=_out_ag(X2)) -> U5_A(=_out_ag(X2)) we obtained the following new rules [LPAR04]: (U2_A(=_out_ag(zero)) -> U5_A(=_out_ag(zero)),U2_A(=_out_ag(zero)) -> U5_A(=_out_ag(zero))) ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: U3_A(isGreater_out_ag) -> MY_DIVIDE_IN_A U5_A(=_out_ag(X1)) -> 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) U2_A(=_out_ag(zero)) -> U5_A(=_out_ag(zero)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (107) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U5_A(=_out_ag(X1)) -> MY_DIVIDE_IN_A we obtained the following new rules [LPAR04]: (U5_A(=_out_ag(zero)) -> MY_DIVIDE_IN_A,U5_A(=_out_ag(zero)) -> MY_DIVIDE_IN_A) ---------------------------------------- (108) 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) U2_A(=_out_ag(zero)) -> U5_A(=_out_ag(zero)) U5_A(=_out_ag(zero)) -> MY_DIVIDE_IN_A R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (109) 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. ---------------------------------------- (110) NO ---------------------------------------- (111) UndefinedPredicateHandlerProof (SOUND) Added facts for all undefined predicates [PROLOG]. ---------------------------------------- (112) 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) ---------------------------------------- (113) 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 ---------------------------------------- (114) 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 ---------------------------------------- (115) 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 ---------------------------------------- (116) 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 ---------------------------------------- (117) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (118) 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 ---------------------------------------- (119) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (120) 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 ---------------------------------------- (121) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (122) 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. ---------------------------------------- (123) 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)) ---------------------------------------- (124) 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. ---------------------------------------- (125) 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. ---------------------------------------- (126) 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. ---------------------------------------- (127) 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) ---------------------------------------- (128) 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. ---------------------------------------- (129) 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. ---------------------------------------- (130) NO ---------------------------------------- (131) 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 ---------------------------------------- (132) 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 ---------------------------------------- (133) 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 ---------------------------------------- (134) 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 ---------------------------------------- (135) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (136) 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 ---------------------------------------- (137) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (138) 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 ---------------------------------------- (139) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (140) 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. ---------------------------------------- (141) 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))) ---------------------------------------- (142) 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. ---------------------------------------- (143) 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. ---------------------------------------- (144) 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. ---------------------------------------- (145) 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) ---------------------------------------- (146) 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. ---------------------------------------- (147) 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. ---------------------------------------- (148) NO