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