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, 32 ms] (2) QDP (3) TransformationProof [EQUIVALENT, 135 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) QDPOrderProof [EQUIVALENT, 313 ms] (8) QDP (9) QDPOrderProof [EQUIVALENT, 347 ms] (10) QDP (11) QDPOrderProof [EQUIVALENT, 316 ms] (12) QDP (13) QDPOrderProof [EQUIVALENT, 360 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 336 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) QDPOrderProof [EQUIVALENT, 314 ms] (22) QDP (23) QDPOrderProof [EQUIVALENT, 303 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) QDP (27) QDPOrderProof [EQUIVALENT, 257 ms] (28) QDP (29) QDPOrderProof [EQUIVALENT, 265 ms] (30) QDP (31) QDPOrderProof [EQUIVALENT, 241 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 239 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 301 ms] (36) QDP (37) QDPOrderProof [EQUIVALENT, 252 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 290 ms] (40) QDP (41) QDPOrderProof [EQUIVALENT, 362 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) AND (45) QDP (46) QDPOrderProof [EQUIVALENT, 231 ms] (47) QDP (48) QDPOrderProof [EQUIVALENT, 151 ms] (49) QDP (50) QDPOrderProof [EQUIVALENT, 221 ms] (51) QDP (52) QDPQMonotonicMRRProof [EQUIVALENT, 66 ms] (53) QDP (54) QDPOrderProof [EQUIVALENT, 338 ms] (55) QDP (56) QDPOrderProof [EQUIVALENT, 245 ms] (57) QDP (58) PisEmptyProof [EQUIVALENT, 0 ms] (59) YES (60) QDP (61) QDPOrderProof [EQUIVALENT, 276 ms] (62) QDP (63) PisEmptyProof [EQUIVALENT, 0 ms] (64) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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, cons(Y, Z))) -> MARK(Y) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule A__PI(X) -> A__2NDSPOS(mark(X), a__from(0)) at position [1] we obtained the following new rules [LPAR04]: (A__PI(y0) -> A__2NDSPOS(mark(y0), cons(mark(0), from(s(0)))),A__PI(y0) -> A__2NDSPOS(mark(y0), cons(mark(0), from(s(0))))) (A__PI(y0) -> A__2NDSPOS(mark(y0), from(0)),A__PI(y0) -> A__2NDSPOS(mark(y0), from(0))) ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: A__FROM(X) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Y) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PI(y0) -> A__2NDSPOS(mark(y0), cons(mark(0), from(s(0)))) A__PI(y0) -> A__2NDSPOS(mark(y0), 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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, 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, 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) -> MARK(X) 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__TIMES(s(X), Y) -> MARK(Y) 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__PI(X) -> A__FROM(0) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. 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)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[4A]] + [[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)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[4A]] + [[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(pi(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(A__PI(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(square(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(A__SQUARE(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(posrecip(x_1)) = [[4A]] + [[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)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(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(a__pi(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, 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, 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) -> MARK(X) 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__PI(X) -> A__FROM(0) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. A__PI(X) -> A__FROM(0) 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)) = [[0A]] + [[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(2ndsneg(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)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(A__PI(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< 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(square(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__SQUARE(x_1)) = [[0A]] + [[0A]] * 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__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(a__pi(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, 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, 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) -> MARK(X) 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) 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)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< 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)) = [[1A]] + [[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(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(pi(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(A__PI(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(plus(x_1, x_2)) = [[0A]] + [[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)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__SQUARE(x_1)) = [[1A]] + [[0A]] * 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__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(a__pi(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (12) 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, 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, 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) -> 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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(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)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[0A]] + [[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)) = [[0A]] + [[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(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(pi(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(A__PI(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< 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)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(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(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(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)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__pi(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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: 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, 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, cons(Y, Z))) -> MARK(Y) MARK(2ndsneg(X1, X2)) -> MARK(X1) MARK(2ndsneg(X1, X2)) -> MARK(X2) A__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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (16) 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, 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, 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) 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) 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)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[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)) = [[-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)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[-I]] + [[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)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(A__SQUARE(x_1)) = [[0A]] + [[0A]] * 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__from(x_1)) = [[-I]] + [[1A]] * 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)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (18) 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, 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, 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (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, 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, 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> 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(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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(square(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)) = [[1A]] + [[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(mark(x_1)) = [[-I]] + [[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(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)) = [[0A]] + [[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]] + [[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)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(A__SQUARE(x_1)) = [[2A]] + [[0A]] * 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(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)) = [[-I]] + [[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(a__square(x_1)) = [[2A]] + [[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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, 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, 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(square(X)) -> A__SQUARE(mark(X)) A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__SQUARE(X) -> MARK(X) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. A__SQUARE(X) -> A__TIMES(mark(X), mark(X)) A__SQUARE(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)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[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(2ndsneg(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(plus(x_1, x_2)) = [[0A]] + [[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)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__times(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(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)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[-I]] + [[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(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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, 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, 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(square(X)) -> A__SQUARE(mark(X)) A__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) A__PLUS(s(X), Y) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSPOS(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Y) MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) 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(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Y) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(Y) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__2NDSPOS(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(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)) = [[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)) = [[-I]] + [[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)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[-I]] + [[1A]] * 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)) = [[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]] + [[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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) 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, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) 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(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(N) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> MARK(N) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[3A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[3A]] + [[3A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[-I]] + [[3A]] * 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(A__2NDSNEG(x_1, x_2)) = [[-I]] + [[3A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[3A]] + [[3A]] * 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)) = [[3A]] + [[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)) = [[3A]] + [[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)) = [[4A]] + [[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)) = [[3A]] + [[3A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[3A]] + [[3A]] * 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)) = [[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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) 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, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) 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(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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(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)) = [[1A]] + [[1A]] * 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(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[2A]] + [[1A]] * 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)) = [[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(from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[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)) = [[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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) 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(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. MARK(times(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)) = [[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(A__2NDSNEG(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[0A]] + [[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)) = [[5A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[5A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[5A]] + [[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)) = [[-I]] + [[0A]] * 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)) = [[-I]] + [[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)) = [[5A]] + [[1A]] * x_1 >>> <<< POL(a__square(x_1)) = [[5A]] + [[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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) 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(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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(plus(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)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[1A]] + [[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(A__2NDSNEG(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[2A]] + [[1A]] * 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)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[2A]] + [[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)) = [[-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)) = [[2A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[3A]] + [[2A]] * x_1 >>> <<< POL(a__square(x_1)) = [[3A]] + [[2A]] * 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) 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(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(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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__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)) = [[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)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(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(2ndsneg(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[3A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[3A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[3A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[3A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[3A]] + [[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)) = [[-I]] + [[0A]] * 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)) = [[-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)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[3A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[3A]] + [[2A]] * x_1 >>> <<< POL(a__square(x_1)) = [[3A]] + [[2A]] * 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) MARK(2ndspos(X1, X2)) -> MARK(X2) MARK(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), mark(X2)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) 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(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(X1) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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(2ndsneg(X1, X2)) -> A__2NDSNEG(mark(X1), 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)) = [[0A]] + [[2A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[1A]] + [[1A]] * 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(A__2NDSNEG(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[-I]] + [[2A]] * x_1 + [[1A]] * 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) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[-I]] + [[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)) = [[-I]] + [[1A]] * 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]] + [[2A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[-I]] + [[2A]] * x_1 + [[1A]] * x_2 >>> <<< POL(pi(x_1)) = [[1A]] + [[2A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[1A]] + [[2A]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(a__square(x_1)) = [[-I]] + [[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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(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: MARK(2ndspos(X1, X2)) -> A__2NDSPOS(mark(X1), mark(X2)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) MARK(2ndspos(X1, X2)) -> MARK(X2) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) 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(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(X1) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) 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(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)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[3A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> <<< POL(A__2NDSPOS(x_1, x_2)) = [[2A]] + [[-I]] * 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(A__2NDSNEG(x_1, x_2)) = [[2A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(2ndsneg(x_1, x_2)) = [[3A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__PLUS(x_1, x_2)) = [[2A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[-I]] * 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)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[3A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__2ndsneg(x_1, x_2)) = [[3A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> <<< POL(pi(x_1)) = [[4A]] + [[-I]] * x_1 >>> <<< POL(a__pi(x_1)) = [[4A]] + [[-I]] * x_1 >>> <<< POL(a__plus(x_1, x_2)) = [[0A]] + [[-I]] * 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) = [[3A]] >>> 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(0, Y) -> MARK(Y) 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(X1) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X1) 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__TIMES(s(X), Y) -> MARK(X) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> MARK(Z) A__2NDSNEG(s(N), cons(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. ---------------------------------------- (44) Complex Obligation (AND) ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(Y) 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__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (46) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. 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(A__PLUS(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[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)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[1A]] * 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(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(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)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__square(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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(Y) 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__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(posrecip(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (48) 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(A__PLUS(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(plus(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< 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(posrecip(x_1)) = [[1A]] + [[1A]] * 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)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(2ndspos(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2ndspos(x_1, x_2)) = [[0A]] + [[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(pi(x_1)) = [[1A]] + [[1A]] * x_1 >>> <<< POL(a__pi(x_1)) = [[1A]] + [[1A]] * 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(cons(x_1, x_2)) = [[1A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(Y) 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__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(negrecip(X)) -> MARK(X) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (50) 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(A__PLUS(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(plus(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(A__TIMES(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(a__times(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[-I]] * x_2 >>> <<< POL(negrecip(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(rcons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(from(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[1A]] * 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(2ndsneg(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]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(square(x_1)) = [[0A]] + [[5A]] * x_1 >>> <<< POL(a__square(x_1)) = [[0A]] + [[5A]] * x_1 >>> <<< POL(posrecip(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(nil) = [[0A]] >>> <<< POL(cons(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(Y) 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__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) A__TIMES(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (52) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: A__TIMES(s(X), Y) -> MARK(X) MARK(times(X1, X2)) -> MARK(X1) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(2ndsneg(x_1, x_2)) = 0 POL(2ndspos(x_1, x_2)) = 0 POL(A__PLUS(x_1, x_2)) = 2*x_2 POL(A__TIMES(x_1, x_2)) = 2 + 2*x_1 POL(MARK(x_1)) = 2*x_1 POL(a__2ndsneg(x_1, x_2)) = 0 POL(a__2ndspos(x_1, x_2)) = 0 POL(a__from(x_1)) = 0 POL(a__pi(x_1)) = 0 POL(a__plus(x_1, x_2)) = x_2 POL(a__square(x_1)) = 2 + 2*x_1 POL(a__times(x_1, x_2)) = 1 + x_1 POL(cons(x_1, x_2)) = 0 POL(from(x_1)) = 0 POL(mark(x_1)) = x_1 POL(negrecip(x_1)) = 0 POL(nil) = 0 POL(pi(x_1)) = 0 POL(plus(x_1, x_2)) = x_2 POL(posrecip(x_1)) = 0 POL(rcons(x_1, x_2)) = x_1 + 2*x_2 POL(rnil) = 0 POL(s(x_1)) = x_1 POL(square(x_1)) = 2 + 2*x_1 POL(times(x_1, x_2)) = 1 + x_1 ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) A__PLUS(s(X), Y) -> MARK(Y) 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__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) MARK(s(X)) -> MARK(X) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (54) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__PLUS(0, Y) -> MARK(Y) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(s(X), Y) -> MARK(Y) 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__TIMES(s(X), Y) -> A__TIMES(mark(X), mark(Y)) MARK(s(X)) -> MARK(X) MARK(rcons(X1, X2)) -> MARK(X1) MARK(rcons(X1, X2)) -> MARK(X2) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. A__PLUS(x1, x2) = A__PLUS(x2) 0 = 0 MARK(x1) = MARK(x1) plus(x1, x2) = plus(x1, x2) mark(x1) = x1 s(x1) = s(x1) 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(x1) a__from(x1) = a__from(x1) 2ndspos(x1, x2) = x1 a__2ndspos(x1, x2) = x1 2ndsneg(x1, x2) = x1 a__2ndsneg(x1, x2) = x1 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 cons(x1, x2) = cons(x1) rnil = rnil Recursive path order with status [RPO]. Quasi-Precedence: [0, rnil] > [MARK_1, rcons_2] [from_1, a__from_1, pi_1, a__pi_1] > s_1 > [MARK_1, rcons_2] [from_1, a__from_1, pi_1, a__pi_1] > s_1 > posrecip [from_1, a__from_1, pi_1, a__pi_1] > s_1 > negrecip [from_1, a__from_1, pi_1, a__pi_1] > cons_1 [square_1, a__square_1] > [times_2, A__TIMES_2, a__times_2] > [A__PLUS_1, plus_2, a__plus_2] > s_1 > [MARK_1, rcons_2] [square_1, a__square_1] > [times_2, A__TIMES_2, a__times_2] > [A__PLUS_1, plus_2, a__plus_2] > s_1 > posrecip [square_1, a__square_1] > [times_2, A__TIMES_2, a__times_2] > [A__PLUS_1, plus_2, a__plus_2] > s_1 > negrecip Status: A__PLUS_1: multiset status 0: multiset status MARK_1: multiset status plus_2: multiset status s_1: multiset status times_2: multiset status A__TIMES_2: multiset status a__times_2: multiset status rcons_2: [2,1] from_1: multiset status a__from_1: 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: [] nil: multiset status cons_1: 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(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: A__PLUS(s(X), Y) -> A__PLUS(mark(X), mark(Y)) 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (56) 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) -> A__PLUS(mark(X), mark(Y)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. A__PLUS(x1, x2) = A__PLUS(x1) s(x1) = s(x1) mark(x1) = x1 from(x1) = from a__from(x1) = a__from 2ndspos(x1, x2) = x2 a__2ndspos(x1, x2) = x2 2ndsneg(x1, x2) = 2ndsneg(x1, x2) a__2ndsneg(x1, x2) = a__2ndsneg(x1, x2) pi(x1) = pi(x1) a__pi(x1) = a__pi(x1) 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) square(x1) = square(x1) a__square(x1) = a__square(x1) posrecip(x1) = posrecip negrecip(x1) = negrecip nil = nil cons(x1, x2) = cons rnil = rnil rcons(x1, x2) = x1 Recursive path order with status [RPO]. Quasi-Precedence: [2ndsneg_2, a__2ndsneg_2] > [negrecip, cons] > posrecip > rnil [pi_1, a__pi_1] > [from, a__from] > [A__PLUS_1, s_1] > rnil [pi_1, a__pi_1] > [from, a__from] > [negrecip, cons] > posrecip > rnil 0 > rnil [square_1, a__square_1] > [times_2, a__times_2] > [plus_2, a__plus_2] > [A__PLUS_1, s_1] > rnil nil > rnil Status: A__PLUS_1: multiset status s_1: multiset status from: [] a__from: [] 2ndsneg_2: multiset status a__2ndsneg_2: multiset status pi_1: multiset status a__pi_1: multiset status plus_2: [1,2] a__plus_2: [1,2] 0: multiset status times_2: [1,2] a__times_2: [1,2] square_1: [1] a__square_1: [1] posrecip: multiset status negrecip: [] nil: multiset status cons: 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(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(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__times(0, Y) -> 0 a__times(X1, X2) -> times(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (57) Obligation: Q DP problem: P is empty. 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (58) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (59) YES ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (61) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__2NDSNEG(s(N), cons(X, cons(Y, Z))) -> A__2NDSPOS(mark(N), mark(Z)) A__2NDSPOS(s(N), cons(X, cons(Y, Z))) -> A__2NDSNEG(mark(N), mark(Z)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. A__2NDSNEG(x1, x2) = A__2NDSNEG(x1, x2) s(x1) = s(x1) cons(x1, x2) = x2 A__2NDSPOS(x1, x2) = A__2NDSPOS(x1, x2) mark(x1) = x1 from(x1) = from a__from(x1) = a__from 2ndspos(x1, x2) = x2 a__2ndspos(x1, x2) = x2 2ndsneg(x1, x2) = x1 a__2ndsneg(x1, x2) = x1 pi(x1) = pi a__pi(x1) = a__pi 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) square(x1) = square(x1) a__square(x1) = a__square(x1) posrecip(x1) = posrecip negrecip(x1) = negrecip nil = nil rnil = rnil rcons(x1, x2) = x1 Recursive path order with status [RPO]. Quasi-Precedence: [A__2NDSNEG_2, A__2NDSPOS_2] > [posrecip, rnil] [from, a__from, pi, a__pi, 0] > [s_1, negrecip] > [posrecip, rnil] [square_1, a__square_1] > [times_2, a__times_2] > [plus_2, a__plus_2] > [s_1, negrecip] > [posrecip, rnil] nil > [posrecip, rnil] Status: A__2NDSNEG_2: multiset status s_1: multiset status A__2NDSPOS_2: multiset status from: [] a__from: [] pi: [] a__pi: [] plus_2: [2,1] a__plus_2: [2,1] 0: multiset status times_2: [2,1] a__times_2: [2,1] 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(rnil) -> rnil mark(rcons(X1, X2)) -> rcons(mark(X1), mark(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__times(0, Y) -> 0 a__times(X1, X2) -> times(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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(mark(Y)), a__2ndspos(mark(N), mark(Z))) ---------------------------------------- (62) Obligation: Q DP problem: P is empty. 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, cons(Y, Z))) -> rcons(posrecip(mark(Y)), a__2ndsneg(mark(N), mark(Z))) a__2ndsneg(0, Z) -> rnil a__2ndsneg(s(N), cons(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(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(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. ---------------------------------------- (63) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (64) YES