/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 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) TransformationProof [SOUND, 3 ms] (16) QDP (17) MRRProof [EQUIVALENT, 28 ms] (18) QDP (19) QReductionProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) QReductionProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) QDP (45) QReductionProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 0 ms] (48) QDP (49) UsableRulesProof [EQUIVALENT, 0 ms] (50) QDP (51) QReductionProof [EQUIVALENT, 0 ms] (52) QDP (53) TransformationProof [EQUIVALENT, 0 ms] (54) QDP (55) DependencyGraphProof [EQUIVALENT, 0 ms] (56) TRUE ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: 0 -> b(0, 0) b(b(x, y), z) -> c b(x, b(y, z)) -> c 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(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) reduce(0) -> go_up(b(0, 0)) redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_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(b(x_1, x_2)) -> CHECK_B(redex_b(x_1, x_2)) REDUCE(b(x_1, x_2)) -> REDEX_B(x_1, x_2) CHECK_B(redex_b(x_1, x_2)) -> IN_B_1(reduce(x_1), x_2) CHECK_B(redex_b(x_1, x_2)) -> REDUCE(x_1) CHECK_B(redex_b(x_1, x_2)) -> IN_B_2(x_1, reduce(x_2)) CHECK_B(redex_b(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) reduce(0) -> go_up(b(0, 0)) redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_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(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) reduce(0) -> go_up(b(0, 0)) redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_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(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) reduce(0) -> go_up(b(0, 0)) redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_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)) ---------------------------------------- (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(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) reduce(0) -> go_up(b(0, 0)) redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) 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(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))),TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1)))) (TOP(go_up(0)) -> TOP(go_up(b(0, 0))),TOP(go_up(0)) -> TOP(go_up(b(0, 0)))) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))) TOP(go_up(0)) -> TOP(go_up(b(0, 0))) The TRS R consists of the following rules: reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) reduce(0) -> go_up(b(0, 0)) redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(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: TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))) TOP(go_up(0)) -> TOP(go_up(b(0, 0))) The TRS R consists of the following rules: redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) TransformationProof (SOUND) By narrowing [LPAR04] the rule TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)),TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1))) (TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))),TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1)))) (TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))),TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c)))) (TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))),TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c)))) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(0)) -> TOP(go_up(b(0, 0))) TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) The TRS R consists of the following rules: redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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: redex_b(b(x, y), z) -> result_b(c) redex_b(x, b(y, z)) -> result_b(c) check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(TOP(x_1)) = 2*x_1 POL(b(x_1, x_2)) = 2*x_1 + 2*x_2 POL(c) = 0 POL(check_b(x_1)) = 2*x_1 POL(go_up(x_1)) = x_1 POL(in_b_1(x_1, x_2)) = 2*x_1 + 2*x_2 POL(in_b_2(x_1, x_2)) = 2*x_1 + 2*x_2 POL(redex_b(x_1, x_2)) = 2 + x_1 + x_2 POL(reduce(x_1)) = x_1 POL(result_b(x_1)) = x_1 ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(0)) -> TOP(go_up(b(0, 0))) TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) The TRS R consists of the following rules: check_b(result_b(x)) -> go_up(x) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) redex_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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_b(b(x0, x1), x2) redex_b(x0, b(x1, x2)) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(0)) -> TOP(go_up(b(0, 0))) TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) The TRS R consists of the following rules: check_b(result_b(x)) -> go_up(x) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(b(x0, x1), x2))) -> TOP(go_up(c)),TOP(go_up(b(b(x0, x1), x2))) -> TOP(go_up(c))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(0)) -> TOP(go_up(b(0, 0))) TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) TOP(go_up(b(b(x0, x1), x2))) -> TOP(go_up(c)) The TRS R consists of the following rules: check_b(result_b(x)) -> go_up(x) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) TOP(go_up(0)) -> TOP(go_up(b(0, 0))) The TRS R consists of the following rules: check_b(result_b(x)) -> go_up(x) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(x0, b(x1, x2)))) -> TOP(go_up(c)),TOP(go_up(b(x0, b(x1, x2)))) -> TOP(go_up(c))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(0)) -> TOP(go_up(b(0, 0))) TOP(go_up(b(x0, b(x1, x2)))) -> TOP(go_up(c)) The TRS R consists of the following rules: check_b(result_b(x)) -> go_up(x) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) The TRS R consists of the following rules: check_b(result_b(x)) -> go_up(x) reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) check_b(result_b(x0)) check_b(redex_b(x0, x1)) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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_b(result_b(x0)) check_b(redex_b(x0, x1)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1)),TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1)) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1)) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))),TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1)))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_1(go_up(x0), x1) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) 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]. in_b_1(go_up(x0), x1) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))),TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0))))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) The TRS R consists of the following rules: reduce(0) -> go_up(b(0, 0)) in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) 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. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) The TRS R consists of the following rules: in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: reduce(b(x0, x1)) reduce(0) in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) 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(b(x0, x1)) reduce(0) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) The TRS R consists of the following rules: in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))),TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0))))) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) The TRS R consists of the following rules: in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) The set Q consists of the following terms: in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) 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. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) R is empty. The set Q consists of the following terms: in_b_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) 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]. in_b_2(x0, go_up(x1)) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) we obtained the following new rules [LPAR04]: (TOP(go_up(b(0, b(0, 0)))) -> TOP(go_up(b(b(0, 0), b(0, 0)))),TOP(go_up(b(0, b(0, 0)))) -> TOP(go_up(b(b(0, 0), b(0, 0))))) ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) TOP(go_up(b(0, b(0, 0)))) -> TOP(go_up(b(b(0, 0), b(0, 0)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (56) TRUE