4.10/2.05 YES 4.10/2.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.10/2.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.10/2.07 4.10/2.07 4.10/2.07 Termination w.r.t. Q of the given QTRS could be proven: 4.10/2.07 4.10/2.07 (0) QTRS 4.10/2.07 (1) QTRSToCSRProof [SOUND, 0 ms] 4.10/2.07 (2) CSR 4.10/2.07 (3) CSRInnermostProof [EQUIVALENT, 1 ms] 4.10/2.07 (4) CSR 4.10/2.07 (5) CSDependencyPairsProof [EQUIVALENT, 0 ms] 4.10/2.07 (6) QCSDP 4.10/2.07 (7) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 4.10/2.07 (8) AND 4.10/2.07 (9) QCSDP 4.10/2.07 (10) QCSDPSubtermProof [EQUIVALENT, 21 ms] 4.10/2.07 (11) QCSDP 4.10/2.07 (12) PIsEmptyProof [EQUIVALENT, 0 ms] 4.10/2.07 (13) YES 4.10/2.07 (14) QCSDP 4.10/2.07 (15) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.10/2.07 (16) QCSDP 4.10/2.07 (17) PIsEmptyProof [EQUIVALENT, 0 ms] 4.10/2.07 (18) YES 4.10/2.07 (19) QCSDP 4.10/2.07 (20) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.10/2.07 (21) QCSDP 4.10/2.07 (22) PIsEmptyProof [EQUIVALENT, 0 ms] 4.10/2.07 (23) YES 4.10/2.07 (24) QCSDP 4.10/2.07 (25) QCSDPSubtermProof [EQUIVALENT, 3 ms] 4.10/2.07 (26) QCSDP 4.10/2.07 (27) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 4.10/2.07 (28) TRUE 4.10/2.07 4.10/2.07 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (0) 4.10/2.07 Obligation: 4.10/2.07 Q restricted rewrite system: 4.10/2.07 The TRS R consists of the following rules: 4.10/2.07 4.10/2.07 active(from(X)) -> mark(cons(X, from(s(X)))) 4.10/2.07 active(2ndspos(0, Z)) -> mark(rnil) 4.10/2.07 active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z))) 4.10/2.07 active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z))) 4.10/2.07 active(2ndsneg(0, Z)) -> mark(rnil) 4.10/2.07 active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z))) 4.10/2.07 active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z))) 4.10/2.07 active(pi(X)) -> mark(2ndspos(X, from(0))) 4.10/2.07 active(plus(0, Y)) -> mark(Y) 4.10/2.07 active(plus(s(X), Y)) -> mark(s(plus(X, Y))) 4.10/2.07 active(times(0, Y)) -> mark(0) 4.10/2.07 active(times(s(X), Y)) -> mark(plus(Y, times(X, Y))) 4.10/2.07 active(square(X)) -> mark(times(X, X)) 4.10/2.07 active(s(X)) -> s(active(X)) 4.10/2.07 active(posrecip(X)) -> posrecip(active(X)) 4.10/2.07 active(negrecip(X)) -> negrecip(active(X)) 4.10/2.07 active(cons(X1, X2)) -> cons(active(X1), X2) 4.10/2.07 active(cons2(X1, X2)) -> cons2(X1, active(X2)) 4.10/2.07 active(rcons(X1, X2)) -> rcons(active(X1), X2) 4.10/2.07 active(rcons(X1, X2)) -> rcons(X1, active(X2)) 4.10/2.07 active(from(X)) -> from(active(X)) 4.10/2.07 active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2) 4.10/2.07 active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2)) 4.10/2.07 active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2) 4.10/2.07 active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2)) 4.10/2.07 active(pi(X)) -> pi(active(X)) 4.10/2.07 active(plus(X1, X2)) -> plus(active(X1), X2) 4.10/2.07 active(plus(X1, X2)) -> plus(X1, active(X2)) 4.10/2.07 active(times(X1, X2)) -> times(active(X1), X2) 4.10/2.07 active(times(X1, X2)) -> times(X1, active(X2)) 4.10/2.07 active(square(X)) -> square(active(X)) 4.10/2.07 s(mark(X)) -> mark(s(X)) 4.10/2.07 posrecip(mark(X)) -> mark(posrecip(X)) 4.10/2.07 negrecip(mark(X)) -> mark(negrecip(X)) 4.10/2.07 cons(mark(X1), X2) -> mark(cons(X1, X2)) 4.10/2.07 cons2(X1, mark(X2)) -> mark(cons2(X1, X2)) 4.10/2.07 rcons(mark(X1), X2) -> mark(rcons(X1, X2)) 4.10/2.07 rcons(X1, mark(X2)) -> mark(rcons(X1, X2)) 4.10/2.07 from(mark(X)) -> mark(from(X)) 4.10/2.07 2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2)) 4.10/2.07 2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2)) 4.10/2.07 2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2)) 4.10/2.07 2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2)) 4.10/2.07 pi(mark(X)) -> mark(pi(X)) 4.10/2.07 plus(mark(X1), X2) -> mark(plus(X1, X2)) 4.10/2.07 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 4.10/2.07 times(mark(X1), X2) -> mark(times(X1, X2)) 4.10/2.07 times(X1, mark(X2)) -> mark(times(X1, X2)) 4.10/2.07 square(mark(X)) -> mark(square(X)) 4.10/2.07 proper(0) -> ok(0) 4.10/2.07 proper(s(X)) -> s(proper(X)) 4.10/2.07 proper(posrecip(X)) -> posrecip(proper(X)) 4.10/2.07 proper(negrecip(X)) -> negrecip(proper(X)) 4.10/2.07 proper(nil) -> ok(nil) 4.10/2.07 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 4.10/2.07 proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2)) 4.10/2.07 proper(rnil) -> ok(rnil) 4.10/2.07 proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2)) 4.10/2.07 proper(from(X)) -> from(proper(X)) 4.10/2.07 proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2)) 4.10/2.07 proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2)) 4.10/2.07 proper(pi(X)) -> pi(proper(X)) 4.10/2.07 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 4.10/2.07 proper(times(X1, X2)) -> times(proper(X1), proper(X2)) 4.10/2.07 proper(square(X)) -> square(proper(X)) 4.10/2.07 s(ok(X)) -> ok(s(X)) 4.10/2.07 posrecip(ok(X)) -> ok(posrecip(X)) 4.10/2.07 negrecip(ok(X)) -> ok(negrecip(X)) 4.10/2.07 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 4.10/2.07 cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2)) 4.10/2.07 rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2)) 4.10/2.07 from(ok(X)) -> ok(from(X)) 4.10/2.07 2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2)) 4.10/2.07 2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2)) 4.10/2.07 pi(ok(X)) -> ok(pi(X)) 4.10/2.07 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 4.10/2.07 times(ok(X1), ok(X2)) -> ok(times(X1, X2)) 4.10/2.07 square(ok(X)) -> ok(square(X)) 4.10/2.07 top(mark(X)) -> top(proper(X)) 4.10/2.07 top(ok(X)) -> top(active(X)) 4.10/2.07 4.10/2.07 The set Q consists of the following terms: 4.10/2.07 4.10/2.07 active(from(x0)) 4.10/2.07 active(pi(x0)) 4.10/2.07 active(square(x0)) 4.10/2.07 active(s(x0)) 4.10/2.07 active(posrecip(x0)) 4.10/2.07 active(negrecip(x0)) 4.10/2.07 active(cons(x0, x1)) 4.10/2.07 active(cons2(x0, x1)) 4.10/2.07 active(rcons(x0, x1)) 4.10/2.07 active(2ndspos(x0, x1)) 4.10/2.07 active(2ndsneg(x0, x1)) 4.10/2.07 active(plus(x0, x1)) 4.10/2.07 active(times(x0, x1)) 4.10/2.07 s(mark(x0)) 4.10/2.07 posrecip(mark(x0)) 4.10/2.07 negrecip(mark(x0)) 4.10/2.07 cons(mark(x0), x1) 4.10/2.07 cons2(x0, mark(x1)) 4.10/2.07 rcons(mark(x0), x1) 4.10/2.07 rcons(x0, mark(x1)) 4.10/2.07 from(mark(x0)) 4.10/2.07 2ndspos(mark(x0), x1) 4.10/2.07 2ndspos(x0, mark(x1)) 4.10/2.07 2ndsneg(mark(x0), x1) 4.10/2.07 2ndsneg(x0, mark(x1)) 4.10/2.07 pi(mark(x0)) 4.10/2.07 plus(mark(x0), x1) 4.10/2.07 plus(x0, mark(x1)) 4.10/2.07 times(mark(x0), x1) 4.10/2.07 times(x0, mark(x1)) 4.10/2.07 square(mark(x0)) 4.10/2.07 proper(0) 4.10/2.07 proper(s(x0)) 4.10/2.07 proper(posrecip(x0)) 4.10/2.07 proper(negrecip(x0)) 4.10/2.07 proper(nil) 4.10/2.07 proper(cons(x0, x1)) 4.10/2.07 proper(cons2(x0, x1)) 4.10/2.07 proper(rnil) 4.10/2.07 proper(rcons(x0, x1)) 4.10/2.07 proper(from(x0)) 4.10/2.07 proper(2ndspos(x0, x1)) 4.10/2.07 proper(2ndsneg(x0, x1)) 4.10/2.07 proper(pi(x0)) 4.10/2.07 proper(plus(x0, x1)) 4.10/2.07 proper(times(x0, x1)) 4.10/2.07 proper(square(x0)) 4.10/2.07 s(ok(x0)) 4.10/2.07 posrecip(ok(x0)) 4.10/2.07 negrecip(ok(x0)) 4.10/2.07 cons(ok(x0), ok(x1)) 4.10/2.07 cons2(ok(x0), ok(x1)) 4.10/2.07 rcons(ok(x0), ok(x1)) 4.10/2.07 from(ok(x0)) 4.10/2.07 2ndspos(ok(x0), ok(x1)) 4.10/2.07 2ndsneg(ok(x0), ok(x1)) 4.10/2.07 pi(ok(x0)) 4.10/2.07 plus(ok(x0), ok(x1)) 4.10/2.07 times(ok(x0), ok(x1)) 4.10/2.07 square(ok(x0)) 4.10/2.07 top(mark(x0)) 4.10/2.07 top(ok(x0)) 4.10/2.07 4.10/2.07 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (1) QTRSToCSRProof (SOUND) 4.10/2.07 The following Q TRS is given: Q restricted rewrite system: 4.10/2.07 The TRS R consists of the following rules: 4.10/2.07 4.10/2.07 active(from(X)) -> mark(cons(X, from(s(X)))) 4.10/2.07 active(2ndspos(0, Z)) -> mark(rnil) 4.10/2.07 active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z))) 4.10/2.07 active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z))) 4.10/2.07 active(2ndsneg(0, Z)) -> mark(rnil) 4.10/2.07 active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z))) 4.10/2.07 active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z))) 4.10/2.07 active(pi(X)) -> mark(2ndspos(X, from(0))) 4.10/2.07 active(plus(0, Y)) -> mark(Y) 4.10/2.07 active(plus(s(X), Y)) -> mark(s(plus(X, Y))) 4.10/2.07 active(times(0, Y)) -> mark(0) 4.10/2.07 active(times(s(X), Y)) -> mark(plus(Y, times(X, Y))) 4.10/2.07 active(square(X)) -> mark(times(X, X)) 4.10/2.07 active(s(X)) -> s(active(X)) 4.10/2.07 active(posrecip(X)) -> posrecip(active(X)) 4.10/2.07 active(negrecip(X)) -> negrecip(active(X)) 4.10/2.07 active(cons(X1, X2)) -> cons(active(X1), X2) 4.10/2.07 active(cons2(X1, X2)) -> cons2(X1, active(X2)) 4.10/2.07 active(rcons(X1, X2)) -> rcons(active(X1), X2) 4.10/2.07 active(rcons(X1, X2)) -> rcons(X1, active(X2)) 4.10/2.07 active(from(X)) -> from(active(X)) 4.10/2.07 active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2) 4.10/2.07 active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2)) 4.10/2.07 active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2) 4.10/2.07 active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2)) 4.10/2.07 active(pi(X)) -> pi(active(X)) 4.10/2.07 active(plus(X1, X2)) -> plus(active(X1), X2) 4.10/2.07 active(plus(X1, X2)) -> plus(X1, active(X2)) 4.10/2.07 active(times(X1, X2)) -> times(active(X1), X2) 4.10/2.07 active(times(X1, X2)) -> times(X1, active(X2)) 4.10/2.07 active(square(X)) -> square(active(X)) 4.10/2.07 s(mark(X)) -> mark(s(X)) 4.10/2.07 posrecip(mark(X)) -> mark(posrecip(X)) 4.10/2.07 negrecip(mark(X)) -> mark(negrecip(X)) 4.10/2.07 cons(mark(X1), X2) -> mark(cons(X1, X2)) 4.10/2.07 cons2(X1, mark(X2)) -> mark(cons2(X1, X2)) 4.10/2.07 rcons(mark(X1), X2) -> mark(rcons(X1, X2)) 4.10/2.07 rcons(X1, mark(X2)) -> mark(rcons(X1, X2)) 4.10/2.07 from(mark(X)) -> mark(from(X)) 4.10/2.07 2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2)) 4.10/2.07 2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2)) 4.10/2.07 2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2)) 4.10/2.07 2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2)) 4.10/2.07 pi(mark(X)) -> mark(pi(X)) 4.10/2.07 plus(mark(X1), X2) -> mark(plus(X1, X2)) 4.10/2.07 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 4.10/2.07 times(mark(X1), X2) -> mark(times(X1, X2)) 4.10/2.07 times(X1, mark(X2)) -> mark(times(X1, X2)) 4.10/2.07 square(mark(X)) -> mark(square(X)) 4.10/2.07 proper(0) -> ok(0) 4.10/2.07 proper(s(X)) -> s(proper(X)) 4.10/2.07 proper(posrecip(X)) -> posrecip(proper(X)) 4.10/2.07 proper(negrecip(X)) -> negrecip(proper(X)) 4.10/2.07 proper(nil) -> ok(nil) 4.10/2.07 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 4.10/2.07 proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2)) 4.10/2.07 proper(rnil) -> ok(rnil) 4.10/2.07 proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2)) 4.10/2.07 proper(from(X)) -> from(proper(X)) 4.10/2.07 proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2)) 4.10/2.07 proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2)) 4.10/2.07 proper(pi(X)) -> pi(proper(X)) 4.10/2.07 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 4.10/2.07 proper(times(X1, X2)) -> times(proper(X1), proper(X2)) 4.10/2.07 proper(square(X)) -> square(proper(X)) 4.10/2.07 s(ok(X)) -> ok(s(X)) 4.10/2.07 posrecip(ok(X)) -> ok(posrecip(X)) 4.10/2.07 negrecip(ok(X)) -> ok(negrecip(X)) 4.10/2.07 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 4.10/2.07 cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2)) 4.10/2.07 rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2)) 4.10/2.07 from(ok(X)) -> ok(from(X)) 4.10/2.07 2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2)) 4.10/2.07 2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2)) 4.10/2.07 pi(ok(X)) -> ok(pi(X)) 4.10/2.07 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 4.10/2.07 times(ok(X1), ok(X2)) -> ok(times(X1, X2)) 4.10/2.07 square(ok(X)) -> ok(square(X)) 4.10/2.07 top(mark(X)) -> top(proper(X)) 4.10/2.07 top(ok(X)) -> top(active(X)) 4.10/2.07 4.10/2.07 The set Q consists of the following terms: 4.10/2.07 4.10/2.07 active(from(x0)) 4.10/2.07 active(pi(x0)) 4.10/2.07 active(square(x0)) 4.10/2.07 active(s(x0)) 4.10/2.07 active(posrecip(x0)) 4.10/2.07 active(negrecip(x0)) 4.10/2.07 active(cons(x0, x1)) 4.10/2.07 active(cons2(x0, x1)) 4.10/2.07 active(rcons(x0, x1)) 4.10/2.07 active(2ndspos(x0, x1)) 4.10/2.07 active(2ndsneg(x0, x1)) 4.10/2.07 active(plus(x0, x1)) 4.10/2.07 active(times(x0, x1)) 4.10/2.07 s(mark(x0)) 4.10/2.07 posrecip(mark(x0)) 4.10/2.07 negrecip(mark(x0)) 4.10/2.07 cons(mark(x0), x1) 4.10/2.07 cons2(x0, mark(x1)) 4.10/2.07 rcons(mark(x0), x1) 4.10/2.07 rcons(x0, mark(x1)) 4.10/2.07 from(mark(x0)) 4.10/2.07 2ndspos(mark(x0), x1) 4.10/2.07 2ndspos(x0, mark(x1)) 4.10/2.07 2ndsneg(mark(x0), x1) 4.10/2.07 2ndsneg(x0, mark(x1)) 4.10/2.07 pi(mark(x0)) 4.10/2.07 plus(mark(x0), x1) 4.10/2.07 plus(x0, mark(x1)) 4.10/2.07 times(mark(x0), x1) 4.10/2.07 times(x0, mark(x1)) 4.10/2.07 square(mark(x0)) 4.10/2.07 proper(0) 4.10/2.07 proper(s(x0)) 4.10/2.07 proper(posrecip(x0)) 4.10/2.07 proper(negrecip(x0)) 4.10/2.07 proper(nil) 4.10/2.07 proper(cons(x0, x1)) 4.10/2.07 proper(cons2(x0, x1)) 4.10/2.07 proper(rnil) 4.10/2.07 proper(rcons(x0, x1)) 4.10/2.07 proper(from(x0)) 4.10/2.07 proper(2ndspos(x0, x1)) 4.10/2.07 proper(2ndsneg(x0, x1)) 4.10/2.07 proper(pi(x0)) 4.10/2.07 proper(plus(x0, x1)) 4.10/2.07 proper(times(x0, x1)) 4.10/2.07 proper(square(x0)) 4.10/2.07 s(ok(x0)) 4.10/2.07 posrecip(ok(x0)) 4.10/2.07 negrecip(ok(x0)) 4.10/2.07 cons(ok(x0), ok(x1)) 4.10/2.07 cons2(ok(x0), ok(x1)) 4.10/2.07 rcons(ok(x0), ok(x1)) 4.10/2.07 from(ok(x0)) 4.10/2.07 2ndspos(ok(x0), ok(x1)) 4.10/2.07 2ndsneg(ok(x0), ok(x1)) 4.10/2.07 pi(ok(x0)) 4.10/2.07 plus(ok(x0), ok(x1)) 4.10/2.07 times(ok(x0), ok(x1)) 4.10/2.07 square(ok(x0)) 4.10/2.07 top(mark(x0)) 4.10/2.07 top(ok(x0)) 4.10/2.07 4.10/2.07 Special symbols used for the transformation (see [GM04]): 4.10/2.07 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 4.10/2.07 The replacement map contains the following entries: 4.10/2.07 4.10/2.07 from: {1} 4.10/2.07 cons: {1} 4.10/2.07 s: {1} 4.10/2.07 2ndspos: {1, 2} 4.10/2.07 0: empty set 4.10/2.07 rnil: empty set 4.10/2.07 cons2: {2} 4.10/2.07 rcons: {1, 2} 4.10/2.07 posrecip: {1} 4.10/2.07 2ndsneg: {1, 2} 4.10/2.07 negrecip: {1} 4.10/2.07 pi: {1} 4.10/2.07 plus: {1, 2} 4.10/2.07 times: {1, 2} 4.10/2.07 square: {1} 4.10/2.07 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (2) 4.10/2.07 Obligation: 4.10/2.07 Context-sensitive rewrite system: 4.10/2.07 The TRS R consists of the following rules: 4.10/2.07 4.10/2.07 from(X) -> cons(X, from(s(X))) 4.10/2.07 2ndspos(0, Z) -> rnil 4.10/2.07 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.07 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.07 2ndsneg(0, Z) -> rnil 4.10/2.07 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.07 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.07 pi(X) -> 2ndspos(X, from(0)) 4.10/2.07 plus(0, Y) -> Y 4.10/2.07 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.07 times(0, Y) -> 0 4.10/2.07 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.07 square(X) -> times(X, X) 4.10/2.07 4.10/2.07 The replacement map contains the following entries: 4.10/2.07 4.10/2.07 from: {1} 4.10/2.07 cons: {1} 4.10/2.07 s: {1} 4.10/2.07 2ndspos: {1, 2} 4.10/2.07 0: empty set 4.10/2.07 rnil: empty set 4.10/2.07 cons2: {2} 4.10/2.07 rcons: {1, 2} 4.10/2.07 posrecip: {1} 4.10/2.07 2ndsneg: {1, 2} 4.10/2.07 negrecip: {1} 4.10/2.07 pi: {1} 4.10/2.07 plus: {1, 2} 4.10/2.07 times: {1, 2} 4.10/2.07 square: {1} 4.10/2.07 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (3) CSRInnermostProof (EQUIVALENT) 4.10/2.07 The CSR is orthogonal. By [CS_Inn] we can switch to innermost. 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (4) 4.10/2.07 Obligation: 4.10/2.07 Context-sensitive rewrite system: 4.10/2.07 The TRS R consists of the following rules: 4.10/2.07 4.10/2.07 from(X) -> cons(X, from(s(X))) 4.10/2.07 2ndspos(0, Z) -> rnil 4.10/2.07 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.07 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.07 2ndsneg(0, Z) -> rnil 4.10/2.07 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.07 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.07 pi(X) -> 2ndspos(X, from(0)) 4.10/2.07 plus(0, Y) -> Y 4.10/2.07 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.07 times(0, Y) -> 0 4.10/2.07 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.07 square(X) -> times(X, X) 4.10/2.07 4.10/2.07 The replacement map contains the following entries: 4.10/2.07 4.10/2.07 from: {1} 4.10/2.07 cons: {1} 4.10/2.07 s: {1} 4.10/2.07 2ndspos: {1, 2} 4.10/2.07 0: empty set 4.10/2.07 rnil: empty set 4.10/2.07 cons2: {2} 4.10/2.07 rcons: {1, 2} 4.10/2.07 posrecip: {1} 4.10/2.07 2ndsneg: {1, 2} 4.10/2.07 negrecip: {1} 4.10/2.07 pi: {1} 4.10/2.07 plus: {1, 2} 4.10/2.07 times: {1, 2} 4.10/2.07 square: {1} 4.10/2.07 4.10/2.07 4.10/2.07 Innermost Strategy. 4.10/2.07 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (5) CSDependencyPairsProof (EQUIVALENT) 4.10/2.07 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 4.10/2.07 ---------------------------------------- 4.10/2.07 4.10/2.07 (6) 4.10/2.07 Obligation: 4.10/2.07 Q-restricted context-sensitive dependency pair problem: 4.10/2.07 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, 2NDSPOS_2, 2NDSNEG_2, PI_1, FROM_1, PLUS_2, TIMES_2, SQUARE_1} are replacing on all positions. 4.10/2.07 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.07 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.07 The symbols in {U_1} are not replacing on any position. 4.10/2.07 4.10/2.07 The ordinary context-sensitive dependency pairs DP_o are: 4.10/2.07 2NDSPOS(s(N), cons(X, Z)) -> 2NDSPOS(s(N), cons2(X, Z)) 4.10/2.07 2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> 2NDSNEG(N, Z) 4.10/2.07 2NDSNEG(s(N), cons(X, Z)) -> 2NDSNEG(s(N), cons2(X, Z)) 4.10/2.07 2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> 2NDSPOS(N, Z) 4.10/2.07 PI(X) -> 2NDSPOS(X, from(0)) 4.10/2.07 PI(X) -> FROM(0) 4.10/2.07 PLUS(s(X), Y) -> PLUS(X, Y) 4.10/2.07 TIMES(s(X), Y) -> PLUS(Y, times(X, Y)) 4.10/2.07 TIMES(s(X), Y) -> TIMES(X, Y) 4.10/2.07 SQUARE(X) -> TIMES(X, X) 4.10/2.07 4.10/2.07 The collapsing dependency pairs are DP_c: 4.10/2.07 2NDSPOS(s(N), cons(X, Z)) -> Z 4.10/2.07 2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> Z 4.10/2.07 2NDSNEG(s(N), cons(X, Z)) -> Z 4.10/2.07 2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> Z 4.10/2.07 4.10/2.07 4.10/2.07 The hidden terms of R are: 4.10/2.07 4.10/2.07 from(s(x0)) 4.10/2.07 4.10/2.07 Every hiding context is built from: 4.10/2.07 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@7a9b5a64 4.10/2.07 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@77242192 4.10/2.07 4.10/2.07 Hence, the new unhiding pairs DP_u are : 4.10/2.07 2NDSPOS(s(N), cons(X, Z)) -> U(Z) 4.10/2.07 2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> U(Z) 4.10/2.07 2NDSNEG(s(N), cons(X, Z)) -> U(Z) 4.10/2.07 2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> U(Z) 4.10/2.07 U(s(x_0)) -> U(x_0) 4.10/2.07 U(from(x_0)) -> U(x_0) 4.10/2.07 U(from(s(x0))) -> FROM(s(x0)) 4.10/2.07 4.10/2.07 The TRS R consists of the following rules: 4.10/2.07 4.10/2.07 from(X) -> cons(X, from(s(X))) 4.10/2.07 2ndspos(0, Z) -> rnil 4.10/2.07 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.07 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.07 2ndsneg(0, Z) -> rnil 4.10/2.07 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.07 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.07 pi(X) -> 2ndspos(X, from(0)) 4.10/2.07 plus(0, Y) -> Y 4.10/2.07 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.07 times(0, Y) -> 0 4.10/2.07 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.07 square(X) -> times(X, X) 4.10/2.07 4.10/2.07 The set Q consists of the following terms: 4.10/2.07 4.10/2.07 from(x0) 4.10/2.07 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (7) QCSDependencyGraphProof (EQUIVALENT) 4.10/2.08 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 4 SCCs with 8 less nodes. 4.10/2.08 The rules 2NDSPOS(s(z0), cons(z1, z2)) -> 2NDSPOS(s(z0), cons2(z1, z2)) and 2NDSPOS(s(x0), cons(x1, x2)) -> 2NDSPOS(s(x0), cons2(x1, x2)) form no chain, because ECap^mu(2NDSPOS(s(z0), cons2(z1, z2))) = 2NDSPOS(s(z0), cons2(z1, x_1)) does not unify with 2NDSPOS(s(x0), cons(x1, x2)). The rules 2NDSPOS(s(z0), cons(z1, z2)) -> 2NDSPOS(s(z0), cons2(z1, z2)) and 2NDSPOS(s(x0), cons(x1, x2)) -> U(x2) form no chain, because ECap^mu(2NDSPOS(s(z0), cons2(z1, z2))) = 2NDSPOS(s(z0), cons2(z1, x_1)) does not unify with 2NDSPOS(s(x0), cons(x1, x2)). The rules 2NDSNEG(s(z0), cons(z1, z2)) -> 2NDSNEG(s(z0), cons2(z1, z2)) and 2NDSNEG(s(x0), cons(x1, x2)) -> 2NDSNEG(s(x0), cons2(x1, x2)) form no chain, because ECap^mu(2NDSNEG(s(z0), cons2(z1, z2))) = 2NDSNEG(s(z0), cons2(z1, x_1)) does not unify with 2NDSNEG(s(x0), cons(x1, x2)). The rules 2NDSNEG(s(z0), cons(z1, z2)) -> 2NDSNEG(s(z0), cons2(z1, z2)) and 2NDSNEG(s(x0), cons(x1, x2)) -> U(x2) form no chain, because ECap^mu(2NDSNEG(s(z0), cons2(z1, z2))) = 2NDSNEG(s(z0), cons2(z1, x_1)) does not unify with 2NDSNEG(s(x0), cons(x1, x2)). The rules PI(x0) -> 2NDSPOS(x0, from(0)) and 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> 2NDSNEG(z0, z3) form no chain, because ECap^mu_R'(2NDSPOS(s(z0), cons2(z1, cons(z2, z3)))) = 2NDSPOS(s(x_1), cons2(z1, x_3)) does not unify with 2NDSPOS(x0, from(0)). 4.10/2.08 R' = 4.10/2.08 ( cons(X, from(s(X))), from(X)) 4.10/2.08 4.10/2.08 4.10/2.08 The rules PI(x0) -> 2NDSPOS(x0, from(0)) and 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> U(z3) form no chain, because ECap^mu_R'(2NDSPOS(s(z0), cons2(z1, cons(z2, z3)))) = 2NDSPOS(s(x_1), cons2(z1, x_3)) does not unify with 2NDSPOS(x0, from(0)). 4.10/2.08 R' = 4.10/2.08 ( cons(X, from(s(X))), from(X)) 4.10/2.08 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (8) 4.10/2.08 Complex Obligation (AND) 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (9) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 The symbols in {U_1} are not replacing on any position. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 4.10/2.08 U(s(x_0)) -> U(x_0) 4.10/2.08 U(from(x_0)) -> U(x_0) 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (10) QCSDPSubtermProof (EQUIVALENT) 4.10/2.08 We use the subterm processor [DA_EMMES]. 4.10/2.08 4.10/2.08 4.10/2.08 The following pairs can be oriented strictly and are deleted. 4.10/2.08 4.10/2.08 U(s(x_0)) -> U(x_0) 4.10/2.08 U(from(x_0)) -> U(x_0) 4.10/2.08 The remaining pairs can at least be oriented weakly. 4.10/2.08 none 4.10/2.08 Used ordering: Combined order from the following AFS and order. 4.10/2.08 U(x1) = x1 4.10/2.08 4.10/2.08 4.10/2.08 Subterm Order 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (11) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 none 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (12) PIsEmptyProof (EQUIVALENT) 4.10/2.08 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (13) 4.10/2.08 YES 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (14) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, PLUS_2} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 4.10/2.08 PLUS(s(X), Y) -> PLUS(X, Y) 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (15) QCSDPSubtermProof (EQUIVALENT) 4.10/2.08 We use the subterm processor [DA_EMMES]. 4.10/2.08 4.10/2.08 4.10/2.08 The following pairs can be oriented strictly and are deleted. 4.10/2.08 4.10/2.08 PLUS(s(X), Y) -> PLUS(X, Y) 4.10/2.08 The remaining pairs can at least be oriented weakly. 4.10/2.08 none 4.10/2.08 Used ordering: Combined order from the following AFS and order. 4.10/2.08 PLUS(x1, x2) = x1 4.10/2.08 4.10/2.08 4.10/2.08 Subterm Order 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (16) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 none 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (17) PIsEmptyProof (EQUIVALENT) 4.10/2.08 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (18) 4.10/2.08 YES 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (19) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, TIMES_2} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 4.10/2.08 TIMES(s(X), Y) -> TIMES(X, Y) 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (20) QCSDPSubtermProof (EQUIVALENT) 4.10/2.08 We use the subterm processor [DA_EMMES]. 4.10/2.08 4.10/2.08 4.10/2.08 The following pairs can be oriented strictly and are deleted. 4.10/2.08 4.10/2.08 TIMES(s(X), Y) -> TIMES(X, Y) 4.10/2.08 The remaining pairs can at least be oriented weakly. 4.10/2.08 none 4.10/2.08 Used ordering: Combined order from the following AFS and order. 4.10/2.08 TIMES(x1, x2) = x1 4.10/2.08 4.10/2.08 4.10/2.08 Subterm Order 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (21) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 none 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (22) PIsEmptyProof (EQUIVALENT) 4.10/2.08 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (23) 4.10/2.08 YES 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (24) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, 2NDSNEG_2, 2NDSPOS_2} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 4.10/2.08 2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> 2NDSNEG(N, Z) 4.10/2.08 2NDSNEG(s(N), cons(X, Z)) -> 2NDSNEG(s(N), cons2(X, Z)) 4.10/2.08 2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> 2NDSPOS(N, Z) 4.10/2.08 2NDSPOS(s(N), cons(X, Z)) -> 2NDSPOS(s(N), cons2(X, Z)) 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (25) QCSDPSubtermProof (EQUIVALENT) 4.10/2.08 We use the subterm processor [DA_EMMES]. 4.10/2.08 4.10/2.08 4.10/2.08 The following pairs can be oriented strictly and are deleted. 4.10/2.08 4.10/2.08 2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> 2NDSNEG(N, Z) 4.10/2.08 2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> 2NDSPOS(N, Z) 4.10/2.08 The remaining pairs can at least be oriented weakly. 4.10/2.08 4.10/2.08 2NDSNEG(s(N), cons(X, Z)) -> 2NDSNEG(s(N), cons2(X, Z)) 4.10/2.08 2NDSPOS(s(N), cons(X, Z)) -> 2NDSPOS(s(N), cons2(X, Z)) 4.10/2.08 Used ordering: Combined order from the following AFS and order. 4.10/2.08 2NDSNEG(x1, x2) = x1 4.10/2.08 4.10/2.08 2NDSPOS(x1, x2) = x1 4.10/2.08 4.10/2.08 4.10/2.08 Subterm Order 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (26) 4.10/2.08 Obligation: 4.10/2.08 Q-restricted context-sensitive dependency pair problem: 4.10/2.08 The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, 2NDSNEG_2, 2NDSPOS_2} are replacing on all positions. 4.10/2.08 For all symbols f in {cons_2} we have mu(f) = {1}. 4.10/2.08 For all symbols f in {cons2_2} we have mu(f) = {2}. 4.10/2.08 4.10/2.08 The TRS P consists of the following rules: 4.10/2.08 4.10/2.08 2NDSNEG(s(N), cons(X, Z)) -> 2NDSNEG(s(N), cons2(X, Z)) 4.10/2.08 2NDSPOS(s(N), cons(X, Z)) -> 2NDSPOS(s(N), cons2(X, Z)) 4.10/2.08 4.10/2.08 The TRS R consists of the following rules: 4.10/2.08 4.10/2.08 from(X) -> cons(X, from(s(X))) 4.10/2.08 2ndspos(0, Z) -> rnil 4.10/2.08 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, Z)) 4.10/2.08 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z)) 4.10/2.08 2ndsneg(0, Z) -> rnil 4.10/2.08 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, Z)) 4.10/2.08 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z)) 4.10/2.08 pi(X) -> 2ndspos(X, from(0)) 4.10/2.08 plus(0, Y) -> Y 4.10/2.08 plus(s(X), Y) -> s(plus(X, Y)) 4.10/2.08 times(0, Y) -> 0 4.10/2.08 times(s(X), Y) -> plus(Y, times(X, Y)) 4.10/2.08 square(X) -> times(X, X) 4.10/2.08 4.10/2.08 The set Q consists of the following terms: 4.10/2.08 4.10/2.08 from(x0) 4.10/2.08 2ndspos(0, x0) 4.10/2.08 2ndspos(s(x0), cons(x1, x2)) 4.10/2.08 2ndspos(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 2ndsneg(0, x0) 4.10/2.08 2ndsneg(s(x0), cons(x1, x2)) 4.10/2.08 2ndsneg(s(x0), cons2(x1, cons(x2, x3))) 4.10/2.08 pi(x0) 4.10/2.08 plus(0, x0) 4.10/2.08 plus(s(x0), x1) 4.10/2.08 times(0, x0) 4.10/2.08 times(s(x0), x1) 4.10/2.08 square(x0) 4.10/2.08 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (27) QCSDependencyGraphProof (EQUIVALENT) 4.10/2.08 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 4.10/2.08 4.10/2.08 ---------------------------------------- 4.10/2.08 4.10/2.08 (28) 4.10/2.08 TRUE 4.43/2.11 EOF