/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES 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 proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 23 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) MRRProof [EQUIVALENT, 29 ms] (9) QDP (10) MRRProof [EQUIVALENT, 17 ms] (11) QDP (12) DependencyGraphProof [EQUIVALENT, 0 ms] (13) AND (14) QDP (15) TransformationProof [EQUIVALENT, 0 ms] (16) QDP (17) DependencyGraphProof [EQUIVALENT, 0 ms] (18) TRUE (19) QDP (20) TransformationProof [EQUIVALENT, 0 ms] (21) QDP (22) TransformationProof [EQUIVALENT, 0 ms] (23) QDP (24) TransformationProof [EQUIVALENT, 0 ms] (25) QDP (26) TransformationProof [EQUIVALENT, 0 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) QDP (34) TransformationProof [EQUIVALENT, 0 ms] (35) QDP (36) DependencyGraphProof [EQUIVALENT, 0 ms] (37) QDP (38) SplitQDPProof [EQUIVALENT, 0 ms] (39) AND (40) QDP (41) SemLabProof [SOUND, 0 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) QDP (45) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (46) QDP (47) MRRProof [EQUIVALENT, 5 ms] (48) QDP (49) PisEmptyProof [SOUND, 0 ms] (50) TRUE (51) QDP (52) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (53) QDP (54) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms] (55) YES (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) QDPOrderProof [EQUIVALENT, 415 ms] (60) QDP (61) PisEmptyProof [EQUIVALENT, 0 ms] (62) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: g(c, g(c, x)) -> g(e, g(d, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(e, g(e, x)) -> g(d, g(c, x)) f(g(x, y)) -> g(y, g(f(f(x)), a)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) 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: G(c, g(c, x)) -> G(e, g(d, x)) G(c, g(c, x)) -> G(d, x) G(d, g(d, x)) -> G(c, g(e, x)) G(d, g(d, x)) -> G(e, x) G(e, g(e, x)) -> G(d, g(c, x)) G(e, g(e, x)) -> G(c, x) F(g(x, y)) -> G(y, g(f(f(x)), a)) F(g(x, y)) -> G(f(f(x)), a) F(g(x, y)) -> F(f(x)) F(g(x, y)) -> F(x) G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) G(x, g(y, g(x, y))) -> G(x, g(y, b)) G(x, g(y, g(x, y))) -> G(y, b) The TRS R consists of the following rules: g(c, g(c, x)) -> g(e, g(d, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(e, g(e, x)) -> g(d, g(c, x)) f(g(x, y)) -> g(y, g(f(f(x)), a)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) 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 3 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: G(e, g(e, x)) -> G(d, g(c, x)) G(d, g(d, x)) -> G(c, g(e, x)) G(c, g(c, x)) -> G(e, g(d, x)) G(e, g(e, x)) -> G(c, x) G(c, g(c, x)) -> G(d, x) G(d, g(d, x)) -> G(e, x) G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) G(x, g(y, g(x, y))) -> G(x, g(y, b)) The TRS R consists of the following rules: g(c, g(c, x)) -> g(e, g(d, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(e, g(e, x)) -> g(d, g(c, x)) f(g(x, y)) -> g(y, g(f(f(x)), a)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) 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(e, g(e, x)) -> G(d, g(c, x)) G(d, g(d, x)) -> G(c, g(e, x)) G(c, g(c, x)) -> G(e, g(d, x)) G(e, g(e, x)) -> G(c, x) G(c, g(c, x)) -> G(d, x) G(d, g(d, x)) -> G(e, x) G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) G(x, g(y, g(x, y))) -> G(x, g(y, b)) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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: G(e, g(e, x)) -> G(c, x) G(c, g(c, x)) -> G(d, x) G(d, g(d, x)) -> G(e, x) Used ordering: Polynomial interpretation [POLO]: POL(G(x_1, x_2)) = x_1 + 2*x_2 POL(a) = 0 POL(b) = 0 POL(c) = 1 POL(d) = 1 POL(e) = 1 POL(g(x_1, x_2)) = 2*x_1 + 2*x_2 ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: G(e, g(e, x)) -> G(d, g(c, x)) G(d, g(d, x)) -> G(c, g(e, x)) G(c, g(c, x)) -> G(e, g(d, x)) G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) G(x, g(y, g(x, y))) -> G(x, g(y, b)) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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: G(x, g(y, g(x, y))) -> G(x, g(y, b)) Used ordering: Polynomial interpretation [POLO]: POL(G(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a) = 0 POL(b) = 0 POL(c) = 0 POL(d) = 0 POL(e) = 0 POL(g(x_1, x_2)) = 2 + 2*x_1 + x_2 ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: G(e, g(e, x)) -> G(d, g(c, x)) G(d, g(d, x)) -> G(c, g(e, x)) G(c, g(c, x)) -> G(e, g(d, x)) G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (13) Complex Obligation (AND) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule G(x, g(y, g(x, y))) -> G(a, g(x, g(y, b))) we obtained the following new rules [LPAR04]: (G(a, g(x1, g(a, x1))) -> G(a, g(a, g(x1, b))),G(a, g(x1, g(a, x1))) -> G(a, g(a, g(x1, b)))) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: G(a, g(x1, g(a, x1))) -> G(a, g(a, g(x1, b))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (18) TRUE ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: G(d, g(d, x)) -> G(c, g(e, x)) G(c, g(c, x)) -> G(e, g(d, x)) G(e, g(e, x)) -> G(d, g(c, x)) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(d, g(d, x)) -> G(c, g(e, x)) at position [1] we obtained the following new rules [LPAR04]: (G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))),G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0)))) (G(d, g(d, g(x1, g(e, x1)))) -> G(c, g(a, g(e, g(x1, b)))),G(d, g(d, g(x1, g(e, x1)))) -> G(c, g(a, g(e, g(x1, b))))) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: G(c, g(c, x)) -> G(e, g(d, x)) G(e, g(e, x)) -> G(d, g(c, x)) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(d, g(d, g(x1, g(e, x1)))) -> G(c, g(a, g(e, g(x1, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(c, g(c, x)) -> G(e, g(d, x)) at position [1] we obtained the following new rules [LPAR04]: (G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))),G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0)))) (G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b)))),G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b))))) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: G(e, g(e, x)) -> G(d, g(c, x)) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(d, g(d, g(x1, g(e, x1)))) -> G(c, g(a, g(e, g(x1, b)))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(e, g(e, x)) -> G(d, g(c, x)) at position [1] we obtained the following new rules [LPAR04]: (G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))),G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0)))) (G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))),G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b))))) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(d, g(d, g(x1, g(e, x1)))) -> G(c, g(a, g(e, g(x1, b)))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b)))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(d, g(d, g(x1, g(e, x1)))) -> G(c, g(a, g(e, g(x1, b)))) at position [1] we obtained the following new rules [LPAR04]: (G(d, g(d, g(e, g(e, e)))) -> G(c, g(a, g(d, g(c, b)))),G(d, g(d, g(e, g(e, e)))) -> G(c, g(a, g(d, g(c, b))))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b)))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))) G(d, g(d, g(e, g(e, e)))) -> G(c, g(a, g(d, g(c, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, 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 1 SCC with 1 less node. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b)))) G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(c, g(c, g(x1, g(d, x1)))) -> G(e, g(a, g(d, g(x1, b)))) at position [1] we obtained the following new rules [LPAR04]: (G(c, g(c, g(d, g(d, d)))) -> G(e, g(a, g(c, g(e, b)))),G(c, g(c, g(d, g(d, d)))) -> G(e, g(a, g(c, g(e, b))))) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))) G(c, g(c, g(d, g(d, d)))) -> G(e, g(a, g(c, g(e, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule G(e, g(e, g(x1, g(c, x1)))) -> G(d, g(a, g(c, g(x1, b)))) at position [1] we obtained the following new rules [LPAR04]: (G(e, g(e, g(c, g(c, c)))) -> G(d, g(a, g(e, g(d, b)))),G(e, g(e, g(c, g(c, c)))) -> G(d, g(a, g(e, g(d, b))))) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(c, g(c, c)))) -> G(d, g(a, g(e, g(d, b)))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (39) Complex Obligation (AND) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) The TRS R consists of the following rules: g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) SemLabProof (SOUND) We found the following model for the rules of the TRSs R and P. Interpretation over the domain with elements from 0 to 1. a: 0 b: 1 c: 0 G: 0 d: 0 e: 0 g: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: G.0-0(d., g.0-0(d., g.0-0(e., x0))) -> G.0-0(c., g.0-0(d., g.0-0(c., x0))) G.0-0(c., g.0-0(c., g.0-0(d., x0))) -> G.0-0(e., g.0-0(c., g.0-0(e., x0))) G.0-0(c., g.0-0(c., g.0-1(d., x0))) -> G.0-0(e., g.0-0(c., g.0-1(e., x0))) G.0-0(d., g.0-0(d., g.0-1(e., x0))) -> G.0-0(c., g.0-0(d., g.0-1(c., x0))) G.0-0(e., g.0-0(e., g.0-0(c., x0))) -> G.0-0(d., g.0-0(e., g.0-0(d., x0))) G.0-0(e., g.0-0(e., g.0-1(c., x0))) -> G.0-0(d., g.0-0(e., g.0-1(d., x0))) The TRS R consists of the following rules: g.0-0(e., g.0-0(e., x)) -> g.0-0(d., g.0-0(c., x)) g.0-0(e., g.0-1(e., x)) -> g.0-0(d., g.0-1(c., x)) g.0-0(d., g.0-0(d., x)) -> g.0-0(c., g.0-0(e., x)) g.0-0(d., g.0-1(d., x)) -> g.0-0(c., g.0-1(e., x)) g.0-0(c., g.0-0(c., x)) -> g.0-0(e., g.0-0(d., x)) g.0-0(c., g.0-1(c., x)) -> g.0-0(e., g.0-1(d., x)) g.0-0(x, g.0-0(y, g.0-0(x, y))) -> g.0-0(a., g.0-0(x, g.0-1(y, b.))) g.0-0(x, g.1-0(y, g.0-1(x, y))) -> g.0-0(a., g.0-0(x, g.1-1(y, b.))) g.1-0(x, g.0-0(y, g.1-0(x, y))) -> g.0-0(a., g.1-0(x, g.0-1(y, b.))) g.1-0(x, g.1-0(y, g.1-1(x, y))) -> g.0-0(a., g.1-0(x, g.1-1(y, b.))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: G.0-0(c., g.0-0(c., g.0-0(d., x0))) -> G.0-0(e., g.0-0(c., g.0-0(e., x0))) G.0-0(e., g.0-0(e., g.0-0(c., x0))) -> G.0-0(d., g.0-0(e., g.0-0(d., x0))) G.0-0(d., g.0-0(d., g.0-0(e., x0))) -> G.0-0(c., g.0-0(d., g.0-0(c., x0))) The TRS R consists of the following rules: g.0-0(e., g.0-0(e., x)) -> g.0-0(d., g.0-0(c., x)) g.0-0(e., g.0-1(e., x)) -> g.0-0(d., g.0-1(c., x)) g.0-0(d., g.0-0(d., x)) -> g.0-0(c., g.0-0(e., x)) g.0-0(d., g.0-1(d., x)) -> g.0-0(c., g.0-1(e., x)) g.0-0(c., g.0-0(c., x)) -> g.0-0(e., g.0-0(d., x)) g.0-0(c., g.0-1(c., x)) -> g.0-0(e., g.0-1(d., x)) g.0-0(x, g.0-0(y, g.0-0(x, y))) -> g.0-0(a., g.0-0(x, g.0-1(y, b.))) g.0-0(x, g.1-0(y, g.0-1(x, y))) -> g.0-0(a., g.0-0(x, g.1-1(y, b.))) g.1-0(x, g.0-0(y, g.1-0(x, y))) -> g.0-0(a., g.1-0(x, g.0-1(y, b.))) g.1-0(x, g.1-0(y, g.1-1(x, y))) -> g.0-0(a., g.1-0(x, g.1-1(y, b.))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) 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: g.0-0(x, g.1-0(y, g.0-1(x, y))) -> g.0-0(a., g.0-0(x, g.1-1(y, b.))) g.1-0(x, g.0-0(y, g.1-0(x, y))) -> g.0-0(a., g.1-0(x, g.0-1(y, b.))) g.1-0(x, g.1-0(y, g.1-1(x, y))) -> g.0-0(a., g.1-0(x, g.1-1(y, b.))) Used ordering: POLO with Polynomial interpretation [POLO]: POL(G.0-0(x_1, x_2)) = x_1 + x_2 POL(a.) = 0 POL(b.) = 0 POL(c.) = 1 POL(d.) = 1 POL(e.) = 1 POL(g.0-0(x_1, x_2)) = 1 + x_1 + x_2 POL(g.0-1(x_1, x_2)) = 1 + x_1 + x_2 POL(g.1-0(x_1, x_2)) = 1 + x_1 + x_2 POL(g.1-1(x_1, x_2)) = 1 + x_1 + x_2 ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: G.0-0(c., g.0-0(c., g.0-0(d., x0))) -> G.0-0(e., g.0-0(c., g.0-0(e., x0))) G.0-0(e., g.0-0(e., g.0-0(c., x0))) -> G.0-0(d., g.0-0(e., g.0-0(d., x0))) G.0-0(d., g.0-0(d., g.0-0(e., x0))) -> G.0-0(c., g.0-0(d., g.0-0(c., x0))) The TRS R consists of the following rules: g.0-0(d., g.0-0(d., x)) -> g.0-0(c., g.0-0(e., x)) g.0-0(c., g.0-0(c., x)) -> g.0-0(e., g.0-0(d., x)) g.0-0(e., g.0-0(e., x)) -> g.0-0(d., g.0-0(c., x)) g.0-0(c., g.0-1(c., x)) -> g.0-0(e., g.0-1(d., x)) g.0-0(x, g.0-0(y, g.0-0(x, y))) -> g.0-0(a., g.0-0(x, g.0-1(y, b.))) g.0-0(d., g.0-1(d., x)) -> g.0-0(c., g.0-1(e., x)) g.0-0(e., g.0-1(e., x)) -> g.0-0(d., g.0-1(c., x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) 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: g.0-0(x, g.0-0(y, g.0-0(x, y))) -> g.0-0(a., g.0-0(x, g.0-1(y, b.))) Used ordering: Polynomial interpretation [POLO]: POL(G.0-0(x_1, x_2)) = x_1 + x_2 POL(a.) = 0 POL(b.) = 0 POL(c.) = 1 POL(d.) = 1 POL(e.) = 1 POL(g.0-0(x_1, x_2)) = 1 + x_1 + x_2 POL(g.0-1(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: G.0-0(c., g.0-0(c., g.0-0(d., x0))) -> G.0-0(e., g.0-0(c., g.0-0(e., x0))) G.0-0(e., g.0-0(e., g.0-0(c., x0))) -> G.0-0(d., g.0-0(e., g.0-0(d., x0))) G.0-0(d., g.0-0(d., g.0-0(e., x0))) -> G.0-0(c., g.0-0(d., g.0-0(c., x0))) The TRS R consists of the following rules: g.0-0(d., g.0-0(d., x)) -> g.0-0(c., g.0-0(e., x)) g.0-0(c., g.0-0(c., x)) -> g.0-0(e., g.0-0(d., x)) g.0-0(e., g.0-0(e., x)) -> g.0-0(d., g.0-0(c., x)) g.0-0(c., g.0-1(c., x)) -> g.0-0(e., g.0-1(d., x)) g.0-0(d., g.0-1(d., x)) -> g.0-0(c., g.0-1(e., x)) g.0-0(e., g.0-1(e., x)) -> g.0-0(d., g.0-1(c., x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (50) TRUE ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: G(c, g(c, g(d, x0))) -> G(e, g(c, g(e, x0))) G(e, g(e, g(c, x0))) -> G(d, g(e, g(d, x0))) G(d, g(d, g(e, x0))) -> G(c, g(d, g(c, x0))) The TRS R consists of the following rules: g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(e, g(e, x)) -> g(d, g(c, x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) UsableRulesReductionPairsProof (EQUIVALENT) First, we A-transformed [FROCOS05] the QDP-Problem. Then we obtain the following A-transformed DP problem. The pairs P are: c1(c(d(x0))) -> e1(c(e(x0))) e1(e(c(x0))) -> d1(e(d(x0))) d1(d(e(x0))) -> c1(d(c(x0))) and the Q and R are: Q restricted rewrite system: The TRS R consists of the following rules: c(c(x)) -> e(d(x)) e(e(x)) -> d(c(x)) d(d(x)) -> c(e(x)) Q is empty. 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: g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(e, g(e, x)) -> g(d, g(c, x)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(c(x_1)) = x_1 POL(c1(x_1)) = 2*x_1 POL(d(x_1)) = x_1 POL(d1(x_1)) = 2*x_1 POL(e(x_1)) = x_1 POL(e1(x_1)) = 2*x_1 ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: c1(c(d(x0))) -> e1(c(e(x0))) e1(e(c(x0))) -> d1(e(d(x0))) d1(d(e(x0))) -> c1(d(c(x0))) The TRS R consists of the following rules: c(c(x)) -> e(d(x)) e(e(x)) -> d(c(x)) d(d(x)) -> c(e(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) RFCMatchBoundsDPProof (EQUIVALENT) Finiteness of the DP problem can be shown by a matchbound of 1. As the DP problem is minimal we only have to initialize the certificate graph by the rules of P: c1(c(d(x0))) -> e1(c(e(x0))) e1(e(c(x0))) -> d1(e(d(x0))) d1(d(e(x0))) -> c1(d(c(x0))) To find matches we regarded all rules of R and P: c(c(x)) -> e(d(x)) e(e(x)) -> d(c(x)) d(d(x)) -> c(e(x)) c1(c(d(x0))) -> e1(c(e(x0))) e1(e(c(x0))) -> d1(e(d(x0))) d1(d(e(x0))) -> c1(d(c(x0))) The certificate found is represented by the following graph. The certificate consists of the following enumerated nodes: 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496 Node 486 is start node and node 487 is final node. Those nodes are connected through the following edges: * 486 to 488 labelled e1_1(0)* 486 to 490 labelled d1_1(0)* 486 to 492 labelled c1_1(0)* 487 to 487 labelled #_1(0)* 488 to 489 labelled c_1(0)* 489 to 487 labelled e_1(0)* 489 to 494 labelled d_1(1)* 490 to 491 labelled e_1(0)* 491 to 487 labelled d_1(0)* 491 to 495 labelled c_1(1)* 492 to 493 labelled d_1(0)* 493 to 487 labelled c_1(0)* 493 to 496 labelled e_1(1)* 494 to 487 labelled c_1(1)* 494 to 496 labelled e_1(1)* 495 to 487 labelled e_1(1)* 495 to 494 labelled d_1(1)* 496 to 487 labelled d_1(1)* 496 to 495 labelled c_1(1) ---------------------------------------- (55) YES ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(x, y)) -> F(x) F(g(x, y)) -> F(f(x)) The TRS R consists of the following rules: g(c, g(c, x)) -> g(e, g(d, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(e, g(e, x)) -> g(d, g(c, x)) f(g(x, y)) -> g(y, g(f(f(x)), a)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule F(g(x, y)) -> F(f(x)) at position [0] we obtained the following new rules [LPAR04]: (F(g(g(x0, x1), y1)) -> F(g(x1, g(f(f(x0)), a))),F(g(g(x0, x1), y1)) -> F(g(x1, g(f(f(x0)), a)))) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(x, y)) -> F(x) F(g(g(x0, x1), y1)) -> F(g(x1, g(f(f(x0)), a))) The TRS R consists of the following rules: g(c, g(c, x)) -> g(e, g(d, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(e, g(e, x)) -> g(d, g(c, x)) f(g(x, y)) -> g(y, g(f(f(x)), a)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F(g(x, y)) -> F(x) F(g(g(x0, x1), y1)) -> F(g(x1, g(f(f(x0)), a))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(F(x_1)) = [[0]] + [[2, 0]] * x_1 >>> <<< POL(g(x_1, x_2)) = [[1], [1]] + [[1, 1], [0, 0]] * x_1 + [[0, 0], [1, 1]] * x_2 >>> <<< POL(f(x_1)) = [[0], [0]] + [[0, 1], [3, 0]] * x_1 >>> <<< POL(a) = [[0], [0]] >>> <<< POL(e) = [[0], [0]] >>> <<< POL(d) = [[0], [0]] >>> <<< POL(c) = [[0], [0]] >>> <<< POL(b) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f(g(x, y)) -> g(y, g(f(f(x)), a)) g(e, g(e, x)) -> g(d, g(c, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(c, g(c, x)) -> g(e, g(d, x)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) ---------------------------------------- (60) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: g(c, g(c, x)) -> g(e, g(d, x)) g(d, g(d, x)) -> g(c, g(e, x)) g(e, g(e, x)) -> g(d, g(c, x)) f(g(x, y)) -> g(y, g(f(f(x)), a)) g(x, g(y, g(x, y))) -> g(a, g(x, g(y, b))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (62) YES