/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) QDPOrderProof [EQUIVALENT, 251 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) a__sqr(0) -> 0 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) a__dbl(0) -> 0 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) a__add(0, X) -> mark(X) a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) a__first(0, X) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__half(0) -> 0 a__half(s(0)) -> 0 a__half(s(s(X))) -> s(a__half(mark(X))) a__half(dbl(X)) -> mark(X) mark(terms(X)) -> a__terms(mark(X)) mark(sqr(X)) -> a__sqr(mark(X)) mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(half(X)) -> a__half(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(nil) -> nil a__terms(X) -> terms(X) a__sqr(X) -> sqr(X) a__add(X1, X2) -> add(X1, X2) a__dbl(X) -> dbl(X) a__first(X1, X2) -> first(X1, X2) a__half(X) -> half(X) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: A__TERMS(N) -> A__SQR(mark(N)) A__TERMS(N) -> MARK(N) A__SQR(s(X)) -> A__ADD(a__sqr(mark(X)), a__dbl(mark(X))) A__SQR(s(X)) -> A__SQR(mark(X)) A__SQR(s(X)) -> MARK(X) A__SQR(s(X)) -> A__DBL(mark(X)) A__DBL(s(X)) -> A__DBL(mark(X)) A__DBL(s(X)) -> MARK(X) A__ADD(0, X) -> MARK(X) A__ADD(s(X), Y) -> A__ADD(mark(X), mark(Y)) A__ADD(s(X), Y) -> MARK(X) A__ADD(s(X), Y) -> MARK(Y) A__FIRST(s(X), cons(Y, Z)) -> MARK(Y) A__HALF(s(s(X))) -> A__HALF(mark(X)) A__HALF(s(s(X))) -> MARK(X) A__HALF(dbl(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> MARK(X) MARK(sqr(X)) -> A__SQR(mark(X)) MARK(sqr(X)) -> MARK(X) MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2)) MARK(add(X1, X2)) -> MARK(X1) MARK(add(X1, X2)) -> MARK(X2) MARK(dbl(X)) -> A__DBL(mark(X)) MARK(dbl(X)) -> MARK(X) MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2)) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) MARK(half(X)) -> A__HALF(mark(X)) MARK(half(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(recip(X)) -> MARK(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) a__sqr(0) -> 0 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) a__dbl(0) -> 0 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) a__add(0, X) -> mark(X) a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) a__first(0, X) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__half(0) -> 0 a__half(s(0)) -> 0 a__half(s(s(X))) -> s(a__half(mark(X))) a__half(dbl(X)) -> mark(X) mark(terms(X)) -> a__terms(mark(X)) mark(sqr(X)) -> a__sqr(mark(X)) mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(half(X)) -> a__half(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(nil) -> nil a__terms(X) -> terms(X) a__sqr(X) -> sqr(X) a__add(X1, X2) -> add(X1, X2) a__dbl(X) -> dbl(X) a__first(X1, X2) -> first(X1, X2) a__half(X) -> half(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__TERMS(N) -> MARK(N) A__SQR(s(X)) -> A__ADD(a__sqr(mark(X)), a__dbl(mark(X))) A__SQR(s(X)) -> A__SQR(mark(X)) A__SQR(s(X)) -> MARK(X) A__SQR(s(X)) -> A__DBL(mark(X)) A__DBL(s(X)) -> A__DBL(mark(X)) A__DBL(s(X)) -> MARK(X) A__ADD(0, X) -> MARK(X) A__ADD(s(X), Y) -> A__ADD(mark(X), mark(Y)) A__ADD(s(X), Y) -> MARK(X) A__ADD(s(X), Y) -> MARK(Y) A__HALF(s(s(X))) -> A__HALF(mark(X)) A__HALF(s(s(X))) -> MARK(X) A__HALF(dbl(X)) -> MARK(X) MARK(terms(X)) -> A__TERMS(mark(X)) MARK(terms(X)) -> MARK(X) MARK(sqr(X)) -> A__SQR(mark(X)) MARK(sqr(X)) -> MARK(X) MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2)) MARK(add(X1, X2)) -> MARK(X1) MARK(add(X1, X2)) -> MARK(X2) MARK(dbl(X)) -> A__DBL(mark(X)) MARK(dbl(X)) -> MARK(X) MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2)) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. A__TERMS(x1) = A__TERMS(x1) A__SQR(x1) = A__SQR(x1) mark(x1) = x1 MARK(x1) = MARK(x1) s(x1) = s(x1) A__ADD(x1, x2) = A__ADD(x1, x2) a__sqr(x1) = a__sqr(x1) a__dbl(x1) = a__dbl(x1) A__DBL(x1) = A__DBL(x1) 0 = 0 A__FIRST(x1, x2) = A__FIRST(x2) cons(x1, x2) = x1 A__HALF(x1) = A__HALF(x1) dbl(x1) = dbl(x1) terms(x1) = terms(x1) sqr(x1) = sqr(x1) add(x1, x2) = add(x1, x2) first(x1, x2) = first(x1, x2) half(x1) = x1 recip(x1) = x1 a__terms(x1) = a__terms(x1) a__add(x1, x2) = a__add(x1, x2) a__half(x1) = x1 a__first(x1, x2) = a__first(x1, x2) nil = nil Recursive path order with status [RPO]. Quasi-Precedence: [A__TERMS_1, A__SQR_1, a__sqr_1, a__dbl_1, 0, dbl_1, terms_1, sqr_1, a__terms_1] > A__DBL_1 > [MARK_1, A__FIRST_1, A__HALF_1] [A__TERMS_1, A__SQR_1, a__sqr_1, a__dbl_1, 0, dbl_1, terms_1, sqr_1, a__terms_1] > [add_2, a__add_2] > s_1 [A__TERMS_1, A__SQR_1, a__sqr_1, a__dbl_1, 0, dbl_1, terms_1, sqr_1, a__terms_1] > [add_2, a__add_2] > A__ADD_2 > [MARK_1, A__FIRST_1, A__HALF_1] [A__TERMS_1, A__SQR_1, a__sqr_1, a__dbl_1, 0, dbl_1, terms_1, sqr_1, a__terms_1] > nil [first_2, a__first_2] > [MARK_1, A__FIRST_1, A__HALF_1] [first_2, a__first_2] > nil Status: A__TERMS_1: [1] A__SQR_1: [1] MARK_1: multiset status s_1: [1] A__ADD_2: multiset status a__sqr_1: [1] a__dbl_1: [1] A__DBL_1: [1] 0: multiset status A__FIRST_1: multiset status A__HALF_1: multiset status dbl_1: [1] terms_1: [1] sqr_1: [1] add_2: [2,1] first_2: [2,1] a__terms_1: [1] a__add_2: [2,1] a__first_2: [2,1] nil: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(terms(X)) -> a__terms(mark(X)) mark(sqr(X)) -> a__sqr(mark(X)) mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) a__add(0, X) -> mark(X) mark(half(X)) -> a__half(mark(X)) a__half(dbl(X)) -> mark(X) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(nil) -> nil a__sqr(0) -> 0 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) a__sqr(X) -> sqr(X) a__dbl(0) -> 0 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) a__dbl(X) -> dbl(X) a__terms(X) -> terms(X) a__add(X1, X2) -> add(X1, X2) a__half(0) -> 0 a__half(s(0)) -> 0 a__half(X) -> half(X) a__first(0, X) -> nil a__first(X1, X2) -> first(X1, X2) a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) a__half(s(s(X))) -> s(a__half(mark(X))) a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: A__TERMS(N) -> A__SQR(mark(N)) A__FIRST(s(X), cons(Y, Z)) -> MARK(Y) MARK(half(X)) -> A__HALF(mark(X)) MARK(half(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(recip(X)) -> MARK(X) The TRS R consists of the following rules: a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) a__sqr(0) -> 0 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) a__dbl(0) -> 0 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) a__add(0, X) -> mark(X) a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) a__first(0, X) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__half(0) -> 0 a__half(s(0)) -> 0 a__half(s(s(X))) -> s(a__half(mark(X))) a__half(dbl(X)) -> mark(X) mark(terms(X)) -> a__terms(mark(X)) mark(sqr(X)) -> a__sqr(mark(X)) mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(half(X)) -> a__half(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(nil) -> nil a__terms(X) -> terms(X) a__sqr(X) -> sqr(X) a__add(X1, X2) -> add(X1, X2) a__dbl(X) -> dbl(X) a__first(X1, X2) -> first(X1, X2) a__half(X) -> half(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) MARK(half(X)) -> MARK(X) MARK(recip(X)) -> MARK(X) The TRS R consists of the following rules: a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) a__sqr(0) -> 0 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) a__dbl(0) -> 0 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) a__add(0, X) -> mark(X) a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) a__first(0, X) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__half(0) -> 0 a__half(s(0)) -> 0 a__half(s(s(X))) -> s(a__half(mark(X))) a__half(dbl(X)) -> mark(X) mark(terms(X)) -> a__terms(mark(X)) mark(sqr(X)) -> a__sqr(mark(X)) mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) mark(dbl(X)) -> a__dbl(mark(X)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(half(X)) -> a__half(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(recip(X)) -> recip(mark(X)) mark(s(X)) -> s(mark(X)) mark(0) -> 0 mark(nil) -> nil a__terms(X) -> terms(X) a__sqr(X) -> sqr(X) a__add(X1, X2) -> add(X1, X2) a__dbl(X) -> dbl(X) a__first(X1, X2) -> first(X1, X2) a__half(X) -> half(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) MARK(half(X)) -> MARK(X) MARK(recip(X)) -> MARK(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) 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: *MARK(cons(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(half(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(recip(X)) -> MARK(X) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES