YES proof of /export/starexec/sandbox2/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, 15 ms] (2) QDP (3) QDPOrderProof [EQUIVALENT, 91 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) QDPOrderProof [EQUIVALENT, 33 ms] (8) QDP (9) QDPOrderProof [EQUIVALENT, 0 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) QReductionProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) ---------------------------------------- (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__2ND(cons1(X, cons(Y, Z))) -> MARK(Y) A__2ND(cons(X, X1)) -> A__2ND(cons1(mark(X), mark(X1))) A__2ND(cons(X, X1)) -> MARK(X) A__2ND(cons(X, X1)) -> MARK(X1) A__FROM(X) -> MARK(X) MARK(2nd(X)) -> A__2ND(mark(X)) MARK(2nd(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(2nd(X)) -> A__2ND(mark(X)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__2ND(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons1(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(cons(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(2nd(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(from(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__2nd(x_1)) = [[-I]] + [[1A]] * x_1 >>> <<< POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(2nd(X)) -> a__2nd(mark(X)) a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) a__from(X) -> cons(mark(X), from(s(X))) ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: A__2ND(cons1(X, cons(Y, Z))) -> MARK(Y) A__2ND(cons(X, X1)) -> A__2ND(cons1(mark(X), mark(X1))) A__2ND(cons(X, X1)) -> MARK(X) A__2ND(cons(X, X1)) -> MARK(X1) A__FROM(X) -> MARK(X) MARK(2nd(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) MARK(from(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) 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 4 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2nd(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(from(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(from(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 >>> <<< POL(2nd(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[3A]] + [[3A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[2A]] + [[3A]] * x_1 >>> <<< POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons1(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2nd(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[3A]] + [[3A]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(2nd(X)) -> a__2nd(mark(X)) a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) a__from(X) -> cons(mark(X), from(s(X))) ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2nd(X)) -> MARK(X) MARK(from(X)) -> A__FROM(mark(X)) A__FROM(X) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(from(X)) -> A__FROM(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)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(2nd(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(A__FROM(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons1(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__2nd(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__from(x_1)) = [[0A]] + [[1A]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(2nd(X)) -> a__2nd(mark(X)) a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) a__from(X) -> cons(mark(X), from(s(X))) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(2nd(X)) -> MARK(X) A__FROM(X) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) MARK(2nd(X)) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) MARK(2nd(X)) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) R is empty. The set Q consists of the following terms: a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. a__from(x0) mark(2nd(x0)) mark(from(x0)) mark(cons(x0, x1)) mark(s(x0)) mark(cons1(x0, x1)) a__2nd(x0) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) MARK(2nd(X)) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(cons1(X1, X2)) -> MARK(X1) MARK(cons1(X1, X2)) -> MARK(X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MARK(cons(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(2nd(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(s(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(cons1(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(cons1(X1, X2)) -> MARK(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (18) YES