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, 37 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) MRRProof [EQUIVALENT, 0 ms] (6) QDP (7) TransformationProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [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) TransformationProof [EQUIVALENT, 0 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QReductionProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) ---------------------------------------- (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__H(X) -> A__G(mark(X), X) A__H(X) -> MARK(X) A__G(a, X) -> A__F(b, X) A__F(X, X) -> A__H(a__a) A__F(X, X) -> A__A MARK(h(X)) -> A__H(mark(X)) MARK(h(X)) -> MARK(X) MARK(g(X1, X2)) -> A__G(mark(X1), X2) MARK(g(X1, X2)) -> MARK(X1) MARK(a) -> A__A MARK(f(X1, X2)) -> A__F(mark(X1), X2) MARK(f(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) 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 2 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: A__G(a, X) -> A__F(b, X) A__F(X, X) -> A__H(a__a) A__H(X) -> A__G(mark(X), X) A__H(X) -> MARK(X) MARK(h(X)) -> A__H(mark(X)) MARK(h(X)) -> MARK(X) MARK(g(X1, X2)) -> A__G(mark(X1), X2) MARK(g(X1, X2)) -> MARK(X1) MARK(f(X1, X2)) -> A__F(mark(X1), X2) MARK(f(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) 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 dependency pairs: A__H(X) -> MARK(X) MARK(h(X)) -> A__H(mark(X)) MARK(h(X)) -> MARK(X) MARK(g(X1, X2)) -> A__G(mark(X1), X2) MARK(g(X1, X2)) -> MARK(X1) MARK(f(X1, X2)) -> A__F(mark(X1), X2) MARK(f(X1, X2)) -> MARK(X1) Used ordering: Polynomial interpretation [POLO]: POL(A__F(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(A__G(x_1, x_2)) = 2 + x_1 + x_2 POL(A__H(x_1)) = 2 + 2*x_1 POL(MARK(x_1)) = 1 + 2*x_1 POL(a) = 0 POL(a__a) = 0 POL(a__f(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(a__g(x_1, x_2)) = 2 + x_1 + x_2 POL(a__h(x_1)) = 2 + 2*x_1 POL(b) = 0 POL(f(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(g(x_1, x_2)) = 2 + x_1 + x_2 POL(h(x_1)) = 2 + 2*x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: A__G(a, X) -> A__F(b, X) A__F(X, X) -> A__H(a__a) A__H(X) -> A__G(mark(X), X) The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule A__F(X, X) -> A__H(a__a) at position [0] we obtained the following new rules [LPAR04]: (A__F(y0, y0) -> A__H(b),A__F(y0, y0) -> A__H(b)) (A__F(y0, y0) -> A__H(a),A__F(y0, y0) -> A__H(a)) ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: A__G(a, X) -> A__F(b, X) A__H(X) -> A__G(mark(X), X) A__F(y0, y0) -> A__H(b) A__F(y0, y0) -> A__H(a) The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule A__H(X) -> A__G(mark(X), X) at position [0] we obtained the following new rules [LPAR04]: (A__H(h(x0)) -> A__G(a__h(mark(x0)), h(x0)),A__H(h(x0)) -> A__G(a__h(mark(x0)), h(x0))) (A__H(g(x0, x1)) -> A__G(a__g(mark(x0), x1), g(x0, x1)),A__H(g(x0, x1)) -> A__G(a__g(mark(x0), x1), g(x0, x1))) (A__H(a) -> A__G(a__a, a),A__H(a) -> A__G(a__a, a)) (A__H(f(x0, x1)) -> A__G(a__f(mark(x0), x1), f(x0, x1)),A__H(f(x0, x1)) -> A__G(a__f(mark(x0), x1), f(x0, x1))) (A__H(b) -> A__G(b, b),A__H(b) -> A__G(b, b)) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: A__G(a, X) -> A__F(b, X) A__F(y0, y0) -> A__H(b) A__F(y0, y0) -> A__H(a) A__H(h(x0)) -> A__G(a__h(mark(x0)), h(x0)) A__H(g(x0, x1)) -> A__G(a__g(mark(x0), x1), g(x0, x1)) A__H(a) -> A__G(a__a, a) A__H(f(x0, x1)) -> A__G(a__f(mark(x0), x1), f(x0, x1)) A__H(b) -> A__G(b, b) The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) 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 5 less nodes. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: A__F(y0, y0) -> A__H(a) A__H(a) -> A__G(a__a, a) A__G(a, X) -> A__F(b, X) The TRS R consists of the following rules: a__h(X) -> a__g(mark(X), X) a__g(a, X) -> a__f(b, X) a__f(X, X) -> a__h(a__a) a__a -> b mark(h(X)) -> a__h(mark(X)) mark(g(X1, X2)) -> a__g(mark(X1), X2) mark(a) -> a__a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> b a__h(X) -> h(X) a__g(X1, X2) -> g(X1, X2) a__a -> a a__f(X1, X2) -> f(X1, X2) The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) 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: A__F(y0, y0) -> A__H(a) A__H(a) -> A__G(a__a, a) A__G(a, X) -> A__F(b, X) The TRS R consists of the following rules: a__a -> b a__a -> a The set Q consists of the following terms: a__h(x0) a__a mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) 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__h(x0) mark(h(x0)) mark(g(x0, x1)) mark(a) mark(f(x0, x1)) mark(b) a__g(x0, x1) a__f(x0, x1) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: A__F(y0, y0) -> A__H(a) A__H(a) -> A__G(a__a, a) A__G(a, X) -> A__F(b, X) The TRS R consists of the following rules: a__a -> b a__a -> a The set Q consists of the following terms: a__a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule A__H(a) -> A__G(a__a, a) at position [0] we obtained the following new rules [LPAR04]: (A__H(a) -> A__G(b, a),A__H(a) -> A__G(b, a)) (A__H(a) -> A__G(a, a),A__H(a) -> A__G(a, a)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: A__F(y0, y0) -> A__H(a) A__G(a, X) -> A__F(b, X) A__H(a) -> A__G(b, a) A__H(a) -> A__G(a, a) The TRS R consists of the following rules: a__a -> b a__a -> a The set Q consists of the following terms: a__a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: A__H(a) -> A__G(a, a) A__G(a, X) -> A__F(b, X) A__F(y0, y0) -> A__H(a) The TRS R consists of the following rules: a__a -> b a__a -> a The set Q consists of the following terms: a__a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: A__H(a) -> A__G(a, a) A__G(a, X) -> A__F(b, X) A__F(y0, y0) -> A__H(a) R is empty. The set Q consists of the following terms: a__a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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__a ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: A__H(a) -> A__G(a, a) A__G(a, X) -> A__F(b, X) A__F(y0, y0) -> A__H(a) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule A__G(a, X) -> A__F(b, X) we obtained the following new rules [LPAR04]: (A__G(a, a) -> A__F(b, a),A__G(a, a) -> A__F(b, a)) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: A__H(a) -> A__G(a, a) A__F(y0, y0) -> A__H(a) A__G(a, a) -> A__F(b, a) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (28) TRUE