/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, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 7 ms] (6) QDP (7) QDPOrderProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [EQUIVALENT, 0 ms] (10) QDP (11) NonTerminationLoopProof [COMPLETE, 0 ms] (12) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(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: F(g(X), Y) -> F(X, n__f(n__g(X), activate(Y))) F(g(X), Y) -> ACTIVATE(Y) ACTIVATE(n__f(X1, X2)) -> F(activate(X1), X2) ACTIVATE(n__f(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__g(X)) -> G(activate(X)) ACTIVATE(n__g(X)) -> ACTIVATE(X) The TRS R consists of the following rules: f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(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 1 SCC with 1 less node. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(X), Y) -> ACTIVATE(Y) ACTIVATE(n__f(X1, X2)) -> F(activate(X1), X2) F(g(X), Y) -> F(X, n__f(n__g(X), activate(Y))) ACTIVATE(n__f(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__g(X)) -> ACTIVATE(X) The TRS R consists of the following rules: f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVATE(n__g(X)) -> ACTIVATE(X) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(F(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(g(x_1)) = [[-I]] + [[3A]] * x_1 >>> <<< POL(ACTIVATE(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(n__f(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(activate(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(n__g(x_1)) = [[-I]] + [[3A]] * x_1 >>> <<< POL(f(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(X)) activate(X) -> X f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(X), Y) -> ACTIVATE(Y) ACTIVATE(n__f(X1, X2)) -> F(activate(X1), X2) F(g(X), Y) -> F(X, n__f(n__g(X), activate(Y))) ACTIVATE(n__f(X1, X2)) -> ACTIVATE(X1) The TRS R consists of the following rules: f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(X)) activate(X) -> X Q is empty. 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. ACTIVATE(n__f(X1, X2)) -> ACTIVATE(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(F(x_1, x_2)) = [[1A]] + [[2A]] * x_1 + [[1A]] * x_2 >>> <<< POL(g(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(ACTIVATE(x_1)) = [[0A]] + [[1A]] * x_1 >>> <<< POL(n__f(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(activate(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(n__g(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(f(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[0A]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(X)) activate(X) -> X f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(X), Y) -> ACTIVATE(Y) ACTIVATE(n__f(X1, X2)) -> F(activate(X1), X2) F(g(X), Y) -> F(X, n__f(n__g(X), activate(Y))) The TRS R consists of the following rules: f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ACTIVATE(n__f(X1, X2)) -> F(activate(X1), X2) at position [0] we obtained the following new rules [LPAR04]: (ACTIVATE(n__f(n__f(x0, x1), y1)) -> F(f(activate(x0), x1), y1),ACTIVATE(n__f(n__f(x0, x1), y1)) -> F(f(activate(x0), x1), y1)) (ACTIVATE(n__f(n__g(x0), y1)) -> F(g(activate(x0)), y1),ACTIVATE(n__f(n__g(x0), y1)) -> F(g(activate(x0)), y1)) (ACTIVATE(n__f(x0, y1)) -> F(x0, y1),ACTIVATE(n__f(x0, y1)) -> F(x0, y1)) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(X), Y) -> ACTIVATE(Y) F(g(X), Y) -> F(X, n__f(n__g(X), activate(Y))) ACTIVATE(n__f(n__f(x0, x1), y1)) -> F(f(activate(x0), x1), y1) ACTIVATE(n__f(n__g(x0), y1)) -> F(g(activate(x0)), y1) ACTIVATE(n__f(x0, y1)) -> F(x0, y1) The TRS R consists of the following rules: f(g(X), Y) -> f(X, n__f(n__g(X), activate(Y))) f(X1, X2) -> n__f(X1, X2) g(X) -> n__g(X) activate(n__f(X1, X2)) -> f(activate(X1), X2) activate(n__g(X)) -> g(activate(X)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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 = ACTIVATE(n__f(n__g(g(X)), y1)) evaluates to t =ACTIVATE(n__f(n__g(g(X)), activate(y1))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [y1 / activate(y1)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence ACTIVATE(n__f(n__g(g(X)), y1)) -> F(g(activate(g(X))), y1) with rule ACTIVATE(n__f(n__g(x0), y1')) -> F(g(activate(x0)), y1') at position [] and matcher [x0 / g(X), y1' / y1] F(g(activate(g(X))), y1) -> F(g(g(X)), y1) with rule activate(X') -> X' at position [0,0] and matcher [X' / g(X)] F(g(g(X)), y1) -> F(g(X), n__f(n__g(g(X)), activate(y1))) with rule F(g(X'), Y') -> F(X', n__f(n__g(X'), activate(Y'))) at position [] and matcher [X' / g(X), Y' / y1] F(g(X), n__f(n__g(g(X)), activate(y1))) -> ACTIVATE(n__f(n__g(g(X)), activate(y1))) with rule F(g(X), Y) -> ACTIVATE(Y) 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. ---------------------------------------- (12) NO