8.09/2.89 YES 8.09/2.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.09/2.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.09/2.90 8.09/2.90 8.09/2.90 Termination w.r.t. Q of the given QTRS could be proven: 8.09/2.90 8.09/2.90 (0) QTRS 8.09/2.90 (1) DependencyPairsProof [EQUIVALENT, 16 ms] 8.09/2.90 (2) QDP 8.09/2.90 (3) QDPOrderProof [EQUIVALENT, 349 ms] 8.09/2.90 (4) QDP 8.09/2.90 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.09/2.90 (6) QDP 8.09/2.90 (7) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.90 (8) QDP 8.09/2.90 (9) QReductionProof [EQUIVALENT, 0 ms] 8.09/2.90 (10) QDP 8.09/2.90 (11) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.09/2.90 (12) YES 8.09/2.90 8.09/2.90 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (0) 8.09/2.90 Obligation: 8.09/2.90 Q restricted rewrite system: 8.09/2.90 The TRS R consists of the following rules: 8.09/2.90 8.09/2.90 a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) 8.09/2.90 a__sqr(0) -> 0 8.09/2.90 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) 8.09/2.90 a__dbl(0) -> 0 8.09/2.90 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) 8.09/2.90 a__add(0, X) -> mark(X) 8.09/2.90 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 8.09/2.90 a__first(0, X) -> nil 8.09/2.90 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 8.09/2.90 a__half(0) -> 0 8.09/2.90 a__half(s(0)) -> 0 8.09/2.90 a__half(s(s(X))) -> s(a__half(mark(X))) 8.09/2.90 a__half(dbl(X)) -> mark(X) 8.09/2.90 mark(terms(X)) -> a__terms(mark(X)) 8.09/2.90 mark(sqr(X)) -> a__sqr(mark(X)) 8.09/2.90 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 8.09/2.90 mark(dbl(X)) -> a__dbl(mark(X)) 8.09/2.90 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 8.09/2.90 mark(half(X)) -> a__half(mark(X)) 8.09/2.90 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.09/2.90 mark(recip(X)) -> recip(mark(X)) 8.09/2.90 mark(s(X)) -> s(mark(X)) 8.09/2.90 mark(0) -> 0 8.09/2.90 mark(nil) -> nil 8.09/2.90 a__terms(X) -> terms(X) 8.09/2.90 a__sqr(X) -> sqr(X) 8.09/2.90 a__add(X1, X2) -> add(X1, X2) 8.09/2.90 a__dbl(X) -> dbl(X) 8.09/2.90 a__first(X1, X2) -> first(X1, X2) 8.09/2.90 a__half(X) -> half(X) 8.09/2.90 8.09/2.90 The set Q consists of the following terms: 8.09/2.90 8.09/2.90 a__terms(x0) 8.09/2.90 mark(terms(x0)) 8.09/2.90 mark(sqr(x0)) 8.09/2.90 mark(add(x0, x1)) 8.09/2.90 mark(dbl(x0)) 8.09/2.90 mark(first(x0, x1)) 8.09/2.90 mark(half(x0)) 8.09/2.90 mark(cons(x0, x1)) 8.09/2.90 mark(recip(x0)) 8.09/2.90 mark(s(x0)) 8.09/2.90 mark(0) 8.09/2.90 mark(nil) 8.09/2.90 a__sqr(x0) 8.09/2.90 a__add(x0, x1) 8.09/2.90 a__dbl(x0) 8.09/2.90 a__first(x0, x1) 8.09/2.90 a__half(x0) 8.09/2.90 8.09/2.90 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (1) DependencyPairsProof (EQUIVALENT) 8.09/2.90 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (2) 8.09/2.90 Obligation: 8.09/2.90 Q DP problem: 8.09/2.90 The TRS P consists of the following rules: 8.09/2.90 8.09/2.90 A__TERMS(N) -> A__SQR(mark(N)) 8.09/2.90 A__TERMS(N) -> MARK(N) 8.09/2.90 A__SQR(s(X)) -> A__ADD(a__sqr(mark(X)), a__dbl(mark(X))) 8.09/2.90 A__SQR(s(X)) -> A__SQR(mark(X)) 8.09/2.90 A__SQR(s(X)) -> MARK(X) 8.09/2.90 A__SQR(s(X)) -> A__DBL(mark(X)) 8.09/2.90 A__DBL(s(X)) -> A__DBL(mark(X)) 8.09/2.90 A__DBL(s(X)) -> MARK(X) 8.09/2.90 A__ADD(0, X) -> MARK(X) 8.09/2.90 A__ADD(s(X), Y) -> A__ADD(mark(X), mark(Y)) 8.09/2.90 A__ADD(s(X), Y) -> MARK(X) 8.09/2.90 A__ADD(s(X), Y) -> MARK(Y) 8.09/2.90 A__FIRST(s(X), cons(Y, Z)) -> MARK(Y) 8.09/2.90 A__HALF(s(s(X))) -> A__HALF(mark(X)) 8.09/2.90 A__HALF(s(s(X))) -> MARK(X) 8.09/2.90 A__HALF(dbl(X)) -> MARK(X) 8.09/2.90 MARK(terms(X)) -> A__TERMS(mark(X)) 8.09/2.90 MARK(terms(X)) -> MARK(X) 8.09/2.90 MARK(sqr(X)) -> A__SQR(mark(X)) 8.09/2.90 MARK(sqr(X)) -> MARK(X) 8.09/2.90 MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2)) 8.09/2.90 MARK(add(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(add(X1, X2)) -> MARK(X2) 8.09/2.90 MARK(dbl(X)) -> A__DBL(mark(X)) 8.09/2.90 MARK(dbl(X)) -> MARK(X) 8.09/2.90 MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2)) 8.09/2.90 MARK(first(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(first(X1, X2)) -> MARK(X2) 8.09/2.90 MARK(half(X)) -> A__HALF(mark(X)) 8.09/2.90 MARK(half(X)) -> MARK(X) 8.09/2.90 MARK(cons(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(recip(X)) -> MARK(X) 8.09/2.90 MARK(s(X)) -> MARK(X) 8.09/2.90 8.09/2.90 The TRS R consists of the following rules: 8.09/2.90 8.09/2.90 a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) 8.09/2.90 a__sqr(0) -> 0 8.09/2.90 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) 8.09/2.90 a__dbl(0) -> 0 8.09/2.90 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) 8.09/2.90 a__add(0, X) -> mark(X) 8.09/2.90 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 8.09/2.90 a__first(0, X) -> nil 8.09/2.90 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 8.09/2.90 a__half(0) -> 0 8.09/2.90 a__half(s(0)) -> 0 8.09/2.90 a__half(s(s(X))) -> s(a__half(mark(X))) 8.09/2.90 a__half(dbl(X)) -> mark(X) 8.09/2.90 mark(terms(X)) -> a__terms(mark(X)) 8.09/2.90 mark(sqr(X)) -> a__sqr(mark(X)) 8.09/2.90 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 8.09/2.90 mark(dbl(X)) -> a__dbl(mark(X)) 8.09/2.90 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 8.09/2.90 mark(half(X)) -> a__half(mark(X)) 8.09/2.90 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.09/2.90 mark(recip(X)) -> recip(mark(X)) 8.09/2.90 mark(s(X)) -> s(mark(X)) 8.09/2.90 mark(0) -> 0 8.09/2.90 mark(nil) -> nil 8.09/2.90 a__terms(X) -> terms(X) 8.09/2.90 a__sqr(X) -> sqr(X) 8.09/2.90 a__add(X1, X2) -> add(X1, X2) 8.09/2.90 a__dbl(X) -> dbl(X) 8.09/2.90 a__first(X1, X2) -> first(X1, X2) 8.09/2.90 a__half(X) -> half(X) 8.09/2.90 8.09/2.90 The set Q consists of the following terms: 8.09/2.90 8.09/2.90 a__terms(x0) 8.09/2.90 mark(terms(x0)) 8.09/2.90 mark(sqr(x0)) 8.09/2.90 mark(add(x0, x1)) 8.09/2.90 mark(dbl(x0)) 8.09/2.90 mark(first(x0, x1)) 8.09/2.90 mark(half(x0)) 8.09/2.90 mark(cons(x0, x1)) 8.09/2.90 mark(recip(x0)) 8.09/2.90 mark(s(x0)) 8.09/2.90 mark(0) 8.09/2.90 mark(nil) 8.09/2.90 a__sqr(x0) 8.09/2.90 a__add(x0, x1) 8.09/2.90 a__dbl(x0) 8.09/2.90 a__first(x0, x1) 8.09/2.90 a__half(x0) 8.09/2.90 8.09/2.90 We have to consider all minimal (P,Q,R)-chains. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (3) QDPOrderProof (EQUIVALENT) 8.09/2.90 We use the reduction pair processor [LPAR04,JAR06]. 8.09/2.90 8.09/2.90 8.09/2.90 The following pairs can be oriented strictly and are deleted. 8.09/2.90 8.09/2.90 A__TERMS(N) -> MARK(N) 8.09/2.90 A__SQR(s(X)) -> A__ADD(a__sqr(mark(X)), a__dbl(mark(X))) 8.09/2.90 A__SQR(s(X)) -> A__SQR(mark(X)) 8.09/2.90 A__SQR(s(X)) -> MARK(X) 8.09/2.90 A__SQR(s(X)) -> A__DBL(mark(X)) 8.09/2.90 A__DBL(s(X)) -> A__DBL(mark(X)) 8.09/2.90 A__DBL(s(X)) -> MARK(X) 8.09/2.90 A__ADD(0, X) -> MARK(X) 8.09/2.90 A__ADD(s(X), Y) -> A__ADD(mark(X), mark(Y)) 8.09/2.90 A__ADD(s(X), Y) -> MARK(X) 8.09/2.90 A__ADD(s(X), Y) -> MARK(Y) 8.09/2.90 A__HALF(s(s(X))) -> A__HALF(mark(X)) 8.09/2.90 A__HALF(s(s(X))) -> MARK(X) 8.09/2.90 A__HALF(dbl(X)) -> MARK(X) 8.09/2.90 MARK(terms(X)) -> A__TERMS(mark(X)) 8.09/2.90 MARK(terms(X)) -> MARK(X) 8.09/2.90 MARK(sqr(X)) -> A__SQR(mark(X)) 8.09/2.90 MARK(sqr(X)) -> MARK(X) 8.09/2.90 MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2)) 8.09/2.90 MARK(add(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(add(X1, X2)) -> MARK(X2) 8.09/2.90 MARK(dbl(X)) -> A__DBL(mark(X)) 8.09/2.90 MARK(dbl(X)) -> MARK(X) 8.09/2.90 MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2)) 8.09/2.90 MARK(first(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(first(X1, X2)) -> MARK(X2) 8.09/2.90 MARK(s(X)) -> MARK(X) 8.09/2.90 The remaining pairs can at least be oriented weakly. 8.09/2.90 Used ordering: Combined order from the following AFS and order. 8.09/2.90 A__TERMS(x1) = A__TERMS(x1) 8.09/2.90 8.09/2.90 A__SQR(x1) = A__SQR(x1) 8.09/2.90 8.09/2.90 mark(x1) = x1 8.09/2.90 8.09/2.90 MARK(x1) = MARK(x1) 8.09/2.90 8.09/2.90 s(x1) = s(x1) 8.09/2.90 8.09/2.90 A__ADD(x1, x2) = A__ADD(x1, x2) 8.09/2.90 8.09/2.90 a__sqr(x1) = a__sqr(x1) 8.09/2.90 8.09/2.90 a__dbl(x1) = a__dbl(x1) 8.09/2.90 8.09/2.90 A__DBL(x1) = A__DBL(x1) 8.09/2.90 8.09/2.90 0 = 0 8.09/2.90 8.09/2.90 A__FIRST(x1, x2) = A__FIRST(x2) 8.09/2.90 8.09/2.90 cons(x1, x2) = x1 8.09/2.90 8.09/2.90 A__HALF(x1) = A__HALF(x1) 8.09/2.90 8.09/2.90 dbl(x1) = dbl(x1) 8.09/2.90 8.09/2.90 terms(x1) = terms(x1) 8.09/2.90 8.09/2.90 sqr(x1) = sqr(x1) 8.09/2.90 8.09/2.90 add(x1, x2) = add(x1, x2) 8.09/2.90 8.09/2.90 first(x1, x2) = first(x1, x2) 8.09/2.90 8.09/2.90 half(x1) = x1 8.09/2.90 8.09/2.90 recip(x1) = x1 8.09/2.90 8.09/2.90 a__terms(x1) = a__terms(x1) 8.09/2.90 8.09/2.90 a__add(x1, x2) = a__add(x1, x2) 8.09/2.90 8.09/2.90 a__half(x1) = x1 8.09/2.90 8.09/2.90 a__first(x1, x2) = a__first(x1, x2) 8.09/2.90 8.09/2.90 nil = nil 8.09/2.90 8.09/2.90 8.09/2.90 Recursive path order with status [RPO]. 8.09/2.90 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] 8.09/2.90 [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 8.09/2.90 [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] 8.09/2.90 [A__TERMS_1, A__SQR_1, a__sqr_1, a__dbl_1, 0, dbl_1, terms_1, sqr_1, a__terms_1] > nil 8.09/2.90 [first_2, a__first_2] > [MARK_1, A__FIRST_1, A__HALF_1] 8.09/2.90 [first_2, a__first_2] > nil 8.09/2.90 8.09/2.90 Status: A__TERMS_1: [1] 8.09/2.90 A__SQR_1: [1] 8.09/2.90 MARK_1: multiset status 8.09/2.90 s_1: [1] 8.09/2.90 A__ADD_2: multiset status 8.09/2.90 a__sqr_1: [1] 8.09/2.90 a__dbl_1: [1] 8.09/2.90 A__DBL_1: [1] 8.09/2.90 0: multiset status 8.09/2.90 A__FIRST_1: multiset status 8.09/2.90 A__HALF_1: multiset status 8.09/2.90 dbl_1: [1] 8.09/2.90 terms_1: [1] 8.09/2.90 sqr_1: [1] 8.09/2.90 add_2: [2,1] 8.09/2.90 first_2: [2,1] 8.09/2.90 a__terms_1: [1] 8.09/2.90 a__add_2: [2,1] 8.09/2.90 a__first_2: [2,1] 8.09/2.90 nil: multiset status 8.09/2.90 8.09/2.90 8.09/2.90 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.09/2.90 8.09/2.90 mark(terms(X)) -> a__terms(mark(X)) 8.09/2.90 mark(sqr(X)) -> a__sqr(mark(X)) 8.09/2.90 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 8.09/2.90 a__add(0, X) -> mark(X) 8.09/2.90 mark(half(X)) -> a__half(mark(X)) 8.09/2.90 a__half(dbl(X)) -> mark(X) 8.09/2.90 mark(dbl(X)) -> a__dbl(mark(X)) 8.09/2.90 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 8.09/2.90 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.09/2.90 mark(recip(X)) -> recip(mark(X)) 8.09/2.90 mark(s(X)) -> s(mark(X)) 8.09/2.90 mark(0) -> 0 8.09/2.90 mark(nil) -> nil 8.09/2.90 a__sqr(0) -> 0 8.09/2.90 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) 8.09/2.90 a__sqr(X) -> sqr(X) 8.09/2.90 a__dbl(0) -> 0 8.09/2.90 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) 8.09/2.90 a__dbl(X) -> dbl(X) 8.09/2.90 a__terms(X) -> terms(X) 8.09/2.90 a__add(X1, X2) -> add(X1, X2) 8.09/2.90 a__half(0) -> 0 8.09/2.90 a__half(s(0)) -> 0 8.09/2.90 a__half(X) -> half(X) 8.09/2.90 a__first(0, X) -> nil 8.09/2.90 a__first(X1, X2) -> first(X1, X2) 8.09/2.90 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 8.09/2.90 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 8.09/2.90 a__half(s(s(X))) -> s(a__half(mark(X))) 8.09/2.90 a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) 8.09/2.90 8.09/2.90 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (4) 8.09/2.90 Obligation: 8.09/2.90 Q DP problem: 8.09/2.90 The TRS P consists of the following rules: 8.09/2.90 8.09/2.90 A__TERMS(N) -> A__SQR(mark(N)) 8.09/2.90 A__FIRST(s(X), cons(Y, Z)) -> MARK(Y) 8.09/2.90 MARK(half(X)) -> A__HALF(mark(X)) 8.09/2.90 MARK(half(X)) -> MARK(X) 8.09/2.90 MARK(cons(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(recip(X)) -> MARK(X) 8.09/2.90 8.09/2.90 The TRS R consists of the following rules: 8.09/2.90 8.09/2.90 a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) 8.09/2.90 a__sqr(0) -> 0 8.09/2.90 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) 8.09/2.90 a__dbl(0) -> 0 8.09/2.90 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) 8.09/2.90 a__add(0, X) -> mark(X) 8.09/2.90 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 8.09/2.90 a__first(0, X) -> nil 8.09/2.90 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 8.09/2.90 a__half(0) -> 0 8.09/2.90 a__half(s(0)) -> 0 8.09/2.90 a__half(s(s(X))) -> s(a__half(mark(X))) 8.09/2.90 a__half(dbl(X)) -> mark(X) 8.09/2.90 mark(terms(X)) -> a__terms(mark(X)) 8.09/2.90 mark(sqr(X)) -> a__sqr(mark(X)) 8.09/2.90 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 8.09/2.90 mark(dbl(X)) -> a__dbl(mark(X)) 8.09/2.90 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 8.09/2.90 mark(half(X)) -> a__half(mark(X)) 8.09/2.90 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.09/2.90 mark(recip(X)) -> recip(mark(X)) 8.09/2.90 mark(s(X)) -> s(mark(X)) 8.09/2.90 mark(0) -> 0 8.09/2.90 mark(nil) -> nil 8.09/2.90 a__terms(X) -> terms(X) 8.09/2.90 a__sqr(X) -> sqr(X) 8.09/2.90 a__add(X1, X2) -> add(X1, X2) 8.09/2.90 a__dbl(X) -> dbl(X) 8.09/2.90 a__first(X1, X2) -> first(X1, X2) 8.09/2.90 a__half(X) -> half(X) 8.09/2.90 8.09/2.90 The set Q consists of the following terms: 8.09/2.90 8.09/2.90 a__terms(x0) 8.09/2.90 mark(terms(x0)) 8.09/2.90 mark(sqr(x0)) 8.09/2.90 mark(add(x0, x1)) 8.09/2.90 mark(dbl(x0)) 8.09/2.90 mark(first(x0, x1)) 8.09/2.90 mark(half(x0)) 8.09/2.90 mark(cons(x0, x1)) 8.09/2.90 mark(recip(x0)) 8.09/2.90 mark(s(x0)) 8.09/2.90 mark(0) 8.09/2.90 mark(nil) 8.09/2.90 a__sqr(x0) 8.09/2.90 a__add(x0, x1) 8.09/2.90 a__dbl(x0) 8.09/2.90 a__first(x0, x1) 8.09/2.90 a__half(x0) 8.09/2.90 8.09/2.90 We have to consider all minimal (P,Q,R)-chains. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (5) DependencyGraphProof (EQUIVALENT) 8.09/2.90 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (6) 8.09/2.90 Obligation: 8.09/2.90 Q DP problem: 8.09/2.90 The TRS P consists of the following rules: 8.09/2.90 8.09/2.90 MARK(cons(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(half(X)) -> MARK(X) 8.09/2.90 MARK(recip(X)) -> MARK(X) 8.09/2.90 8.09/2.90 The TRS R consists of the following rules: 8.09/2.90 8.09/2.90 a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N))) 8.09/2.90 a__sqr(0) -> 0 8.09/2.90 a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)), a__dbl(mark(X)))) 8.09/2.90 a__dbl(0) -> 0 8.09/2.90 a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) 8.09/2.90 a__add(0, X) -> mark(X) 8.09/2.90 a__add(s(X), Y) -> s(a__add(mark(X), mark(Y))) 8.09/2.90 a__first(0, X) -> nil 8.09/2.90 a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) 8.09/2.90 a__half(0) -> 0 8.09/2.90 a__half(s(0)) -> 0 8.09/2.90 a__half(s(s(X))) -> s(a__half(mark(X))) 8.09/2.90 a__half(dbl(X)) -> mark(X) 8.09/2.90 mark(terms(X)) -> a__terms(mark(X)) 8.09/2.90 mark(sqr(X)) -> a__sqr(mark(X)) 8.09/2.90 mark(add(X1, X2)) -> a__add(mark(X1), mark(X2)) 8.09/2.90 mark(dbl(X)) -> a__dbl(mark(X)) 8.09/2.90 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 8.09/2.90 mark(half(X)) -> a__half(mark(X)) 8.09/2.90 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.09/2.90 mark(recip(X)) -> recip(mark(X)) 8.09/2.90 mark(s(X)) -> s(mark(X)) 8.09/2.90 mark(0) -> 0 8.09/2.90 mark(nil) -> nil 8.09/2.90 a__terms(X) -> terms(X) 8.09/2.90 a__sqr(X) -> sqr(X) 8.09/2.90 a__add(X1, X2) -> add(X1, X2) 8.09/2.90 a__dbl(X) -> dbl(X) 8.09/2.90 a__first(X1, X2) -> first(X1, X2) 8.09/2.90 a__half(X) -> half(X) 8.09/2.90 8.09/2.90 The set Q consists of the following terms: 8.09/2.90 8.09/2.90 a__terms(x0) 8.09/2.90 mark(terms(x0)) 8.09/2.90 mark(sqr(x0)) 8.09/2.90 mark(add(x0, x1)) 8.09/2.90 mark(dbl(x0)) 8.09/2.90 mark(first(x0, x1)) 8.09/2.90 mark(half(x0)) 8.09/2.90 mark(cons(x0, x1)) 8.09/2.90 mark(recip(x0)) 8.09/2.90 mark(s(x0)) 8.09/2.90 mark(0) 8.09/2.90 mark(nil) 8.09/2.90 a__sqr(x0) 8.09/2.90 a__add(x0, x1) 8.09/2.90 a__dbl(x0) 8.09/2.90 a__first(x0, x1) 8.09/2.90 a__half(x0) 8.09/2.90 8.09/2.90 We have to consider all minimal (P,Q,R)-chains. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (7) UsableRulesProof (EQUIVALENT) 8.09/2.90 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (8) 8.09/2.90 Obligation: 8.09/2.90 Q DP problem: 8.09/2.90 The TRS P consists of the following rules: 8.09/2.90 8.09/2.90 MARK(cons(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(half(X)) -> MARK(X) 8.09/2.90 MARK(recip(X)) -> MARK(X) 8.09/2.90 8.09/2.90 R is empty. 8.09/2.90 The set Q consists of the following terms: 8.09/2.90 8.09/2.90 a__terms(x0) 8.09/2.90 mark(terms(x0)) 8.09/2.90 mark(sqr(x0)) 8.09/2.90 mark(add(x0, x1)) 8.09/2.90 mark(dbl(x0)) 8.09/2.90 mark(first(x0, x1)) 8.09/2.90 mark(half(x0)) 8.09/2.90 mark(cons(x0, x1)) 8.09/2.90 mark(recip(x0)) 8.09/2.90 mark(s(x0)) 8.09/2.90 mark(0) 8.09/2.90 mark(nil) 8.09/2.90 a__sqr(x0) 8.09/2.90 a__add(x0, x1) 8.09/2.90 a__dbl(x0) 8.09/2.90 a__first(x0, x1) 8.09/2.90 a__half(x0) 8.09/2.90 8.09/2.90 We have to consider all minimal (P,Q,R)-chains. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (9) QReductionProof (EQUIVALENT) 8.09/2.90 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.09/2.90 8.09/2.90 a__terms(x0) 8.09/2.90 mark(terms(x0)) 8.09/2.90 mark(sqr(x0)) 8.09/2.90 mark(add(x0, x1)) 8.09/2.90 mark(dbl(x0)) 8.09/2.90 mark(first(x0, x1)) 8.09/2.90 mark(half(x0)) 8.09/2.90 mark(cons(x0, x1)) 8.09/2.90 mark(recip(x0)) 8.09/2.90 mark(s(x0)) 8.09/2.90 mark(0) 8.09/2.90 mark(nil) 8.09/2.90 a__sqr(x0) 8.09/2.90 a__add(x0, x1) 8.09/2.90 a__dbl(x0) 8.09/2.90 a__first(x0, x1) 8.09/2.90 a__half(x0) 8.09/2.90 8.09/2.90 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (10) 8.09/2.90 Obligation: 8.09/2.90 Q DP problem: 8.09/2.90 The TRS P consists of the following rules: 8.09/2.90 8.09/2.90 MARK(cons(X1, X2)) -> MARK(X1) 8.09/2.90 MARK(half(X)) -> MARK(X) 8.09/2.90 MARK(recip(X)) -> MARK(X) 8.09/2.90 8.09/2.90 R is empty. 8.09/2.90 Q is empty. 8.09/2.90 We have to consider all minimal (P,Q,R)-chains. 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (11) QDPSizeChangeProof (EQUIVALENT) 8.09/2.90 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. 8.09/2.90 8.09/2.90 From the DPs we obtained the following set of size-change graphs: 8.09/2.90 *MARK(cons(X1, X2)) -> MARK(X1) 8.09/2.90 The graph contains the following edges 1 > 1 8.09/2.90 8.09/2.90 8.09/2.90 *MARK(half(X)) -> MARK(X) 8.09/2.90 The graph contains the following edges 1 > 1 8.09/2.90 8.09/2.90 8.09/2.90 *MARK(recip(X)) -> MARK(X) 8.09/2.90 The graph contains the following edges 1 > 1 8.09/2.90 8.09/2.90 8.09/2.90 ---------------------------------------- 8.09/2.90 8.09/2.90 (12) 8.09/2.90 YES 8.23/2.95 EOF