/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 12 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] (9) YES (10) QDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) QDP (13) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (14) QDP (15) MRRProof [EQUIVALENT, 5 ms] (16) QDP (17) MNOCProof [EQUIVALENT, 0 ms] (18) QDP (19) MNOCProof [EQUIVALENT, 0 ms] (20) QDP (21) NonTerminationLoopProof [COMPLETE, 0 ms] (22) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: p(0) -> 0 p(s(X)) -> X leq(0, Y) -> true leq(s(X), 0) -> false leq(s(X), s(Y)) -> leq(X, Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) diff(X, Y) -> if(leq(X, Y), n__0, n__s(diff(p(X), Y))) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X Q is empty. ---------------------------------------- (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: LEQ(s(X), s(Y)) -> LEQ(X, Y) IF(true, X, Y) -> ACTIVATE(X) IF(false, X, Y) -> ACTIVATE(Y) DIFF(X, Y) -> IF(leq(X, Y), n__0, n__s(diff(p(X), Y))) DIFF(X, Y) -> LEQ(X, Y) DIFF(X, Y) -> DIFF(p(X), Y) DIFF(X, Y) -> P(X) ACTIVATE(n__0) -> 0^1 ACTIVATE(n__s(X)) -> S(X) The TRS R consists of the following rules: p(0) -> 0 p(s(X)) -> X leq(0, Y) -> true leq(s(X), 0) -> false leq(s(X), s(Y)) -> leq(X, Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) diff(X, Y) -> if(leq(X, Y), n__0, n__s(diff(p(X), Y))) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 7 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: LEQ(s(X), s(Y)) -> LEQ(X, Y) The TRS R consists of the following rules: p(0) -> 0 p(s(X)) -> X leq(0, Y) -> true leq(s(X), 0) -> false leq(s(X), s(Y)) -> leq(X, Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) diff(X, Y) -> if(leq(X, Y), n__0, n__s(diff(p(X), Y))) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: LEQ(s(X), s(Y)) -> LEQ(X, Y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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: *LEQ(s(X), s(Y)) -> LEQ(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: DIFF(X, Y) -> DIFF(p(X), Y) The TRS R consists of the following rules: p(0) -> 0 p(s(X)) -> X leq(0, Y) -> true leq(s(X), 0) -> false leq(s(X), s(Y)) -> leq(X, Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) diff(X, Y) -> if(leq(X, Y), n__0, n__s(diff(p(X), Y))) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: DIFF(X, Y) -> DIFF(p(X), Y) The TRS R consists of the following rules: p(0) -> 0 p(s(X)) -> X 0 -> n__0 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: p(s(X)) -> X Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 2 POL(DIFF(x_1, x_2)) = 2*x_1 + x_2 POL(n__0) = 2 POL(p(x_1)) = x_1 POL(s(x_1)) = x_1 ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: DIFF(X, Y) -> DIFF(p(X), Y) The TRS R consists of the following rules: p(0) -> 0 0 -> n__0 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: 0 -> n__0 Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(DIFF(x_1, x_2)) = 2*x_1 + x_2 POL(n__0) = 0 POL(p(x_1)) = x_1 ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: DIFF(X, Y) -> DIFF(p(X), Y) The TRS R consists of the following rules: p(0) -> 0 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: DIFF(X, Y) -> DIFF(p(X), Y) The TRS R consists of the following rules: p(0) -> 0 The set Q consists of the following terms: p(0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: DIFF(X, Y) -> DIFF(p(X), Y) The TRS R consists of the following rules: p(0) -> 0 Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = DIFF(X, Y) evaluates to t =DIFF(p(X), Y) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [X / p(X)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from DIFF(X, Y) to DIFF(p(X), Y). ---------------------------------------- (22) NO