/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern weight(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 21 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) UsableRulesReductionPairsProof [EQUIVALENT, 61 ms] (13) QDP (14) PisEmptyProof [EQUIVALENT, 0 ms] (15) YES (16) PiDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) PiDP (19) PiDPToQDPProof [SOUND, 4 ms] (20) QDP (21) UsableRulesReductionPairsProof [EQUIVALENT, 32 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) TRUE ---------------------------------------- (0) Obligation: Clauses: sum(.(s(N), XS), .(M, YS), ZS) :- sum(.(N, XS), .(s(M), YS), ZS). sum(.(0, XS), YS, ZS) :- sum(XS, YS, ZS). sum([], YS, YS). weight(.(N, .(M, XS)), X) :- ','(sum(.(N, .(M, XS)), .(0, XS), YS), weight(YS, X)). weight(.(X, []), X). Query: weight(g,a) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: weight_in_2: (b,f) sum_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: weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X)) weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X) U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X) The argument filtering Pi contains the following mapping: weight_in_ga(x1, x2) = weight_in_ga(x1) .(x1, x2) = .(x1, x2) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) weight_out_ga(x1, x2) = weight_out_ga(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X)) weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X) U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X) The argument filtering Pi contains the following mapping: weight_in_ga(x1, x2) = weight_in_ga(x1) .(x1, x2) = .(x1, x2) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) weight_out_ga(x1, x2) = weight_out_ga(x2) ---------------------------------------- (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: WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) WEIGHT_IN_GA(.(N, .(M, XS)), X) -> SUM_IN_GGA(.(N, .(M, XS)), .(0, XS), YS) SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> U1_GGA(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS) SUM_IN_GGA(.(0, XS), YS, ZS) -> U2_GGA(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS) U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_GA(N, M, XS, X, weight_in_ga(YS, X)) U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X) The TRS R consists of the following rules: weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X)) weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X) U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X) The argument filtering Pi contains the following mapping: weight_in_ga(x1, x2) = weight_in_ga(x1) .(x1, x2) = .(x1, x2) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) weight_out_ga(x1, x2) = weight_out_ga(x2) WEIGHT_IN_GA(x1, x2) = WEIGHT_IN_GA(x1) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) SUM_IN_GGA(x1, x2, x3) = SUM_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5, x6) = U1_GGA(x6) U2_GGA(x1, x2, x3, x4) = U2_GGA(x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) WEIGHT_IN_GA(.(N, .(M, XS)), X) -> SUM_IN_GGA(.(N, .(M, XS)), .(0, XS), YS) SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> U1_GGA(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS) SUM_IN_GGA(.(0, XS), YS, ZS) -> U2_GGA(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS) U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_GA(N, M, XS, X, weight_in_ga(YS, X)) U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X) The TRS R consists of the following rules: weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X)) weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X) U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X) The argument filtering Pi contains the following mapping: weight_in_ga(x1, x2) = weight_in_ga(x1) .(x1, x2) = .(x1, x2) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) weight_out_ga(x1, x2) = weight_out_ga(x2) WEIGHT_IN_GA(x1, x2) = WEIGHT_IN_GA(x1) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) SUM_IN_GGA(x1, x2, x3) = SUM_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5, x6) = U1_GGA(x6) U2_GGA(x1, x2, x3, x4) = U2_GGA(x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS) SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS) The TRS R consists of the following rules: weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X)) weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X) U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X) The argument filtering Pi contains the following mapping: weight_in_ga(x1, x2) = weight_in_ga(x1) .(x1, x2) = .(x1, x2) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) weight_out_ga(x1, x2) = weight_out_ga(x2) SUM_IN_GGA(x1, x2, x3) = SUM_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: SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS) SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) s(x1) = s(x1) 0 = 0 SUM_IN_GGA(x1, x2, x3) = SUM_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: SUM_IN_GGA(.(0, XS), YS) -> SUM_IN_GGA(XS, YS) SUM_IN_GGA(.(s(N), XS), .(M, YS)) -> SUM_IN_GGA(.(N, XS), .(s(M), YS)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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. The following dependency pairs can be deleted: SUM_IN_GGA(.(0, XS), YS) -> SUM_IN_GGA(XS, YS) SUM_IN_GGA(.(s(N), XS), .(M, YS)) -> SUM_IN_GGA(.(N, XS), .(s(M), YS)) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(0) = 0 POL(SUM_IN_GGA(x_1, x_2)) = 2*x_1 + x_2 POL(s(x_1)) = 2 + x_1 ---------------------------------------- (13) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X) WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) The TRS R consists of the following rules: weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X)) weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X) U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X) The argument filtering Pi contains the following mapping: weight_in_ga(x1, x2) = weight_in_ga(x1) .(x1, x2) = .(x1, x2) U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) weight_out_ga(x1, x2) = weight_out_ga(x2) WEIGHT_IN_GA(x1, x2) = WEIGHT_IN_GA(x1) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X) WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS)) The TRS R consists of the following rules: sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS)) sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS)) U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS) U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS) sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) sum_in_gga(x1, x2, x3) = sum_in_gga(x1, x2) s(x1) = s(x1) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x6) 0 = 0 U2_gga(x1, x2, x3, x4) = U2_gga(x4) [] = [] sum_out_gga(x1, x2, x3) = sum_out_gga(x3) WEIGHT_IN_GA(x1, x2) = WEIGHT_IN_GA(x1) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GA(sum_out_gga(YS)) -> WEIGHT_IN_GA(YS) WEIGHT_IN_GA(.(N, .(M, XS))) -> U3_GA(sum_in_gga(.(N, .(M, XS)), .(0, XS))) The TRS R consists of the following rules: sum_in_gga(.(s(N), XS), .(M, YS)) -> U1_gga(sum_in_gga(.(N, XS), .(s(M), YS))) sum_in_gga(.(0, XS), YS) -> U2_gga(sum_in_gga(XS, YS)) U1_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS) U2_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS) sum_in_gga([], YS) -> sum_out_gga(YS) The set Q consists of the following terms: sum_in_gga(x0, x1) U1_gga(x0) U2_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) 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. The following dependency pairs can be deleted: WEIGHT_IN_GA(.(N, .(M, XS))) -> U3_GA(sum_in_gga(.(N, .(M, XS)), .(0, XS))) The following rules are removed from R: sum_in_gga([], YS) -> sum_out_gga(YS) Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + 2*x_2 POL(0) = 0 POL(U1_gga(x_1)) = x_1 POL(U2_gga(x_1)) = x_1 POL(U3_GA(x_1)) = x_1 POL(WEIGHT_IN_GA(x_1)) = 1 + 2*x_1 POL([]) = 2 POL(s(x_1)) = x_1 POL(sum_in_gga(x_1, x_2)) = x_1 + 2*x_2 POL(sum_out_gga(x_1)) = 1 + 2*x_1 ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GA(sum_out_gga(YS)) -> WEIGHT_IN_GA(YS) The TRS R consists of the following rules: sum_in_gga(.(s(N), XS), .(M, YS)) -> U1_gga(sum_in_gga(.(N, XS), .(s(M), YS))) sum_in_gga(.(0, XS), YS) -> U2_gga(sum_in_gga(XS, YS)) U2_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS) U1_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS) The set Q consists of the following terms: sum_in_gga(x0, x1) U1_gga(x0) U2_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (24) TRUE