4.30/1.88 YES 4.30/1.96 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.30/1.96 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.30/1.96 4.30/1.96 4.30/1.96 Left Termination of the query pattern 4.30/1.96 4.30/1.96 mult(g,g,a) 4.30/1.96 4.30/1.96 w.r.t. the given Prolog program could successfully be proven: 4.30/1.96 4.30/1.96 (0) Prolog 4.30/1.96 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.30/1.96 (2) PiTRS 4.30/1.96 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.30/1.96 (4) PiDP 4.30/1.96 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.30/1.96 (6) AND 4.30/1.96 (7) PiDP 4.30/1.96 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.30/1.96 (9) PiDP 4.30/1.96 (10) PiDPToQDPProof [SOUND, 11 ms] 4.30/1.96 (11) QDP 4.30/1.96 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.30/1.96 (13) YES 4.30/1.96 (14) PiDP 4.30/1.96 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.30/1.96 (16) PiDP 4.30/1.96 (17) PiDPToQDPProof [SOUND, 0 ms] 4.30/1.96 (18) QDP 4.30/1.96 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.30/1.96 (20) YES 4.30/1.96 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (0) 4.30/1.96 Obligation: 4.30/1.96 Clauses: 4.30/1.96 4.30/1.96 mult(X1, 0, 0). 4.30/1.96 mult(X, s(Y), Z) :- ','(mult(X, Y, W), sum(W, X, Z)). 4.30/1.96 sum(X, 0, X). 4.30/1.96 sum(X, s(Y), s(Z)) :- sum(X, Y, Z). 4.30/1.96 4.30/1.96 4.30/1.96 Query: mult(g,g,a) 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (1) PrologToPiTRSProof (SOUND) 4.30/1.96 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.30/1.96 4.30/1.96 mult_in_3: (b,b,f) 4.30/1.96 4.30/1.96 sum_in_3: (b,b,f) 4.30/1.96 4.30/1.96 Transforming Prolog into the following Term Rewriting System: 4.30/1.96 4.30/1.96 Pi-finite rewrite system: 4.30/1.96 The TRS R consists of the following rules: 4.30/1.96 4.30/1.96 mult_in_gga(X1, 0, 0) -> mult_out_gga(X1, 0, 0) 4.30/1.96 mult_in_gga(X, s(Y), Z) -> U1_gga(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 U1_gga(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_gga(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 sum_in_gga(X, 0, X) -> sum_out_gga(X, 0, X) 4.30/1.96 sum_in_gga(X, s(Y), s(Z)) -> U3_gga(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 U3_gga(X, Y, Z, sum_out_gga(X, Y, Z)) -> sum_out_gga(X, s(Y), s(Z)) 4.30/1.96 U2_gga(X, Y, Z, sum_out_gga(W, X, Z)) -> mult_out_gga(X, s(Y), Z) 4.30/1.96 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) 4.30/1.96 4.30/1.96 0 = 0 4.30/1.96 4.30/1.96 mult_out_gga(x1, x2, x3) = mult_out_gga(x3) 4.30/1.96 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 U1_gga(x1, x2, x3, x4) = U1_gga(x1, x4) 4.30/1.96 4.30/1.96 U2_gga(x1, x2, x3, x4) = U2_gga(x4) 4.30/1.96 4.30/1.96 sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) 4.30/1.96 4.30/1.96 sum_out_gga(x1, x2, x3) = sum_out_gga(x3) 4.30/1.96 4.30/1.96 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.30/1.96 4.30/1.96 4.30/1.96 4.30/1.96 4.30/1.96 4.30/1.96 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.30/1.96 4.30/1.96 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (2) 4.30/1.96 Obligation: 4.30/1.96 Pi-finite rewrite system: 4.30/1.96 The TRS R consists of the following rules: 4.30/1.96 4.30/1.96 mult_in_gga(X1, 0, 0) -> mult_out_gga(X1, 0, 0) 4.30/1.96 mult_in_gga(X, s(Y), Z) -> U1_gga(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 U1_gga(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_gga(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 sum_in_gga(X, 0, X) -> sum_out_gga(X, 0, X) 4.30/1.96 sum_in_gga(X, s(Y), s(Z)) -> U3_gga(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 U3_gga(X, Y, Z, sum_out_gga(X, Y, Z)) -> sum_out_gga(X, s(Y), s(Z)) 4.30/1.96 U2_gga(X, Y, Z, sum_out_gga(W, X, Z)) -> mult_out_gga(X, s(Y), Z) 4.30/1.96 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) 4.30/1.96 4.30/1.96 0 = 0 4.30/1.96 4.30/1.96 mult_out_gga(x1, x2, x3) = mult_out_gga(x3) 4.30/1.96 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 U1_gga(x1, x2, x3, x4) = U1_gga(x1, x4) 4.30/1.96 4.30/1.96 U2_gga(x1, x2, x3, x4) = U2_gga(x4) 4.30/1.96 4.30/1.96 sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) 4.30/1.96 4.30/1.96 sum_out_gga(x1, x2, x3) = sum_out_gga(x3) 4.30/1.96 4.30/1.96 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.30/1.96 4.30/1.96 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (3) DependencyPairsProof (EQUIVALENT) 4.30/1.96 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.30/1.96 Pi DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 MULT_IN_GGA(X, s(Y), Z) -> U1_GGA(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 MULT_IN_GGA(X, s(Y), Z) -> MULT_IN_GGA(X, Y, W) 4.30/1.96 U1_GGA(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_GGA(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 U1_GGA(X, Y, Z, mult_out_gga(X, Y, W)) -> SUM_IN_GGA(W, X, Z) 4.30/1.96 SUM_IN_GGA(X, s(Y), s(Z)) -> U3_GGA(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 SUM_IN_GGA(X, s(Y), s(Z)) -> SUM_IN_GGA(X, Y, Z) 4.30/1.96 4.30/1.96 The TRS R consists of the following rules: 4.30/1.96 4.30/1.96 mult_in_gga(X1, 0, 0) -> mult_out_gga(X1, 0, 0) 4.30/1.96 mult_in_gga(X, s(Y), Z) -> U1_gga(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 U1_gga(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_gga(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 sum_in_gga(X, 0, X) -> sum_out_gga(X, 0, X) 4.30/1.96 sum_in_gga(X, s(Y), s(Z)) -> U3_gga(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 U3_gga(X, Y, Z, sum_out_gga(X, Y, Z)) -> sum_out_gga(X, s(Y), s(Z)) 4.30/1.96 U2_gga(X, Y, Z, sum_out_gga(W, X, Z)) -> mult_out_gga(X, s(Y), Z) 4.30/1.96 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) 4.30/1.96 4.30/1.96 0 = 0 4.30/1.96 4.30/1.96 mult_out_gga(x1, x2, x3) = mult_out_gga(x3) 4.30/1.96 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 U1_gga(x1, x2, x3, x4) = U1_gga(x1, x4) 4.30/1.96 4.30/1.96 U2_gga(x1, x2, x3, x4) = U2_gga(x4) 4.30/1.96 4.30/1.96 sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) 4.30/1.96 4.30/1.96 sum_out_gga(x1, x2, x3) = sum_out_gga(x3) 4.30/1.96 4.30/1.96 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.30/1.96 4.30/1.96 MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x4) 4.30/1.96 4.30/1.96 U2_GGA(x1, x2, x3, x4) = U2_GGA(x4) 4.30/1.96 4.30/1.96 SUM_IN_GGA(x1, x2, x3) = SUM_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) 4.30/1.96 4.30/1.96 4.30/1.96 We have to consider all (P,R,Pi)-chains 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (4) 4.30/1.96 Obligation: 4.30/1.96 Pi DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 MULT_IN_GGA(X, s(Y), Z) -> U1_GGA(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 MULT_IN_GGA(X, s(Y), Z) -> MULT_IN_GGA(X, Y, W) 4.30/1.96 U1_GGA(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_GGA(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 U1_GGA(X, Y, Z, mult_out_gga(X, Y, W)) -> SUM_IN_GGA(W, X, Z) 4.30/1.96 SUM_IN_GGA(X, s(Y), s(Z)) -> U3_GGA(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 SUM_IN_GGA(X, s(Y), s(Z)) -> SUM_IN_GGA(X, Y, Z) 4.30/1.96 4.30/1.96 The TRS R consists of the following rules: 4.30/1.96 4.30/1.96 mult_in_gga(X1, 0, 0) -> mult_out_gga(X1, 0, 0) 4.30/1.96 mult_in_gga(X, s(Y), Z) -> U1_gga(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 U1_gga(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_gga(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 sum_in_gga(X, 0, X) -> sum_out_gga(X, 0, X) 4.30/1.96 sum_in_gga(X, s(Y), s(Z)) -> U3_gga(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 U3_gga(X, Y, Z, sum_out_gga(X, Y, Z)) -> sum_out_gga(X, s(Y), s(Z)) 4.30/1.96 U2_gga(X, Y, Z, sum_out_gga(W, X, Z)) -> mult_out_gga(X, s(Y), Z) 4.30/1.96 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) 4.30/1.96 4.30/1.96 0 = 0 4.30/1.96 4.30/1.96 mult_out_gga(x1, x2, x3) = mult_out_gga(x3) 4.30/1.96 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 U1_gga(x1, x2, x3, x4) = U1_gga(x1, x4) 4.30/1.96 4.30/1.96 U2_gga(x1, x2, x3, x4) = U2_gga(x4) 4.30/1.96 4.30/1.96 sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) 4.30/1.96 4.30/1.96 sum_out_gga(x1, x2, x3) = sum_out_gga(x3) 4.30/1.96 4.30/1.96 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.30/1.96 4.30/1.96 MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x4) 4.30/1.96 4.30/1.96 U2_GGA(x1, x2, x3, x4) = U2_GGA(x4) 4.30/1.96 4.30/1.96 SUM_IN_GGA(x1, x2, x3) = SUM_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) 4.30/1.96 4.30/1.96 4.30/1.96 We have to consider all (P,R,Pi)-chains 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (5) DependencyGraphProof (EQUIVALENT) 4.30/1.96 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (6) 4.30/1.96 Complex Obligation (AND) 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (7) 4.30/1.96 Obligation: 4.30/1.96 Pi DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 SUM_IN_GGA(X, s(Y), s(Z)) -> SUM_IN_GGA(X, Y, Z) 4.30/1.96 4.30/1.96 The TRS R consists of the following rules: 4.30/1.96 4.30/1.96 mult_in_gga(X1, 0, 0) -> mult_out_gga(X1, 0, 0) 4.30/1.96 mult_in_gga(X, s(Y), Z) -> U1_gga(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 U1_gga(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_gga(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 sum_in_gga(X, 0, X) -> sum_out_gga(X, 0, X) 4.30/1.96 sum_in_gga(X, s(Y), s(Z)) -> U3_gga(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 U3_gga(X, Y, Z, sum_out_gga(X, Y, Z)) -> sum_out_gga(X, s(Y), s(Z)) 4.30/1.96 U2_gga(X, Y, Z, sum_out_gga(W, X, Z)) -> mult_out_gga(X, s(Y), Z) 4.30/1.96 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) 4.30/1.96 4.30/1.96 0 = 0 4.30/1.96 4.30/1.96 mult_out_gga(x1, x2, x3) = mult_out_gga(x3) 4.30/1.96 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 U1_gga(x1, x2, x3, x4) = U1_gga(x1, x4) 4.30/1.96 4.30/1.96 U2_gga(x1, x2, x3, x4) = U2_gga(x4) 4.30/1.96 4.30/1.96 sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) 4.30/1.96 4.30/1.96 sum_out_gga(x1, x2, x3) = sum_out_gga(x3) 4.30/1.96 4.30/1.96 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.30/1.96 4.30/1.96 SUM_IN_GGA(x1, x2, x3) = SUM_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 4.30/1.96 We have to consider all (P,R,Pi)-chains 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (8) UsableRulesProof (EQUIVALENT) 4.30/1.96 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (9) 4.30/1.96 Obligation: 4.30/1.96 Pi DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 SUM_IN_GGA(X, s(Y), s(Z)) -> SUM_IN_GGA(X, Y, Z) 4.30/1.96 4.30/1.96 R is empty. 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 SUM_IN_GGA(x1, x2, x3) = SUM_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 4.30/1.96 We have to consider all (P,R,Pi)-chains 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (10) PiDPToQDPProof (SOUND) 4.30/1.96 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (11) 4.30/1.96 Obligation: 4.30/1.96 Q DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 SUM_IN_GGA(X, s(Y)) -> SUM_IN_GGA(X, Y) 4.30/1.96 4.30/1.96 R is empty. 4.30/1.96 Q is empty. 4.30/1.96 We have to consider all (P,Q,R)-chains. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (12) QDPSizeChangeProof (EQUIVALENT) 4.30/1.96 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. 4.30/1.96 4.30/1.96 From the DPs we obtained the following set of size-change graphs: 4.30/1.96 *SUM_IN_GGA(X, s(Y)) -> SUM_IN_GGA(X, Y) 4.30/1.96 The graph contains the following edges 1 >= 1, 2 > 2 4.30/1.96 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (13) 4.30/1.96 YES 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (14) 4.30/1.96 Obligation: 4.30/1.96 Pi DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 MULT_IN_GGA(X, s(Y), Z) -> MULT_IN_GGA(X, Y, W) 4.30/1.96 4.30/1.96 The TRS R consists of the following rules: 4.30/1.96 4.30/1.96 mult_in_gga(X1, 0, 0) -> mult_out_gga(X1, 0, 0) 4.30/1.96 mult_in_gga(X, s(Y), Z) -> U1_gga(X, Y, Z, mult_in_gga(X, Y, W)) 4.30/1.96 U1_gga(X, Y, Z, mult_out_gga(X, Y, W)) -> U2_gga(X, Y, Z, sum_in_gga(W, X, Z)) 4.30/1.96 sum_in_gga(X, 0, X) -> sum_out_gga(X, 0, X) 4.30/1.96 sum_in_gga(X, s(Y), s(Z)) -> U3_gga(X, Y, Z, sum_in_gga(X, Y, Z)) 4.30/1.96 U3_gga(X, Y, Z, sum_out_gga(X, Y, Z)) -> sum_out_gga(X, s(Y), s(Z)) 4.30/1.96 U2_gga(X, Y, Z, sum_out_gga(W, X, Z)) -> mult_out_gga(X, s(Y), Z) 4.30/1.96 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 mult_in_gga(x1, x2, x3) = mult_in_gga(x1, x2) 4.30/1.96 4.30/1.96 0 = 0 4.30/1.96 4.30/1.96 mult_out_gga(x1, x2, x3) = mult_out_gga(x3) 4.30/1.96 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 U1_gga(x1, x2, x3, x4) = U1_gga(x1, x4) 4.30/1.96 4.30/1.96 U2_gga(x1, x2, x3, x4) = U2_gga(x4) 4.30/1.96 4.30/1.96 sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) 4.30/1.96 4.30/1.96 sum_out_gga(x1, x2, x3) = sum_out_gga(x3) 4.30/1.96 4.30/1.96 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.30/1.96 4.30/1.96 MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 4.30/1.96 We have to consider all (P,R,Pi)-chains 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (15) UsableRulesProof (EQUIVALENT) 4.30/1.96 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (16) 4.30/1.96 Obligation: 4.30/1.96 Pi DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 MULT_IN_GGA(X, s(Y), Z) -> MULT_IN_GGA(X, Y, W) 4.30/1.96 4.30/1.96 R is empty. 4.30/1.96 The argument filtering Pi contains the following mapping: 4.30/1.96 s(x1) = s(x1) 4.30/1.96 4.30/1.96 MULT_IN_GGA(x1, x2, x3) = MULT_IN_GGA(x1, x2) 4.30/1.96 4.30/1.96 4.30/1.96 We have to consider all (P,R,Pi)-chains 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (17) PiDPToQDPProof (SOUND) 4.30/1.96 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (18) 4.30/1.96 Obligation: 4.30/1.96 Q DP problem: 4.30/1.96 The TRS P consists of the following rules: 4.30/1.96 4.30/1.96 MULT_IN_GGA(X, s(Y)) -> MULT_IN_GGA(X, Y) 4.30/1.96 4.30/1.96 R is empty. 4.30/1.96 Q is empty. 4.30/1.96 We have to consider all (P,Q,R)-chains. 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (19) QDPSizeChangeProof (EQUIVALENT) 4.30/1.96 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. 4.30/1.96 4.30/1.96 From the DPs we obtained the following set of size-change graphs: 4.30/1.96 *MULT_IN_GGA(X, s(Y)) -> MULT_IN_GGA(X, Y) 4.30/1.96 The graph contains the following edges 1 >= 1, 2 > 2 4.30/1.96 4.30/1.96 4.30/1.96 ---------------------------------------- 4.30/1.96 4.30/1.96 (20) 4.30/1.96 YES 4.54/1.99 EOF