/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox/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) QTRSRRRProof [EQUIVALENT, 39 ms] (2) QTRS (3) AAECC Innermost [EQUIVALENT, 0 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 29 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) QDP (9) UsableRulesProof [EQUIVALENT, 0 ms] (10) QDP (11) QReductionProof [EQUIVALENT, 0 ms] (12) QDP (13) MNOCProof [EQUIVALENT, 0 ms] (14) QDP (15) NonTerminationLoopProof [COMPLETE, 0 ms] (16) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: g(X) -> h(activate(X)) c -> d h(n__d) -> g(n__c) d -> n__d c -> n__c activate(n__d) -> d activate(n__c) -> c activate(X) -> X Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(activate(x_1)) = 1 + x_1 POL(c) = 1 POL(d) = 1 POL(g(x_1)) = 1 + x_1 POL(h(x_1)) = x_1 POL(n__c) = 0 POL(n__d) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: c -> n__c activate(n__d) -> d activate(X) -> X ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: g(X) -> h(activate(X)) c -> d h(n__d) -> g(n__c) d -> n__d activate(n__c) -> c Q is empty. ---------------------------------------- (3) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is d -> n__d activate(n__c) -> c c -> d The TRS R 2 is g(X) -> h(activate(X)) h(n__d) -> g(n__c) The signature Sigma is {g_1, h_1} ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: g(X) -> h(activate(X)) c -> d h(n__d) -> g(n__c) d -> n__d activate(n__c) -> c The set Q consists of the following terms: g(x0) c h(n__d) d activate(n__c) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: G(X) -> H(activate(X)) G(X) -> ACTIVATE(X) C -> D H(n__d) -> G(n__c) ACTIVATE(n__c) -> C The TRS R consists of the following rules: g(X) -> h(activate(X)) c -> d h(n__d) -> g(n__c) d -> n__d activate(n__c) -> c The set Q consists of the following terms: g(x0) c h(n__d) d activate(n__c) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: H(n__d) -> G(n__c) G(X) -> H(activate(X)) The TRS R consists of the following rules: g(X) -> h(activate(X)) c -> d h(n__d) -> g(n__c) d -> n__d activate(n__c) -> c The set Q consists of the following terms: g(x0) c h(n__d) d activate(n__c) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) 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. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: H(n__d) -> G(n__c) G(X) -> H(activate(X)) The TRS R consists of the following rules: activate(n__c) -> c c -> d d -> n__d The set Q consists of the following terms: g(x0) c h(n__d) d activate(n__c) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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]. g(x0) h(n__d) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: H(n__d) -> G(n__c) G(X) -> H(activate(X)) The TRS R consists of the following rules: activate(n__c) -> c c -> d d -> n__d The set Q consists of the following terms: c d activate(n__c) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: H(n__d) -> G(n__c) G(X) -> H(activate(X)) The TRS R consists of the following rules: activate(n__c) -> c c -> d d -> n__d Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = G(n__c) evaluates to t =G(n__c) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence G(n__c) -> H(activate(n__c)) with rule G(X) -> H(activate(X)) at position [] and matcher [X / n__c] H(activate(n__c)) -> H(c) with rule activate(n__c) -> c at position [0] and matcher [ ] H(c) -> H(d) with rule c -> d at position [0] and matcher [ ] H(d) -> H(n__d) with rule d -> n__d at position [0] and matcher [ ] H(n__d) -> G(n__c) with rule H(n__d) -> G(n__c) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (16) NO