/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES 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 proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 31 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) TransformationProof [EQUIVALENT, 0 ms] (9) QDP (10) DependencyGraphProof [EQUIVALENT, 0 ms] (11) QDP (12) TransformationProof [EQUIVALENT, 0 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) QDP (16) TransformationProof [EQUIVALENT, 0 ms] (17) QDP (18) DependencyGraphProof [EQUIVALENT, 0 ms] (19) QDP (20) TransformationProof [EQUIVALENT, 0 ms] (21) QDP (22) DependencyGraphProof [EQUIVALENT, 0 ms] (23) QDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) QDP (26) TransformationProof [EQUIVALENT, 0 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) TRUE (30) QDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 64 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 76 ms] (40) QDP (41) QDPOrderProof [EQUIVALENT, 26 ms] (42) QDP (43) QDPOrderProof [EQUIVALENT, 797 ms] (44) QDP (45) PisEmptyProof [EQUIVALENT, 0 ms] (46) YES (47) QDP (48) UsableRulesProof [EQUIVALENT, 0 ms] (49) QDP (50) QDPOrderProof [EQUIVALENT, 7 ms] (51) QDP (52) UsableRulesProof [EQUIVALENT, 0 ms] (53) QDP (54) MRRProof [EQUIVALENT, 0 ms] (55) QDP (56) PisEmptyProof [EQUIVALENT, 0 ms] (57) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) 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: I(x, x) -> I(a, b) G(x, x) -> G(a, b) H(s(f(x))) -> H(f(x)) F(s(x)) -> F(h(s(x))) F(s(x)) -> H(s(x)) F(g(s(x), y)) -> F(g(x, s(y))) F(g(s(x), y)) -> G(x, s(y)) H(g(x, s(y))) -> H(g(s(x), y)) H(g(x, s(y))) -> G(s(x), y) H(i(x, y)) -> I(i(c, h(h(y))), x) H(i(x, y)) -> I(c, h(h(y))) H(i(x, y)) -> H(h(y)) H(i(x, y)) -> H(y) G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(a, g(x, g(b, g(b, y)))))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(x, g(b, g(b, y))))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(x, g(b, g(b, y)))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(b, g(b, y)) G(a, g(x, g(b, g(a, g(x, y))))) -> G(b, y) The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) 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 3 SCCs with 10 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(x, g(b, g(b, y)))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(x, g(b, g(b, y))))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) 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: G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(x, g(b, g(b, y)))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(x, g(b, g(b, y))))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(x, g(b, g(b, y)))) at position [1] we obtained the following new rules [LPAR04]: (G(a, g(g(b, g(b, y1)), g(b, g(a, g(g(b, g(b, y1)), y1))))) -> G(a, g(a, b)),G(a, g(g(b, g(b, y1)), g(b, g(a, g(g(b, g(b, y1)), y1))))) -> G(a, g(a, b))) (G(a, g(a, g(b, g(a, g(a, g(a, g(b, x1))))))) -> G(a, g(a, g(a, g(a, g(b, g(b, g(b, x1))))))),G(a, g(a, g(b, g(a, g(a, g(a, g(b, x1))))))) -> G(a, g(a, g(a, g(a, g(b, g(b, g(b, x1)))))))) (G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b)))),G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b))))) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(x, g(b, g(b, y))))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(g(b, g(b, y1)), g(b, g(a, g(g(b, g(b, y1)), y1))))) -> G(a, g(a, b)) G(a, g(a, g(b, g(a, g(a, g(a, g(b, x1))))))) -> G(a, g(a, g(a, g(a, g(b, g(b, g(b, x1))))))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b)))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(x, g(b, g(b, y))))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b)))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(a, g(x, g(b, g(a, g(x, y))))) -> G(a, g(a, g(x, g(b, g(b, y))))) at position [1] we obtained the following new rules [LPAR04]: (G(a, g(g(b, g(b, y1)), g(b, g(a, g(g(b, g(b, y1)), y1))))) -> G(a, g(a, g(a, b))),G(a, g(g(b, g(b, y1)), g(b, g(a, g(g(b, g(b, y1)), y1))))) -> G(a, g(a, g(a, b)))) (G(a, g(a, g(b, g(a, g(a, g(a, g(b, x1))))))) -> G(a, g(a, g(a, g(a, g(a, g(b, g(b, g(b, x1)))))))),G(a, g(a, g(b, g(a, g(a, g(a, g(b, x1))))))) -> G(a, g(a, g(a, g(a, g(a, g(b, g(b, g(b, x1))))))))) (G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b))))),G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b)))))) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b)))) G(a, g(g(b, g(b, y1)), g(b, g(a, g(g(b, g(b, y1)), y1))))) -> G(a, g(a, g(a, b))) G(a, g(a, g(b, g(a, g(a, g(a, g(b, x1))))))) -> G(a, g(a, g(a, g(a, g(a, g(b, g(b, g(b, x1)))))))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b))))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b)))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b))))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(y0, g(b, g(a, b)))) at position [1] we obtained the following new rules [LPAR04]: (G(a, g(g(b, g(a, b)), g(b, g(a, g(g(b, g(a, b)), b))))) -> G(a, g(a, b)),G(a, g(g(b, g(a, b)), g(b, g(a, g(g(b, g(a, b)), b))))) -> G(a, g(a, b))) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b))))) G(a, g(g(b, g(a, b)), g(b, g(a, g(g(b, g(a, b)), b))))) -> G(a, g(a, b)) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b))))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(a, g(y0, g(b, g(a, g(y0, b))))) -> G(a, g(a, g(y0, g(b, g(a, b))))) at position [1] we obtained the following new rules [LPAR04]: (G(a, g(g(b, g(a, b)), g(b, g(a, g(g(b, g(a, b)), b))))) -> G(a, g(a, g(a, b))),G(a, g(g(b, g(a, b)), g(b, g(a, g(g(b, g(a, b)), b))))) -> G(a, g(a, g(a, b)))) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) G(a, g(g(b, g(a, b)), g(b, g(a, g(g(b, g(a, b)), b))))) -> G(a, g(a, g(a, b))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) The TRS R consists of the following rules: g(x, x) -> g(a, b) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) 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. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) The TRS R consists of the following rules: g(x, x) -> g(a, b) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule G(a, g(x, g(b, g(a, g(x, y))))) -> G(x, g(b, g(b, y))) we obtained the following new rules [LPAR04]: (G(a, g(a, g(b, g(a, g(a, x1))))) -> G(a, g(b, g(b, x1))),G(a, g(a, g(b, g(a, g(a, x1))))) -> G(a, g(b, g(b, x1)))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(a, g(b, g(a, g(a, x1))))) -> G(a, g(b, g(b, x1))) The TRS R consists of the following rules: g(x, x) -> g(a, b) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (29) TRUE ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: H(g(x, s(y))) -> H(g(s(x), y)) H(s(f(x))) -> H(f(x)) H(i(x, y)) -> H(h(y)) H(i(x, y)) -> H(y) The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: H(g(x, s(y))) -> H(g(s(x), y)) H(s(f(x))) -> H(f(x)) H(i(x, y)) -> H(h(y)) H(i(x, y)) -> H(y) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. H(s(f(x))) -> H(f(x)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO,RATPOLO]: POL(H(x_1)) = [4]x_1 POL(a) = 0 POL(b) = 0 POL(c) = 0 POL(f(x_1)) = [4]x_1 POL(g(x_1, x_2)) = 0 POL(h(x_1)) = [1/4]x_1 POL(i(x_1, x_2)) = [4]x_1 + x_2 POL(s(x_1)) = [1/4] + x_1 The value of delta used in the strict ordering is 1. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(s(f(x))) -> h(f(x)) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: H(g(x, s(y))) -> H(g(s(x), y)) H(i(x, y)) -> H(h(y)) H(i(x, y)) -> H(y) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. H(g(x, s(y))) -> H(g(s(x), y)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(H(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(g(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(s(x_1)) = [[0], [1]] + [[0, 1], [1, 0]] * x_1 >>> <<< POL(i(x_1, x_2)) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(h(x_1)) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< POL(a) = [[0], [0]] >>> <<< POL(b) = [[0], [0]] >>> <<< POL(f(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(c) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) i(x, x) -> i(a, b) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: H(i(x, y)) -> H(h(y)) H(i(x, y)) -> H(y) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule H(i(x, y)) -> H(h(y)) at position [0] we obtained the following new rules [LPAR04]: (H(i(y0, g(x0, s(x1)))) -> H(h(g(s(x0), x1))),H(i(y0, g(x0, s(x1)))) -> H(h(g(s(x0), x1)))) (H(i(y0, s(f(x0)))) -> H(h(f(x0))),H(i(y0, s(f(x0)))) -> H(h(f(x0)))) (H(i(y0, i(x0, x1))) -> H(i(i(c, h(h(x1))), x0)),H(i(y0, i(x0, x1))) -> H(i(i(c, h(h(x1))), x0))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: H(i(x, y)) -> H(y) H(i(y0, g(x0, s(x1)))) -> H(h(g(s(x0), x1))) H(i(y0, s(f(x0)))) -> H(h(f(x0))) H(i(y0, i(x0, x1))) -> H(i(i(c, h(h(x1))), x0)) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. H(i(y0, g(x0, s(x1)))) -> H(h(g(s(x0), x1))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO,RATPOLO]: POL(H(x_1)) = [1/4]x_1 POL(a) = 0 POL(b) = 0 POL(c) = 0 POL(f(x_1)) = 0 POL(g(x_1, x_2)) = [1/4] + x_2 POL(h(x_1)) = [1/4]x_1 POL(i(x_1, x_2)) = [4]x_1 + x_2 POL(s(x_1)) = [2]x_1 The value of delta used in the strict ordering is 3/64. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) i(x, x) -> i(a, b) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: H(i(x, y)) -> H(y) H(i(y0, s(f(x0)))) -> H(h(f(x0))) H(i(y0, i(x0, x1))) -> H(i(i(c, h(h(x1))), x0)) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. H(i(y0, s(f(x0)))) -> H(h(f(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO,RATPOLO]: POL(H(x_1)) = [1/2]x_1 POL(a) = 0 POL(b) = 0 POL(c) = 0 POL(f(x_1)) = [1/4] POL(g(x_1, x_2)) = 0 POL(h(x_1)) = [1/4]x_1 POL(i(x_1, x_2)) = [4]x_1 + x_2 POL(s(x_1)) = [1/4] The value of delta used in the strict ordering is 3/32. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(s(f(x))) -> h(f(x)) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: H(i(x, y)) -> H(y) H(i(y0, i(x0, x1))) -> H(i(i(c, h(h(x1))), x0)) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. H(i(x, y)) -> H(y) H(i(y0, i(x0, x1))) -> H(i(i(c, h(h(x1))), x0)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(H(x_1)) = [[0]] + [[2, 0]] * x_1 >>> <<< POL(i(x_1, x_2)) = [[1], [1]] + [[0, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(c) = [[0], [0]] >>> <<< POL(h(x_1)) = [[0], [0]] + [[0, 1], [3, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(f(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(g(x_1, x_2)) = [[0], [0]] + [[0, 0], [2, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(a) = [[0], [0]] >>> <<< POL(b) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: h(s(f(x))) -> h(f(x)) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) f(s(x)) -> s(s(f(h(s(x))))) g(x, x) -> g(a, b) f(g(s(x), y)) -> f(g(x, s(y))) ---------------------------------------- (44) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (46) YES ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(s(x), y)) -> F(g(x, s(y))) F(s(x)) -> F(h(s(x))) The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) 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. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(s(x), y)) -> F(g(x, s(y))) F(s(x)) -> F(h(s(x))) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) g(x, x) -> g(a, b) h(i(x, y)) -> i(i(c, h(h(y))), x) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) i(x, x) -> i(a, b) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F(s(x)) -> F(h(s(x))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. F(x1) = x1 g(x1, x2) = g s(x1) = s h(x1) = h i(x1, x2) = i Knuth-Bendix order [KBO] with precedence:s > h > i and weight map: s=1 i=1 h=1 g=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) i(x, x) -> i(a, b) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(s(x), y)) -> F(g(x, s(y))) The TRS R consists of the following rules: h(g(x, s(y))) -> h(g(s(x), y)) h(s(f(x))) -> h(f(x)) g(x, x) -> g(a, b) h(i(x, y)) -> i(i(c, h(h(y))), x) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) i(x, x) -> i(a, b) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) 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. ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(s(x), y)) -> F(g(x, s(y))) The TRS R consists of the following rules: g(x, x) -> g(a, b) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) 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: F(g(s(x), y)) -> F(g(x, s(y))) Used ordering: Polynomial interpretation [POLO]: POL(F(x_1)) = x_1 POL(a) = 0 POL(b) = 0 POL(g(x_1, x_2)) = 2*x_1 + x_2 POL(s(x_1)) = 1 + x_1 ---------------------------------------- (55) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: g(x, x) -> g(a, b) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (57) YES