/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern myis(a,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 27 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 26 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) PiDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) PiDP (31) PiDPToQDPProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) PiDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) PiDP (38) PiDPToQDPProof [SOUND, 0 ms] (39) QDP (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] (41) YES ---------------------------------------- (0) Obligation: Clauses: myis(Z, X) :- evaluate(X, Z). evaluate(+(X, Y), Z) :- ','(evaluate(X, X1), ','(evaluate(Y, Y1), add(X1, Y1, Z))). evaluate(-(X, Y), Z) :- ','(evaluate(X, X1), ','(evaluate(Y, Y1), sub(X1, Y1, Z))). evaluate(*(X, Y), Z) :- ','(evaluate(X, X1), ','(evaluate(Y, Y1), mult(X1, Y1, Z))). evaluate(X, X) :- myinteger(X). myinteger(s(X)) :- myinteger(X). myinteger(0). add(s(X), Y, s(Z)) :- add(X, Y, Z). add(0, X, X). sub(s(X), s(Y), Z) :- sub(X, Y, Z). sub(X, 0, X). mult(s(X), Y, R) :- ','(mult(X, Y, Z), add(Y, Z, R)). mult(0, Y, 0). notEq(s(X), s(Y)) :- notEq(X, Y). notEq(s(X), 0). notEq(0, s(X)). lt(s(X), s(Y)) :- lt(X, Y). lt(0, s(Y)). gt(s(X), s(Y)) :- gt(X, Y). gt(s(X), 0). le(s(X), s(Y)) :- le(X, Y). le(0, s(Y)). le(0, 0). Query: myis(a,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: myis_in_2: (f,b) evaluate_in_2: (b,f) myinteger_in_1: (b) mult_in_3: (b,b,f) add_in_3: (b,b,f) sub_in_3: (b,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: MYIS_IN_AG(Z, X) -> U1_AG(Z, X, evaluate_in_ga(X, Z)) MYIS_IN_AG(Z, X) -> EVALUATE_IN_GA(X, Z) EVALUATE_IN_GA(+(X, Y), Z) -> U2_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(+(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(-(X, Y), Z) -> U5_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(-(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(*(X, Y), Z) -> U8_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(*(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(X, X) -> U11_GA(X, myinteger_in_g(X)) EVALUATE_IN_GA(X, X) -> MYINTEGER_IN_G(X) MYINTEGER_IN_G(s(X)) -> U12_G(X, myinteger_in_g(X)) MYINTEGER_IN_G(s(X)) -> MYINTEGER_IN_G(X) U8_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_GA(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U8_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) U9_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_GA(X, Y, Z, mult_in_gga(X1, Y1, Z)) U9_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> MULT_IN_GGA(X1, Y1, Z) MULT_IN_GGA(s(X), Y, R) -> U15_GGA(X, Y, R, mult_in_gga(X, Y, Z)) MULT_IN_GGA(s(X), Y, R) -> MULT_IN_GGA(X, Y, Z) U15_GGA(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_GGA(X, Y, R, add_in_gga(Y, Z, R)) U15_GGA(X, Y, R, mult_out_gga(X, Y, Z)) -> ADD_IN_GGA(Y, Z, R) ADD_IN_GGA(s(X), Y, s(Z)) -> U13_GGA(X, Y, Z, add_in_gga(X, Y, Z)) ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) U5_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_GA(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U5_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) U6_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_GA(X, Y, Z, sub_in_gga(X1, Y1, Z)) U6_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> SUB_IN_GGA(X1, Y1, Z) SUB_IN_GGA(s(X), s(Y), Z) -> U14_GGA(X, Y, Z, sub_in_gga(X, Y, Z)) SUB_IN_GGA(s(X), s(Y), Z) -> SUB_IN_GGA(X, Y, Z) U2_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_GA(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U2_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) U3_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_GA(X, Y, Z, add_in_gga(X1, Y1, Z)) U3_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> ADD_IN_GGA(X1, Y1, Z) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) MYIS_IN_AG(x1, x2) = MYIS_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x3) EVALUATE_IN_GA(x1, x2) = EVALUATE_IN_GA(x1) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) U8_GA(x1, x2, x3, x4) = U8_GA(x2, x4) U11_GA(x1, x2) = U11_GA(x1, x2) MYINTEGER_IN_G(x1) = MYINTEGER_IN_G(x1) U12_G(x1, x2) = U12_G(x2) U9_GA(x1, x2, x3, x4, x5) = U9_GA(x4, x5) U10_GA(x1, x2, x3, x4) = U10_GA(x4) MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) U15_GGA(x1, x2, x3, x4) = U15_GGA(x2, x4) U16_GGA(x1, x2, x3, x4) = U16_GGA(x4) ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) U13_GGA(x1, x2, x3, x4) = U13_GGA(x4) U6_GA(x1, x2, x3, x4, x5) = U6_GA(x4, x5) U7_GA(x1, x2, x3, x4) = U7_GA(x4) SUB_IN_GGA(x1, x2, x3) = SUB_IN_GGA(x1, x2) U14_GGA(x1, x2, x3, x4) = U14_GGA(x4) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x4, x5) U4_GA(x1, x2, x3, x4) = U4_GA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: MYIS_IN_AG(Z, X) -> U1_AG(Z, X, evaluate_in_ga(X, Z)) MYIS_IN_AG(Z, X) -> EVALUATE_IN_GA(X, Z) EVALUATE_IN_GA(+(X, Y), Z) -> U2_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(+(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(-(X, Y), Z) -> U5_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(-(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(*(X, Y), Z) -> U8_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(*(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(X, X) -> U11_GA(X, myinteger_in_g(X)) EVALUATE_IN_GA(X, X) -> MYINTEGER_IN_G(X) MYINTEGER_IN_G(s(X)) -> U12_G(X, myinteger_in_g(X)) MYINTEGER_IN_G(s(X)) -> MYINTEGER_IN_G(X) U8_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_GA(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U8_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) U9_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_GA(X, Y, Z, mult_in_gga(X1, Y1, Z)) U9_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> MULT_IN_GGA(X1, Y1, Z) MULT_IN_GGA(s(X), Y, R) -> U15_GGA(X, Y, R, mult_in_gga(X, Y, Z)) MULT_IN_GGA(s(X), Y, R) -> MULT_IN_GGA(X, Y, Z) U15_GGA(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_GGA(X, Y, R, add_in_gga(Y, Z, R)) U15_GGA(X, Y, R, mult_out_gga(X, Y, Z)) -> ADD_IN_GGA(Y, Z, R) ADD_IN_GGA(s(X), Y, s(Z)) -> U13_GGA(X, Y, Z, add_in_gga(X, Y, Z)) ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) U5_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_GA(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U5_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) U6_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_GA(X, Y, Z, sub_in_gga(X1, Y1, Z)) U6_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> SUB_IN_GGA(X1, Y1, Z) SUB_IN_GGA(s(X), s(Y), Z) -> U14_GGA(X, Y, Z, sub_in_gga(X, Y, Z)) SUB_IN_GGA(s(X), s(Y), Z) -> SUB_IN_GGA(X, Y, Z) U2_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_GA(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U2_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) U3_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_GA(X, Y, Z, add_in_gga(X1, Y1, Z)) U3_GA(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> ADD_IN_GGA(X1, Y1, Z) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) MYIS_IN_AG(x1, x2) = MYIS_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x3) EVALUATE_IN_GA(x1, x2) = EVALUATE_IN_GA(x1) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) U8_GA(x1, x2, x3, x4) = U8_GA(x2, x4) U11_GA(x1, x2) = U11_GA(x1, x2) MYINTEGER_IN_G(x1) = MYINTEGER_IN_G(x1) U12_G(x1, x2) = U12_G(x2) U9_GA(x1, x2, x3, x4, x5) = U9_GA(x4, x5) U10_GA(x1, x2, x3, x4) = U10_GA(x4) MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) U15_GGA(x1, x2, x3, x4) = U15_GGA(x2, x4) U16_GGA(x1, x2, x3, x4) = U16_GGA(x4) ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) U13_GGA(x1, x2, x3, x4) = U13_GGA(x4) U6_GA(x1, x2, x3, x4, x5) = U6_GA(x4, x5) U7_GA(x1, x2, x3, x4) = U7_GA(x4) SUB_IN_GGA(x1, x2, x3) = SUB_IN_GGA(x1, x2) U14_GGA(x1, x2, x3, x4) = U14_GGA(x4) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x4, x5) U4_GA(x1, x2, x3, x4) = U4_GA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 19 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: SUB_IN_GGA(s(X), s(Y), Z) -> SUB_IN_GGA(X, Y, Z) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) SUB_IN_GGA(x1, x2, x3) = SUB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: SUB_IN_GGA(s(X), s(Y), Z) -> SUB_IN_GGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) SUB_IN_GGA(x1, x2, x3) = SUB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: SUB_IN_GGA(s(X), s(Y)) -> SUB_IN_GGA(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *SUB_IN_GGA(s(X), s(Y)) -> SUB_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: ADD_IN_GGA(s(X), Y) -> ADD_IN_GGA(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ADD_IN_GGA(s(X), Y) -> ADD_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: MULT_IN_GGA(s(X), Y, R) -> MULT_IN_GGA(X, Y, Z) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: MULT_IN_GGA(s(X), Y, R) -> MULT_IN_GGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MULT_IN_GGA(s(X), Y) -> MULT_IN_GGA(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) 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: *MULT_IN_GGA(s(X), Y) -> MULT_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: MYINTEGER_IN_G(s(X)) -> MYINTEGER_IN_G(X) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) MYINTEGER_IN_G(x1) = MYINTEGER_IN_G(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: MYINTEGER_IN_G(s(X)) -> MYINTEGER_IN_G(X) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MYINTEGER_IN_G(s(X)) -> MYINTEGER_IN_G(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) 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: *MYINTEGER_IN_G(s(X)) -> MYINTEGER_IN_G(X) The graph contains the following edges 1 > 1 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Pi DP problem: The TRS P consists of the following rules: U2_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) EVALUATE_IN_GA(+(X, Y), Z) -> U2_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(+(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(-(X, Y), Z) -> U5_GA(X, Y, Z, evaluate_in_ga(X, X1)) U5_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) EVALUATE_IN_GA(-(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(*(X, Y), Z) -> U8_GA(X, Y, Z, evaluate_in_ga(X, X1)) U8_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) EVALUATE_IN_GA(*(X, Y), Z) -> EVALUATE_IN_GA(X, X1) The TRS R consists of the following rules: myis_in_ag(Z, X) -> U1_ag(Z, X, evaluate_in_ga(X, Z)) evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U1_ag(Z, X, evaluate_out_ga(X, Z)) -> myis_out_ag(Z, X) The argument filtering Pi contains the following mapping: myis_in_ag(x1, x2) = myis_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) myis_out_ag(x1, x2) = myis_out_ag(x1) EVALUATE_IN_GA(x1, x2) = EVALUATE_IN_GA(x1) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) U8_GA(x1, x2, x3, x4) = U8_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (37) Obligation: Pi DP problem: The TRS P consists of the following rules: U2_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) EVALUATE_IN_GA(+(X, Y), Z) -> U2_GA(X, Y, Z, evaluate_in_ga(X, X1)) EVALUATE_IN_GA(+(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(-(X, Y), Z) -> U5_GA(X, Y, Z, evaluate_in_ga(X, X1)) U5_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) EVALUATE_IN_GA(-(X, Y), Z) -> EVALUATE_IN_GA(X, X1) EVALUATE_IN_GA(*(X, Y), Z) -> U8_GA(X, Y, Z, evaluate_in_ga(X, X1)) U8_GA(X, Y, Z, evaluate_out_ga(X, X1)) -> EVALUATE_IN_GA(Y, Y1) EVALUATE_IN_GA(*(X, Y), Z) -> EVALUATE_IN_GA(X, X1) The TRS R consists of the following rules: evaluate_in_ga(+(X, Y), Z) -> U2_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(-(X, Y), Z) -> U5_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(*(X, Y), Z) -> U8_ga(X, Y, Z, evaluate_in_ga(X, X1)) evaluate_in_ga(X, X) -> U11_ga(X, myinteger_in_g(X)) U2_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U3_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U5_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U6_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U8_ga(X, Y, Z, evaluate_out_ga(X, X1)) -> U9_ga(X, Y, Z, X1, evaluate_in_ga(Y, Y1)) U11_ga(X, myinteger_out_g(X)) -> evaluate_out_ga(X, X) U3_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U4_ga(X, Y, Z, add_in_gga(X1, Y1, Z)) U6_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U7_ga(X, Y, Z, sub_in_gga(X1, Y1, Z)) U9_ga(X, Y, Z, X1, evaluate_out_ga(Y, Y1)) -> U10_ga(X, Y, Z, mult_in_gga(X1, Y1, Z)) myinteger_in_g(s(X)) -> U12_g(X, myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g(0) U4_ga(X, Y, Z, add_out_gga(X1, Y1, Z)) -> evaluate_out_ga(+(X, Y), Z) U7_ga(X, Y, Z, sub_out_gga(X1, Y1, Z)) -> evaluate_out_ga(-(X, Y), Z) U10_ga(X, Y, Z, mult_out_gga(X1, Y1, Z)) -> evaluate_out_ga(*(X, Y), Z) U12_g(X, myinteger_out_g(X)) -> myinteger_out_g(s(X)) add_in_gga(s(X), Y, s(Z)) -> U13_gga(X, Y, Z, add_in_gga(X, Y, Z)) add_in_gga(0, X, X) -> add_out_gga(0, X, X) sub_in_gga(s(X), s(Y), Z) -> U14_gga(X, Y, Z, sub_in_gga(X, Y, Z)) sub_in_gga(X, 0, X) -> sub_out_gga(X, 0, X) mult_in_gga(s(X), Y, R) -> U15_gga(X, Y, R, mult_in_gga(X, Y, Z)) mult_in_gga(0, Y, 0) -> mult_out_gga(0, Y, 0) U13_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) U14_gga(X, Y, Z, sub_out_gga(X, Y, Z)) -> sub_out_gga(s(X), s(Y), Z) U15_gga(X, Y, R, mult_out_gga(X, Y, Z)) -> U16_gga(X, Y, R, add_in_gga(Y, Z, R)) U16_gga(X, Y, R, add_out_gga(Y, Z, R)) -> mult_out_gga(s(X), Y, R) The argument filtering Pi contains the following mapping: evaluate_in_ga(x1, x2) = evaluate_in_ga(x1) +(x1, x2) = +(x1, x2) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) -(x1, x2) = -(x1, x2) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) *(x1, x2) = *(x1, x2) U8_ga(x1, x2, x3, x4) = U8_ga(x2, x4) U11_ga(x1, x2) = U11_ga(x1, x2) myinteger_in_g(x1) = myinteger_in_g(x1) s(x1) = s(x1) U12_g(x1, x2) = U12_g(x2) 0 = 0 myinteger_out_g(x1) = myinteger_out_g evaluate_out_ga(x1, x2) = evaluate_out_ga(x2) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x4, x5) U10_ga(x1, x2, x3, x4) = U10_ga(x4) mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) U15_gga(x1, x2, x3, x4) = U15_gga(x2, x4) mult_out_gga(x1, x2, x3) = mult_out_gga(x3) U16_gga(x1, x2, x3, x4) = U16_gga(x4) add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) U13_gga(x1, x2, x3, x4) = U13_gga(x4) add_out_gga(x1, x2, x3) = add_out_gga(x3) U6_ga(x1, x2, x3, x4, x5) = U6_ga(x4, x5) U7_ga(x1, x2, x3, x4) = U7_ga(x4) sub_in_gga(x1, x2, x3) = sub_in_gga(x1, x2) U14_gga(x1, x2, x3, x4) = U14_gga(x4) sub_out_gga(x1, x2, x3) = sub_out_gga(x3) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x4, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x4) EVALUATE_IN_GA(x1, x2) = EVALUATE_IN_GA(x1) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) U8_GA(x1, x2, x3, x4) = U8_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (38) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GA(Y, evaluate_out_ga(X1)) -> EVALUATE_IN_GA(Y) EVALUATE_IN_GA(+(X, Y)) -> U2_GA(Y, evaluate_in_ga(X)) EVALUATE_IN_GA(+(X, Y)) -> EVALUATE_IN_GA(X) EVALUATE_IN_GA(-(X, Y)) -> U5_GA(Y, evaluate_in_ga(X)) U5_GA(Y, evaluate_out_ga(X1)) -> EVALUATE_IN_GA(Y) EVALUATE_IN_GA(-(X, Y)) -> EVALUATE_IN_GA(X) EVALUATE_IN_GA(*(X, Y)) -> U8_GA(Y, evaluate_in_ga(X)) U8_GA(Y, evaluate_out_ga(X1)) -> EVALUATE_IN_GA(Y) EVALUATE_IN_GA(*(X, Y)) -> EVALUATE_IN_GA(X) The TRS R consists of the following rules: evaluate_in_ga(+(X, Y)) -> U2_ga(Y, evaluate_in_ga(X)) evaluate_in_ga(-(X, Y)) -> U5_ga(Y, evaluate_in_ga(X)) evaluate_in_ga(*(X, Y)) -> U8_ga(Y, evaluate_in_ga(X)) evaluate_in_ga(X) -> U11_ga(X, myinteger_in_g(X)) U2_ga(Y, evaluate_out_ga(X1)) -> U3_ga(X1, evaluate_in_ga(Y)) U5_ga(Y, evaluate_out_ga(X1)) -> U6_ga(X1, evaluate_in_ga(Y)) U8_ga(Y, evaluate_out_ga(X1)) -> U9_ga(X1, evaluate_in_ga(Y)) U11_ga(X, myinteger_out_g) -> evaluate_out_ga(X) U3_ga(X1, evaluate_out_ga(Y1)) -> U4_ga(add_in_gga(X1, Y1)) U6_ga(X1, evaluate_out_ga(Y1)) -> U7_ga(sub_in_gga(X1, Y1)) U9_ga(X1, evaluate_out_ga(Y1)) -> U10_ga(mult_in_gga(X1, Y1)) myinteger_in_g(s(X)) -> U12_g(myinteger_in_g(X)) myinteger_in_g(0) -> myinteger_out_g U4_ga(add_out_gga(Z)) -> evaluate_out_ga(Z) U7_ga(sub_out_gga(Z)) -> evaluate_out_ga(Z) U10_ga(mult_out_gga(Z)) -> evaluate_out_ga(Z) U12_g(myinteger_out_g) -> myinteger_out_g add_in_gga(s(X), Y) -> U13_gga(add_in_gga(X, Y)) add_in_gga(0, X) -> add_out_gga(X) sub_in_gga(s(X), s(Y)) -> U14_gga(sub_in_gga(X, Y)) sub_in_gga(X, 0) -> sub_out_gga(X) mult_in_gga(s(X), Y) -> U15_gga(Y, mult_in_gga(X, Y)) mult_in_gga(0, Y) -> mult_out_gga(0) U13_gga(add_out_gga(Z)) -> add_out_gga(s(Z)) U14_gga(sub_out_gga(Z)) -> sub_out_gga(Z) U15_gga(Y, mult_out_gga(Z)) -> U16_gga(add_in_gga(Y, Z)) U16_gga(add_out_gga(R)) -> mult_out_gga(R) The set Q consists of the following terms: evaluate_in_ga(x0) U2_ga(x0, x1) U5_ga(x0, x1) U8_ga(x0, x1) U11_ga(x0, x1) U3_ga(x0, x1) U6_ga(x0, x1) U9_ga(x0, x1) myinteger_in_g(x0) U4_ga(x0) U7_ga(x0) U10_ga(x0) U12_g(x0) add_in_gga(x0, x1) sub_in_gga(x0, x1) mult_in_gga(x0, x1) U13_gga(x0) U14_gga(x0) U15_gga(x0, x1) U16_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (40) 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: *EVALUATE_IN_GA(+(X, Y)) -> U2_GA(Y, evaluate_in_ga(X)) The graph contains the following edges 1 > 1 *U2_GA(Y, evaluate_out_ga(X1)) -> EVALUATE_IN_GA(Y) The graph contains the following edges 1 >= 1 *U5_GA(Y, evaluate_out_ga(X1)) -> EVALUATE_IN_GA(Y) The graph contains the following edges 1 >= 1 *U8_GA(Y, evaluate_out_ga(X1)) -> EVALUATE_IN_GA(Y) The graph contains the following edges 1 >= 1 *EVALUATE_IN_GA(-(X, Y)) -> U5_GA(Y, evaluate_in_ga(X)) The graph contains the following edges 1 > 1 *EVALUATE_IN_GA(*(X, Y)) -> U8_GA(Y, evaluate_in_ga(X)) The graph contains the following edges 1 > 1 *EVALUATE_IN_GA(+(X, Y)) -> EVALUATE_IN_GA(X) The graph contains the following edges 1 > 1 *EVALUATE_IN_GA(-(X, Y)) -> EVALUATE_IN_GA(X) The graph contains the following edges 1 > 1 *EVALUATE_IN_GA(*(X, Y)) -> EVALUATE_IN_GA(X) The graph contains the following edges 1 > 1 ---------------------------------------- (41) YES