YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 115 ms] (2) QDP (3) QDPOrderProof [EQUIVALENT, 390 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) QDPOrderProof [EQUIVALENT, 388 ms] (8) QDP (9) QDPOrderProof [EQUIVALENT, 392 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) QDP (13) QDPOrderProof [EQUIVALENT, 402 ms] (14) QDP (15) QDPOrderProof [EQUIVALENT, 487 ms] (16) QDP (17) DependencyGraphProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPOrderProof [EQUIVALENT, 402 ms] (20) QDP (21) QDPOrderProof [EQUIVALENT, 398 ms] (22) QDP (23) QDPOrderProof [EQUIVALENT, 285 ms] (24) QDP (25) QDPOrderProof [EQUIVALENT, 373 ms] (26) QDP (27) QDPOrderProof [EQUIVALENT, 350 ms] (28) QDP (29) QDPOrderProof [EQUIVALENT, 430 ms] (30) QDP (31) QDPOrderProof [EQUIVALENT, 280 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 388 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 418 ms] (36) QDP (37) QDPOrderProof [EQUIVALENT, 357 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 577 ms] (40) QDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) QDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) QDP (45) QReductionProof [EQUIVALENT, 0 ms] (46) QDP (47) QDPSizeChangeProof [EQUIVALENT, 0 ms] (48) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) ---------------------------------------- (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__FROM(X) -> MARK(X) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__PI(X) -> A__2NDSPOS(mark(X), a__from(0)) A__PI(X) -> MARK(X) A__PI(X) -> A__FROM(0) A__PLUS(0, Y) -> MARK(Y) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__SQUARE(X) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(pi(X)) -> A__PI(mark(X)) MARK(pi(X)) -> MARK(X) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(square(X)) -> A__SQUARE(mark(X)) MARK(square(X)) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) 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. MARK(square(X)) -> A__SQUARE(mark(X)) MARK(square(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PI(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(0) = [[0A]] >>> <<< POL(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__SQUARE(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__pi(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__square(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__from(X) -> from(X) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: A__FROM(X) -> MARK(X) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__PI(X) -> A__2NDSPOS(mark(X), a__from(0)) A__PI(X) -> MARK(X) A__PI(X) -> A__FROM(0) A__PLUS(0, Y) -> MARK(Y) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__SQUARE(X) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(pi(X)) -> A__PI(mark(X)) MARK(pi(X)) -> MARK(X) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) 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 2 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(pi(X)) -> A__PI(mark(X)) A__PI(X) -> A__2NDSPOS(mark(X), a__from(0)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) MARK(pi(X)) -> MARK(X) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__PI(X) -> MARK(X) A__PI(X) -> A__FROM(0) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(pi(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[3A]] + [[1A]] * x_1 >>> <<< POL(A__PI(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(0) = [[0A]] >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__pi(x_1)) = [[3A]] + [[1A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[5A]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[5A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__from(X) -> from(X) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(pi(X)) -> A__PI(mark(X)) A__PI(X) -> A__2NDSPOS(mark(X), a__from(0)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__PI(X) -> MARK(X) A__PI(X) -> A__FROM(0) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(pi(X)) -> A__PI(mark(X)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(A__PI(x_1)) = [[0A]] + [[2A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(0) = [[0A]] >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__pi(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> cons(mark(X), from(s(X))) a__from(X) -> from(X) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) A__PI(X) -> A__2NDSPOS(mark(X), a__from(0)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__PI(X) -> MARK(X) A__PI(X) -> A__FROM(0) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: A__FROM(X) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(from(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__FROM(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[1A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__from(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: A__FROM(X) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__FROM(X) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__FROM(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[1A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__from(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(from(X)) -> A__FROM(mark(X)) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__TIMES(s(X), Y) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[4A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[-I]] + [[4A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[-I]] + [[4A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[0A]] + [[4A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[4A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> MARK(X2) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(2ndspos(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[1A]] >>> <<< POL(times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(times(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__square(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__PLUS(s(X), Y) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[1A]] >>> <<< POL(times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(rcons(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(pi(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(negrecip(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[5A]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[5A]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__TIMES(s(X), Y) -> MARK(Y) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[1A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__square(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[0A]] + [[-I]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(posrecip(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Y) MARK(cons(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons2(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(pi(x_1)) = [[3A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[3A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__square(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[0A]] + [[-I]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(rnil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(cons2(X1, X2)) -> MARK(X2) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) A__TIMES(s(X), Y) -> A__PLUS(mark(Y), a__times(mark(X), mark(Y))) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) MARK(times(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(N) A__2NDSPOS(s(N), cons(X, Z)) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(N) A__2NDSNEG(s(N), cons(X, Z)) -> MARK(Z) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons2(X, cons(Y, Z))) -> MARK(Z) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 2ndspos(x1, x2) = 2ndspos(x1, x2) A__2NDSPOS(x1, x2) = A__2NDSPOS(x1, x2) mark(x1) = x1 s(x1) = s(x1) cons(x1, x2) = x2 cons2(x1, x2) = x2 2ndsneg(x1, x2) = 2ndsneg(x1, x2) A__2NDSNEG(x1, x2) = A__2NDSNEG(x1, x2) plus(x1, x2) = plus(x1, x2) A__PLUS(x1, x2) = A__PLUS(x1, x2) 0 = 0 times(x1, x2) = times(x1, x2) A__TIMES(x1, x2) = A__TIMES(x1, x2) a__times(x1, x2) = a__times(x1, x2) rcons(x1, x2) = rcons(x1, x2) from(x1) = from a__from(x1) = a__from a__2ndspos(x1, x2) = a__2ndspos(x1, x2) a__2ndsneg(x1, x2) = a__2ndsneg(x1, x2) pi(x1) = pi(x1) a__pi(x1) = a__pi(x1) a__plus(x1, x2) = a__plus(x1, x2) square(x1) = square(x1) a__square(x1) = a__square(x1) posrecip(x1) = posrecip negrecip(x1) = negrecip nil = nil rnil = rnil Recursive path order with status [RPO]. Quasi-Precedence: [from, a__from, pi_1, a__pi_1] > [2ndspos_2, 2ndsneg_2, a__2ndspos_2, a__2ndsneg_2, posrecip] > [A__2NDSPOS_2, A__2NDSNEG_2] > s_1 > A__PLUS_2 [from, a__from, pi_1, a__pi_1] > [2ndspos_2, 2ndsneg_2, a__2ndspos_2, a__2ndsneg_2, posrecip] > rcons_2 [from, a__from, pi_1, a__pi_1] > [2ndspos_2, 2ndsneg_2, a__2ndspos_2, a__2ndsneg_2, posrecip] > negrecip [from, a__from, pi_1, a__pi_1] > [2ndspos_2, 2ndsneg_2, a__2ndspos_2, a__2ndsneg_2, posrecip] > rnil [from, a__from, pi_1, a__pi_1] > 0 [square_1, a__square_1] > [times_2, A__TIMES_2, a__times_2] > [plus_2, a__plus_2] > s_1 > A__PLUS_2 [square_1, a__square_1] > [times_2, A__TIMES_2, a__times_2] > 0 Status: 2ndspos_2: multiset status A__2NDSPOS_2: [2,1] s_1: multiset status 2ndsneg_2: multiset status A__2NDSNEG_2: [2,1] plus_2: multiset status A__PLUS_2: [2,1] 0: multiset status times_2: multiset status A__TIMES_2: multiset status a__times_2: multiset status rcons_2: multiset status from: [] a__from: [] a__2ndspos_2: multiset status a__2ndsneg_2: multiset status pi_1: [1] a__pi_1: [1] a__plus_2: multiset status square_1: multiset status a__square_1: multiset status posrecip: multiset status negrecip: multiset status nil: multiset status rnil: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(0, Y) -> mark(Y) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) mark(square(X)) -> a__square(mark(X)) a__square(X) -> a__times(mark(X), mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__times(0, Y) -> 0 a__times(X1, X2) -> times(X1, X2) a__from(X) -> from(X) a__2ndspos(0, Z) -> rnil a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(0, Z) -> rnil a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__square(X) -> square(X) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: A__2NDSPOS(s(N), cons(X, Z)) -> A__2NDSPOS(s(mark(N)), cons2(X, mark(Z))) A__2NDSNEG(s(N), cons(X, Z)) -> A__2NDSNEG(s(mark(N)), cons2(X, mark(Z))) MARK(times(X1, X2)) -> A__TIMES(mark(X1), mark(X2)) MARK(cons2(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons2(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__from(X) -> cons(mark(X), from(s(X))) a__2ndspos(0, Z) -> rnil a__2ndspos(s(N), cons(X, Z)) -> a__2ndspos(s(mark(N)), cons2(X, mark(Z))) a__2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(X, Z)) -> a__2ndsneg(s(mark(N)), cons2(X, mark(Z))) a__2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) a__pi(X) -> a__2ndspos(mark(X), a__from(0)) a__plus(0, Y) -> mark(Y) a__plus(s(X), Y) -> s(a__plus(mark(X), mark(Y))) a__times(0, Y) -> 0 a__times(s(X), Y) -> a__plus(mark(Y), a__times(mark(X), mark(Y))) a__square(X) -> a__times(mark(X), mark(X)) mark(from(X)) -> a__from(mark(X)) mark(2ndspos(X1, X2)) -> a__2ndspos(mark(X1), mark(X2)) mark(2ndsneg(X1, X2)) -> a__2ndsneg(mark(X1), mark(X2)) mark(pi(X)) -> a__pi(mark(X)) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(times(X1, X2)) -> a__times(mark(X1), mark(X2)) mark(square(X)) -> a__square(mark(X)) mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(posrecip(X)) -> posrecip(mark(X)) mark(negrecip(X)) -> negrecip(mark(X)) mark(nil) -> nil mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(cons2(X1, X2)) -> cons2(X1, mark(X2)) mark(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(X2)) a__from(X) -> from(X) a__2ndspos(X1, X2) -> 2ndspos(X1, X2) a__2ndsneg(X1, X2) -> 2ndsneg(X1, X2) a__pi(X) -> pi(X) a__plus(X1, X2) -> plus(X1, X2) a__times(X1, X2) -> times(X1, X2) a__square(X) -> square(X) The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons2(X1, X2)) -> MARK(X2) R is empty. The set Q consists of the following terms: a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. a__from(x0) a__pi(x0) a__square(x0) mark(from(x0)) mark(2ndspos(x0, x1)) mark(2ndsneg(x0, x1)) mark(pi(x0)) mark(plus(x0, x1)) mark(times(x0, x1)) mark(square(x0)) mark(0) mark(s(x0)) mark(posrecip(x0)) mark(negrecip(x0)) mark(nil) mark(cons(x0, x1)) mark(cons2(x0, x1)) mark(rnil) mark(rcons(x0, x1)) a__2ndspos(x0, x1) a__2ndsneg(x0, x1) a__plus(x0, x1) a__times(x0, x1) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons2(X1, X2)) -> MARK(X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) 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(cons2(X1, X2)) -> MARK(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (48) YES