9.11/3.22 YES 9.11/3.23 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 9.11/3.23 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.11/3.23 9.11/3.23 9.11/3.23 Termination w.r.t. Q of the given QTRS could be proven: 9.11/3.23 9.11/3.23 (0) QTRS 9.11/3.23 (1) DependencyPairsProof [EQUIVALENT, 21 ms] 9.11/3.23 (2) QDP 9.11/3.23 (3) QDPOrderProof [EQUIVALENT, 87 ms] 9.11/3.23 (4) QDP 9.11/3.23 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 9.11/3.23 (6) QDP 9.11/3.23 (7) QDPOrderProof [EQUIVALENT, 25 ms] 9.11/3.23 (8) QDP 9.11/3.23 (9) QDPOrderProof [EQUIVALENT, 28 ms] 9.11/3.23 (10) QDP 9.11/3.23 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 9.11/3.23 (12) QDP 9.11/3.23 (13) UsableRulesProof [EQUIVALENT, 0 ms] 9.11/3.23 (14) QDP 9.11/3.23 (15) QReductionProof [EQUIVALENT, 2 ms] 9.11/3.23 (16) QDP 9.11/3.23 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.11/3.23 (18) YES 9.11/3.23 9.11/3.23 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (0) 9.11/3.23 Obligation: 9.11/3.23 Q restricted rewrite system: 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 9.11/3.23 The set Q consists of the following terms: 9.11/3.23 9.11/3.23 a__from(x0) 9.11/3.23 mark(2nd(x0)) 9.11/3.23 mark(from(x0)) 9.11/3.23 mark(cons(x0, x1)) 9.11/3.23 mark(s(x0)) 9.11/3.23 mark(cons1(x0, x1)) 9.11/3.23 a__2nd(x0) 9.11/3.23 9.11/3.23 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (1) DependencyPairsProof (EQUIVALENT) 9.11/3.23 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (2) 9.11/3.23 Obligation: 9.11/3.23 Q DP problem: 9.11/3.23 The TRS P consists of the following rules: 9.11/3.23 9.11/3.23 A__2ND(cons1(X, cons(Y, Z))) -> MARK(Y) 9.11/3.23 A__2ND(cons(X, X1)) -> A__2ND(cons1(mark(X), mark(X1))) 9.11/3.23 A__2ND(cons(X, X1)) -> MARK(X) 9.11/3.23 A__2ND(cons(X, X1)) -> MARK(X1) 9.11/3.23 A__FROM(X) -> MARK(X) 9.11/3.23 MARK(2nd(X)) -> A__2ND(mark(X)) 9.11/3.23 MARK(2nd(X)) -> MARK(X) 9.11/3.23 MARK(from(X)) -> A__FROM(mark(X)) 9.11/3.23 MARK(from(X)) -> MARK(X) 9.11/3.23 MARK(cons(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(s(X)) -> MARK(X) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X2) 9.11/3.23 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 9.11/3.23 The set Q consists of the following terms: 9.11/3.23 9.11/3.23 a__from(x0) 9.11/3.23 mark(2nd(x0)) 9.11/3.23 mark(from(x0)) 9.11/3.23 mark(cons(x0, x1)) 9.11/3.23 mark(s(x0)) 9.11/3.23 mark(cons1(x0, x1)) 9.11/3.23 a__2nd(x0) 9.11/3.23 9.11/3.23 We have to consider all minimal (P,Q,R)-chains. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (3) QDPOrderProof (EQUIVALENT) 9.11/3.23 We use the reduction pair processor [LPAR04,JAR06]. 9.11/3.23 9.11/3.23 9.11/3.23 The following pairs can be oriented strictly and are deleted. 9.11/3.23 9.11/3.23 MARK(2nd(X)) -> A__2ND(mark(X)) 9.11/3.23 The remaining pairs can at least be oriented weakly. 9.11/3.23 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(A__2ND(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(cons1(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(cons(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(2nd(x_1)) = [[-I]] + [[1A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(from(x_1)) = [[1A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(a__2nd(x_1)) = [[-I]] + [[1A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 9.11/3.23 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 9.11/3.23 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 9.11/3.23 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (4) 9.11/3.23 Obligation: 9.11/3.23 Q DP problem: 9.11/3.23 The TRS P consists of the following rules: 9.11/3.23 9.11/3.23 A__2ND(cons1(X, cons(Y, Z))) -> MARK(Y) 9.11/3.23 A__2ND(cons(X, X1)) -> A__2ND(cons1(mark(X), mark(X1))) 9.11/3.23 A__2ND(cons(X, X1)) -> MARK(X) 9.11/3.23 A__2ND(cons(X, X1)) -> MARK(X1) 9.11/3.23 A__FROM(X) -> MARK(X) 9.11/3.23 MARK(2nd(X)) -> MARK(X) 9.11/3.23 MARK(from(X)) -> A__FROM(mark(X)) 9.11/3.23 MARK(from(X)) -> MARK(X) 9.11/3.23 MARK(cons(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(s(X)) -> MARK(X) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X2) 9.11/3.23 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 9.11/3.23 The set Q consists of the following terms: 9.11/3.23 9.11/3.23 a__from(x0) 9.11/3.23 mark(2nd(x0)) 9.11/3.23 mark(from(x0)) 9.11/3.23 mark(cons(x0, x1)) 9.11/3.23 mark(s(x0)) 9.11/3.23 mark(cons1(x0, x1)) 9.11/3.23 a__2nd(x0) 9.11/3.23 9.11/3.23 We have to consider all minimal (P,Q,R)-chains. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (5) DependencyGraphProof (EQUIVALENT) 9.11/3.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (6) 9.11/3.23 Obligation: 9.11/3.23 Q DP problem: 9.11/3.23 The TRS P consists of the following rules: 9.11/3.23 9.11/3.23 MARK(2nd(X)) -> MARK(X) 9.11/3.23 MARK(from(X)) -> A__FROM(mark(X)) 9.11/3.23 A__FROM(X) -> MARK(X) 9.11/3.23 MARK(from(X)) -> MARK(X) 9.11/3.23 MARK(cons(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(s(X)) -> MARK(X) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X2) 9.11/3.23 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 9.11/3.23 The set Q consists of the following terms: 9.11/3.23 9.11/3.23 a__from(x0) 9.11/3.23 mark(2nd(x0)) 9.11/3.23 mark(from(x0)) 9.11/3.23 mark(cons(x0, x1)) 9.11/3.23 mark(s(x0)) 9.11/3.23 mark(cons1(x0, x1)) 9.11/3.23 a__2nd(x0) 9.11/3.23 9.11/3.23 We have to consider all minimal (P,Q,R)-chains. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (7) QDPOrderProof (EQUIVALENT) 9.11/3.23 We use the reduction pair processor [LPAR04,JAR06]. 9.11/3.23 9.11/3.23 9.11/3.23 The following pairs can be oriented strictly and are deleted. 9.11/3.23 9.11/3.23 MARK(from(X)) -> MARK(X) 9.11/3.23 The remaining pairs can at least be oriented weakly. 9.11/3.23 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(2nd(x_1)) = [[1A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(from(x_1)) = [[3A]] + [[3A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(A__FROM(x_1)) = [[2A]] + [[3A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(cons1(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(a__2nd(x_1)) = [[1A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(a__from(x_1)) = [[3A]] + [[3A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 9.11/3.23 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 9.11/3.23 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 9.11/3.23 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (8) 9.11/3.23 Obligation: 9.11/3.23 Q DP problem: 9.11/3.23 The TRS P consists of the following rules: 9.11/3.23 9.11/3.23 MARK(2nd(X)) -> MARK(X) 9.11/3.23 MARK(from(X)) -> A__FROM(mark(X)) 9.11/3.23 A__FROM(X) -> MARK(X) 9.11/3.23 MARK(cons(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(s(X)) -> MARK(X) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X2) 9.11/3.23 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 9.11/3.23 The set Q consists of the following terms: 9.11/3.23 9.11/3.23 a__from(x0) 9.11/3.23 mark(2nd(x0)) 9.11/3.23 mark(from(x0)) 9.11/3.23 mark(cons(x0, x1)) 9.11/3.23 mark(s(x0)) 9.11/3.23 mark(cons1(x0, x1)) 9.11/3.23 a__2nd(x0) 9.11/3.23 9.11/3.23 We have to consider all minimal (P,Q,R)-chains. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (9) QDPOrderProof (EQUIVALENT) 9.11/3.23 We use the reduction pair processor [LPAR04,JAR06]. 9.11/3.23 9.11/3.23 9.11/3.23 The following pairs can be oriented strictly and are deleted. 9.11/3.23 9.11/3.23 MARK(from(X)) -> A__FROM(mark(X)) 9.11/3.23 The remaining pairs can at least be oriented weakly. 9.11/3.23 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(2nd(x_1)) = [[0A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(from(x_1)) = [[0A]] + [[1A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(A__FROM(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(cons1(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(a__2nd(x_1)) = [[0A]] + [[0A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 <<< 9.11/3.23 POL(a__from(x_1)) = [[0A]] + [[1A]] * x_1 9.11/3.23 >>> 9.11/3.23 9.11/3.23 9.11/3.23 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 9.11/3.23 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 9.11/3.23 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (10) 9.11/3.23 Obligation: 9.11/3.23 Q DP problem: 9.11/3.23 The TRS P consists of the following rules: 9.11/3.23 9.11/3.23 MARK(2nd(X)) -> MARK(X) 9.11/3.23 A__FROM(X) -> MARK(X) 9.11/3.23 MARK(cons(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(s(X)) -> MARK(X) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X2) 9.11/3.23 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.11/3.23 a__from(X) -> cons(mark(X), from(s(X))) 9.11/3.23 mark(2nd(X)) -> a__2nd(mark(X)) 9.11/3.23 mark(from(X)) -> a__from(mark(X)) 9.11/3.23 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.11/3.23 mark(s(X)) -> s(mark(X)) 9.11/3.23 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.11/3.23 a__2nd(X) -> 2nd(X) 9.11/3.23 a__from(X) -> from(X) 9.11/3.23 9.11/3.23 The set Q consists of the following terms: 9.11/3.23 9.11/3.23 a__from(x0) 9.11/3.23 mark(2nd(x0)) 9.11/3.23 mark(from(x0)) 9.11/3.23 mark(cons(x0, x1)) 9.11/3.23 mark(s(x0)) 9.11/3.23 mark(cons1(x0, x1)) 9.11/3.23 a__2nd(x0) 9.11/3.23 9.11/3.23 We have to consider all minimal (P,Q,R)-chains. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (11) DependencyGraphProof (EQUIVALENT) 9.11/3.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 9.11/3.23 ---------------------------------------- 9.11/3.23 9.11/3.23 (12) 9.11/3.23 Obligation: 9.11/3.23 Q DP problem: 9.11/3.23 The TRS P consists of the following rules: 9.11/3.23 9.11/3.23 MARK(cons(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(2nd(X)) -> MARK(X) 9.11/3.23 MARK(s(X)) -> MARK(X) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X1) 9.11/3.23 MARK(cons1(X1, X2)) -> MARK(X2) 9.11/3.23 9.11/3.23 The TRS R consists of the following rules: 9.11/3.23 9.11/3.23 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 9.11/3.23 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 9.22/3.24 a__from(X) -> cons(mark(X), from(s(X))) 9.22/3.24 mark(2nd(X)) -> a__2nd(mark(X)) 9.22/3.24 mark(from(X)) -> a__from(mark(X)) 9.22/3.24 mark(cons(X1, X2)) -> cons(mark(X1), X2) 9.22/3.24 mark(s(X)) -> s(mark(X)) 9.22/3.24 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 9.22/3.24 a__2nd(X) -> 2nd(X) 9.22/3.24 a__from(X) -> from(X) 9.22/3.24 9.22/3.24 The set Q consists of the following terms: 9.22/3.24 9.22/3.24 a__from(x0) 9.22/3.24 mark(2nd(x0)) 9.22/3.24 mark(from(x0)) 9.22/3.24 mark(cons(x0, x1)) 9.22/3.24 mark(s(x0)) 9.22/3.24 mark(cons1(x0, x1)) 9.22/3.24 a__2nd(x0) 9.22/3.24 9.22/3.24 We have to consider all minimal (P,Q,R)-chains. 9.22/3.24 ---------------------------------------- 9.22/3.24 9.22/3.24 (13) UsableRulesProof (EQUIVALENT) 9.22/3.24 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 9.22/3.24 ---------------------------------------- 9.22/3.24 9.22/3.24 (14) 9.22/3.24 Obligation: 9.22/3.24 Q DP problem: 9.22/3.24 The TRS P consists of the following rules: 9.22/3.24 9.22/3.24 MARK(cons(X1, X2)) -> MARK(X1) 9.22/3.24 MARK(2nd(X)) -> MARK(X) 9.22/3.24 MARK(s(X)) -> MARK(X) 9.22/3.24 MARK(cons1(X1, X2)) -> MARK(X1) 9.22/3.24 MARK(cons1(X1, X2)) -> MARK(X2) 9.22/3.24 9.22/3.24 R is empty. 9.22/3.24 The set Q consists of the following terms: 9.22/3.24 9.22/3.24 a__from(x0) 9.22/3.24 mark(2nd(x0)) 9.22/3.24 mark(from(x0)) 9.22/3.24 mark(cons(x0, x1)) 9.22/3.24 mark(s(x0)) 9.22/3.24 mark(cons1(x0, x1)) 9.22/3.24 a__2nd(x0) 9.22/3.24 9.22/3.24 We have to consider all minimal (P,Q,R)-chains. 9.22/3.24 ---------------------------------------- 9.22/3.24 9.22/3.24 (15) QReductionProof (EQUIVALENT) 9.22/3.24 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 9.22/3.24 9.22/3.24 a__from(x0) 9.22/3.24 mark(2nd(x0)) 9.22/3.24 mark(from(x0)) 9.22/3.24 mark(cons(x0, x1)) 9.22/3.24 mark(s(x0)) 9.22/3.24 mark(cons1(x0, x1)) 9.22/3.24 a__2nd(x0) 9.22/3.24 9.22/3.24 9.22/3.24 ---------------------------------------- 9.22/3.24 9.22/3.24 (16) 9.22/3.24 Obligation: 9.22/3.24 Q DP problem: 9.22/3.24 The TRS P consists of the following rules: 9.22/3.24 9.22/3.24 MARK(cons(X1, X2)) -> MARK(X1) 9.22/3.24 MARK(2nd(X)) -> MARK(X) 9.22/3.24 MARK(s(X)) -> MARK(X) 9.22/3.24 MARK(cons1(X1, X2)) -> MARK(X1) 9.22/3.24 MARK(cons1(X1, X2)) -> MARK(X2) 9.22/3.24 9.22/3.24 R is empty. 9.22/3.24 Q is empty. 9.22/3.24 We have to consider all minimal (P,Q,R)-chains. 9.22/3.24 ---------------------------------------- 9.22/3.24 9.22/3.24 (17) QDPSizeChangeProof (EQUIVALENT) 9.22/3.24 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 9.22/3.24 9.22/3.24 From the DPs we obtained the following set of size-change graphs: 9.22/3.24 *MARK(cons(X1, X2)) -> MARK(X1) 9.22/3.24 The graph contains the following edges 1 > 1 9.22/3.24 9.22/3.24 9.22/3.24 *MARK(2nd(X)) -> MARK(X) 9.22/3.24 The graph contains the following edges 1 > 1 9.22/3.24 9.22/3.24 9.22/3.24 *MARK(s(X)) -> MARK(X) 9.22/3.24 The graph contains the following edges 1 > 1 9.22/3.24 9.22/3.24 9.22/3.24 *MARK(cons1(X1, X2)) -> MARK(X1) 9.22/3.24 The graph contains the following edges 1 > 1 9.22/3.24 9.22/3.24 9.22/3.24 *MARK(cons1(X1, X2)) -> MARK(X2) 9.22/3.24 The graph contains the following edges 1 > 1 9.22/3.24 9.22/3.24 9.22/3.24 ---------------------------------------- 9.22/3.24 9.22/3.24 (18) 9.22/3.24 YES 9.22/3.28 EOF