/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 Outermost Termination of the given OTRS could be proven: (0) OTRS (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) QReductionProof [EQUIVALENT, 0 ms] (10) QDP (11) TransformationProof [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) UsableRulesProof [EQUIVALENT, 0 ms] (20) QDP (21) QReductionProof [EQUIVALENT, 0 ms] (22) QDP (23) TransformationProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) QReductionProof [EQUIVALENT, 0 ms] (30) QDP (31) QDPOrderProof [EQUIVALENT, 3 ms] (32) QDP (33) DependencyGraphProof [EQUIVALENT, 0 ms] (34) TRUE ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: g(x, x) -> g(g(x, x), x) g(x, y) -> y Outermost Strategy. ---------------------------------------- (1) Thiemann-SpecialC-Transformation (EQUIVALENT) We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) TOP(go_up(x)) -> REDUCE(x) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) REDUCE(g(x_1, x_2)) -> REDEX_G(x_1, x_2) CHECK_G(redex_g(x_1, x_2)) -> IN_G_1(reduce(x_1), x_2) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> IN_G_2(x_1, reduce(x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) 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. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: top(go_up(x0)) reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) 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]. top(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))),TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1)))) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) The TRS R consists of the following rules: reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) 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: TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) The TRS R consists of the following rules: redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: reduce(g(x0, x1)) redex_g(x0, x1) check_g(result_g(x0)) 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]. reduce(g(x0, x1)) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) The TRS R consists of the following rules: redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: redex_g(x0, x1) check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(go_up(g(x0, x0))) -> TOP(check_g(result_g(g(g(x0, x0), x0)))),TOP(go_up(g(x0, x0))) -> TOP(check_g(result_g(g(g(x0, x0), x0))))) (TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1))),TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1)))) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(check_g(result_g(g(g(x0, x0), x0)))) TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1))) The TRS R consists of the following rules: redex_g(x, x) -> result_g(g(g(x, x), x)) redex_g(x, y) -> result_g(y) check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: redex_g(x0, x1) check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(check_g(result_g(g(g(x0, x0), x0)))) TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1))) The TRS R consists of the following rules: check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: redex_g(x0, x1) check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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]. redex_g(x0, x1) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(check_g(result_g(g(g(x0, x0), x0)))) TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1))) The TRS R consists of the following rules: check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(g(x0, x0))) -> TOP(check_g(result_g(g(g(x0, x0), x0)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0))),TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0)))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1))) TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0))) The TRS R consists of the following rules: check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(g(x0, x1))) -> TOP(check_g(result_g(x1))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(g(x0, x1))) -> TOP(go_up(x1)),TOP(go_up(g(x0, x1))) -> TOP(go_up(x1))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0))) TOP(go_up(g(x0, x1))) -> TOP(go_up(x1)) The TRS R consists of the following rules: check_g(result_g(x)) -> go_up(x) The set Q consists of the following terms: check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) 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. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0))) TOP(go_up(g(x0, x1))) -> TOP(go_up(x1)) R is empty. The set Q consists of the following terms: check_g(result_g(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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]. check_g(result_g(x0)) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0))) TOP(go_up(g(x0, x1))) -> TOP(go_up(x1)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(go_up(g(x0, x1))) -> TOP(go_up(x1)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(g(x_1, x_2)) = 1 + x_2 POL(go_up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x0))) -> TOP(go_up(g(g(x0, x0), x0))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (34) TRUE