/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) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) TRUE (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 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) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) DependencyGraphProof [EQUIVALENT, 0 ms] (32) QDP (33) SemLabProof [SOUND, 148 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 62 ms] (36) QDP (37) PisEmptyProof [EQUIVALENT, 0 ms] (38) YES ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(0, 1, x) -> f(x, x, x) f(x, y, z) -> 2 0 -> 2 1 -> 2 g(x, x, y) -> y g(x, y, y) -> x 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(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) ---------------------------------------- (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(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) REDUCE(f(x_1, x_2, x_3)) -> REDEX_F(x_1, x_2, x_3) REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) REDUCE(g(x_1, x_2, x_3)) -> REDEX_G(x_1, x_2, x_3) CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_1(reduce(x_1), x_2, x_3) CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_2(x_1, reduce(x_2), x_3) CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_3(x_1, x_2, reduce(x_3)) CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) CHECK_G(redex_g(x_1, x_2, x_3)) -> IN_G_1(reduce(x_1), x_2, x_3) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2, x_3)) -> IN_G_2(x_1, reduce(x_2), x_3) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) CHECK_G(redex_g(x_1, x_2, x_3)) -> IN_G_3(x_1, x_2, reduce(x_3)) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 13 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) The TRS R consists of the following rules: redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) The TRS R consists of the following rules: redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) The set Q consists of the following terms: redex_g(x0, x0, x1) redex_g(x0, x1, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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. The following dependency pairs can be deleted: REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_G(x_1)) = 2*x_1 POL(REDUCE(x_1)) = 2*x_1 POL(g(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(redex_g(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(result_g(x_1)) = x_1 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) The TRS R consists of the following rules: redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) The set Q consists of the following terms: redex_g(x0, x0, x1) redex_g(x0, x1, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (15) TRUE ---------------------------------------- (16) 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(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) 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(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) 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]. top(go_up(x0)) in_f_1(go_up(x0), x1, x2) in_f_2(x0, go_up(x1), x2) in_f_3(x0, x1, go_up(x2)) ---------------------------------------- (20) 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(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))),TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2)))) (TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))),TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2)))) (TOP(go_up(0)) -> TOP(go_up(2)),TOP(go_up(0)) -> TOP(go_up(2))) (TOP(go_up(1)) -> TOP(go_up(2)),TOP(go_up(1)) -> TOP(go_up(2))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) TOP(go_up(0)) -> TOP(go_up(2)) TOP(go_up(1)) -> TOP(go_up(2)) The TRS R consists of the following rules: reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) 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 2 less nodes. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) The TRS R consists of the following rules: reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(go_up(f(0, 1, x0))) -> TOP(check_f(result_f(f(x0, x0, x0)))),TOP(go_up(f(0, 1, x0))) -> TOP(check_f(result_f(f(x0, x0, x0))))) (TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2))),TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2)))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) TOP(go_up(f(0, 1, x0))) -> TOP(check_f(result_f(f(x0, x0, x0)))) TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2))) The TRS R consists of the following rules: reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(f(0, 1, x0))) -> TOP(check_f(result_f(f(x0, x0, x0)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(f(0, 1, x0))) -> TOP(go_up(f(x0, x0, x0))),TOP(go_up(f(0, 1, x0))) -> TOP(go_up(f(x0, x0, x0)))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2))) TOP(go_up(f(0, 1, x0))) -> TOP(go_up(f(x0, x0, x0))) The TRS R consists of the following rules: reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2))) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(f(x0, x1, x2))) -> TOP(go_up(2)),TOP(go_up(f(x0, x1, x2))) -> TOP(go_up(2))) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) TOP(go_up(f(0, 1, x0))) -> TOP(go_up(f(x0, x0, x0))) TOP(go_up(f(x0, x1, x2))) -> TOP(go_up(2)) The TRS R consists of the following rules: reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) The TRS R consists of the following rules: reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) reduce(0) -> go_up(2) reduce(1) -> go_up(2) redex_g(x, x, y) -> result_g(y) redex_g(x, y, y) -> result_g(x) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) redex_f(0, 1, x) -> result_f(f(x, x, x)) redex_f(x, y, z) -> result_f(2) check_f(result_f(x)) -> go_up(x) The set Q consists of the following terms: reduce(f(x0, x1, x2)) reduce(g(x0, x1, x2)) redex_f(x0, x1, x2) reduce(0) reduce(1) redex_g(x0, x0, x1) redex_g(x0, x1, x1) check_f(result_f(x0)) check_g(result_g(x0)) check_g(redex_g(x0, x1, x2)) in_g_1(go_up(x0), x1, x2) in_g_2(x0, go_up(x1), x2) in_g_3(x0, x1, go_up(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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. result_f: 0 reduce: 0 in_g_1: 0 in_g_3: 0 redex_f: 0 2: 0 check_f: 0 in_g_2: 0 TOP: 0 g: 0 go_up: 0 result_g: 0 f: 0 0: 0 1: 1 check_g: 0 redex_g: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(go_up.0(g.0-0-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-0-0(x0, x1, x2))) TOP.0(go_up.0(g.0-0-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-0-1(x0, x1, x2))) TOP.0(go_up.0(g.0-1-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-1-0(x0, x1, x2))) TOP.0(go_up.0(g.0-1-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-1-1(x0, x1, x2))) TOP.0(go_up.0(g.1-0-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-0-0(x0, x1, x2))) TOP.0(go_up.0(g.1-0-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-0-1(x0, x1, x2))) TOP.0(go_up.0(g.1-1-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-1-0(x0, x1, x2))) TOP.0(go_up.0(g.1-1-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-1-1(x0, x1, x2))) The TRS R consists of the following rules: reduce.0(f.0-0-0(x_1, x_2, x_3)) -> check_f.0(redex_f.0-0-0(x_1, x_2, x_3)) reduce.0(f.0-0-1(x_1, x_2, x_3)) -> check_f.0(redex_f.0-0-1(x_1, x_2, x_3)) reduce.0(f.0-1-0(x_1, x_2, x_3)) -> check_f.0(redex_f.0-1-0(x_1, x_2, x_3)) reduce.0(f.0-1-1(x_1, x_2, x_3)) -> check_f.0(redex_f.0-1-1(x_1, x_2, x_3)) reduce.0(f.1-0-0(x_1, x_2, x_3)) -> check_f.0(redex_f.1-0-0(x_1, x_2, x_3)) reduce.0(f.1-0-1(x_1, x_2, x_3)) -> check_f.0(redex_f.1-0-1(x_1, x_2, x_3)) reduce.0(f.1-1-0(x_1, x_2, x_3)) -> check_f.0(redex_f.1-1-0(x_1, x_2, x_3)) reduce.0(f.1-1-1(x_1, x_2, x_3)) -> check_f.0(redex_f.1-1-1(x_1, x_2, x_3)) reduce.0(g.0-0-0(x_1, x_2, x_3)) -> check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) reduce.0(g.0-0-1(x_1, x_2, x_3)) -> check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) reduce.0(g.0-1-0(x_1, x_2, x_3)) -> check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) reduce.0(g.0-1-1(x_1, x_2, x_3)) -> check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) reduce.0(g.1-0-0(x_1, x_2, x_3)) -> check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) reduce.0(g.1-0-1(x_1, x_2, x_3)) -> check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) reduce.0(g.1-1-0(x_1, x_2, x_3)) -> check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) reduce.0(g.1-1-1(x_1, x_2, x_3)) -> check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) reduce.0(0.) -> go_up.0(2.) reduce.1(1.) -> go_up.0(2.) redex_g.0-0-0(x, x, y) -> result_g.0(y) redex_g.0-0-1(x, x, y) -> result_g.1(y) redex_g.1-1-0(x, x, y) -> result_g.0(y) redex_g.1-1-1(x, x, y) -> result_g.1(y) redex_g.0-0-0(x, y, y) -> result_g.0(x) redex_g.0-1-1(x, y, y) -> result_g.0(x) redex_g.1-0-0(x, y, y) -> result_g.1(x) redex_g.1-1-1(x, y, y) -> result_g.1(x) check_g.0(result_g.0(x)) -> go_up.0(x) check_g.0(result_g.1(x)) -> go_up.1(x) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_1.0-0-0(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_1.0-0-1(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_1.0-1-0(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_1.0-1-1(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_1.0-0-0(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_1.0-0-1(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_1.0-1-0(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_1.0-1-1(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_2.0-0-0(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_2.0-0-1(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_2.0-0-0(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_2.0-0-1(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_2.1-0-0(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_2.1-0-1(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_2.1-0-0(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_2.1-0-1(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_3.0-0-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_3.0-0-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_3.0-1-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_3.0-1-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_3.1-0-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_3.1-0-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_3.1-1-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_3.1-1-0(x_1, x_2, reduce.1(x_3)) in_g_3.0-0-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_3.0-0-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_3.0-1-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_3.0-1-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_3.1-0-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_3.1-0-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_3.1-1-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_3.1-1-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) in_g_2.0-0-0(x_1, go_up.0(x_2), x_3) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_2.0-0-1(x_1, go_up.0(x_2), x_3) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_2.0-0-0(x_1, go_up.1(x_2), x_3) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_2.0-0-1(x_1, go_up.1(x_2), x_3) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_2.1-0-0(x_1, go_up.0(x_2), x_3) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_2.1-0-1(x_1, go_up.0(x_2), x_3) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_2.1-0-0(x_1, go_up.1(x_2), x_3) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_2.1-0-1(x_1, go_up.1(x_2), x_3) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) in_g_1.0-0-0(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_1.0-0-1(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_1.0-1-0(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_1.0-1-1(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_1.0-0-0(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_1.0-0-1(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_1.0-1-0(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_1.0-1-1(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) redex_f.0-1-0(0., 1., x) -> result_f.0(f.0-0-0(x, x, x)) redex_f.0-1-1(0., 1., x) -> result_f.0(f.1-1-1(x, x, x)) redex_f.0-0-0(x, y, z) -> result_f.0(2.) redex_f.0-0-1(x, y, z) -> result_f.0(2.) redex_f.0-1-0(x, y, z) -> result_f.0(2.) redex_f.0-1-1(x, y, z) -> result_f.0(2.) redex_f.1-0-0(x, y, z) -> result_f.0(2.) redex_f.1-0-1(x, y, z) -> result_f.0(2.) redex_f.1-1-0(x, y, z) -> result_f.0(2.) redex_f.1-1-1(x, y, z) -> result_f.0(2.) check_f.0(result_f.0(x)) -> go_up.0(x) check_f.0(result_f.1(x)) -> go_up.1(x) The set Q consists of the following terms: reduce.0(f.0-0-0(x0, x1, x2)) reduce.0(f.0-0-1(x0, x1, x2)) reduce.0(f.0-1-0(x0, x1, x2)) reduce.0(f.0-1-1(x0, x1, x2)) reduce.0(f.1-0-0(x0, x1, x2)) reduce.0(f.1-0-1(x0, x1, x2)) reduce.0(f.1-1-0(x0, x1, x2)) reduce.0(f.1-1-1(x0, x1, x2)) reduce.0(g.0-0-0(x0, x1, x2)) reduce.0(g.0-0-1(x0, x1, x2)) reduce.0(g.0-1-0(x0, x1, x2)) reduce.0(g.0-1-1(x0, x1, x2)) reduce.0(g.1-0-0(x0, x1, x2)) reduce.0(g.1-0-1(x0, x1, x2)) reduce.0(g.1-1-0(x0, x1, x2)) reduce.0(g.1-1-1(x0, x1, x2)) redex_f.0-0-0(x0, x1, x2) redex_f.0-0-1(x0, x1, x2) redex_f.0-1-0(x0, x1, x2) redex_f.0-1-1(x0, x1, x2) redex_f.1-0-0(x0, x1, x2) redex_f.1-0-1(x0, x1, x2) redex_f.1-1-0(x0, x1, x2) redex_f.1-1-1(x0, x1, x2) reduce.0(0.) reduce.1(1.) redex_g.0-0-0(x0, x0, x1) redex_g.0-0-1(x0, x0, x1) redex_g.1-1-0(x0, x0, x1) redex_g.1-1-1(x0, x0, x1) redex_g.0-0-0(x0, x1, x1) redex_g.0-1-1(x0, x1, x1) redex_g.1-0-0(x0, x1, x1) redex_g.1-1-1(x0, x1, x1) check_f.0(result_f.0(x0)) check_f.0(result_f.1(x0)) check_g.0(result_g.0(x0)) check_g.0(result_g.1(x0)) check_g.0(redex_g.0-0-0(x0, x1, x2)) check_g.0(redex_g.0-0-1(x0, x1, x2)) check_g.0(redex_g.0-1-0(x0, x1, x2)) check_g.0(redex_g.0-1-1(x0, x1, x2)) check_g.0(redex_g.1-0-0(x0, x1, x2)) check_g.0(redex_g.1-0-1(x0, x1, x2)) check_g.0(redex_g.1-1-0(x0, x1, x2)) check_g.0(redex_g.1-1-1(x0, x1, x2)) in_g_1.0-0-0(go_up.0(x0), x1, x2) in_g_1.0-0-1(go_up.0(x0), x1, x2) in_g_1.0-1-0(go_up.0(x0), x1, x2) in_g_1.0-1-1(go_up.0(x0), x1, x2) in_g_1.0-0-0(go_up.1(x0), x1, x2) in_g_1.0-0-1(go_up.1(x0), x1, x2) in_g_1.0-1-0(go_up.1(x0), x1, x2) in_g_1.0-1-1(go_up.1(x0), x1, x2) in_g_2.0-0-0(x0, go_up.0(x1), x2) in_g_2.0-0-1(x0, go_up.0(x1), x2) in_g_2.0-0-0(x0, go_up.1(x1), x2) in_g_2.0-0-1(x0, go_up.1(x1), x2) in_g_2.1-0-0(x0, go_up.0(x1), x2) in_g_2.1-0-1(x0, go_up.0(x1), x2) in_g_2.1-0-0(x0, go_up.1(x1), x2) in_g_2.1-0-1(x0, go_up.1(x1), x2) in_g_3.0-0-0(x0, x1, go_up.0(x2)) in_g_3.0-0-0(x0, x1, go_up.1(x2)) in_g_3.0-1-0(x0, x1, go_up.0(x2)) in_g_3.0-1-0(x0, x1, go_up.1(x2)) in_g_3.1-0-0(x0, x1, go_up.0(x2)) in_g_3.1-0-0(x0, x1, go_up.1(x2)) in_g_3.1-1-0(x0, x1, go_up.0(x2)) in_g_3.1-1-0(x0, x1, go_up.1(x2)) 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. TOP.0(go_up.0(g.0-0-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-0-0(x0, x1, x2))) TOP.0(go_up.0(g.0-0-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-0-1(x0, x1, x2))) TOP.0(go_up.0(g.0-1-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-1-0(x0, x1, x2))) TOP.0(go_up.0(g.0-1-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.0-1-1(x0, x1, x2))) TOP.0(go_up.0(g.1-0-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-0-0(x0, x1, x2))) TOP.0(go_up.0(g.1-0-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-0-1(x0, x1, x2))) TOP.0(go_up.0(g.1-1-0(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-1-0(x0, x1, x2))) TOP.0(go_up.0(g.1-1-1(x0, x1, x2))) -> TOP.0(check_g.0(redex_g.1-1-1(x0, x1, x2))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0.) = 1 POL(1.) = 1 POL(2.) = 0 POL(TOP.0(x_1)) = x_1 POL(check_f.0(x_1)) = 1 + x_1 POL(check_g.0(x_1)) = x_1 POL(f.0-0-0(x_1, x_2, x_3)) = 1 + x_2 POL(f.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f.1-1-1(x_1, x_2, x_3)) = 1 + x_1 POL(g.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g.1-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(go_up.0(x_1)) = 1 + x_1 POL(go_up.1(x_1)) = 1 + x_1 POL(in_g_1.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_1.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_1.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_1.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_2.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_2.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_2.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_2.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_3.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_3.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_3.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(in_g_3.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_f.0-0-0(x_1, x_2, x_3)) = 0 POL(redex_f.0-0-1(x_1, x_2, x_3)) = 0 POL(redex_f.0-1-0(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(redex_f.0-1-1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(redex_f.1-0-0(x_1, x_2, x_3)) = 0 POL(redex_f.1-0-1(x_1, x_2, x_3)) = 0 POL(redex_f.1-1-0(x_1, x_2, x_3)) = 0 POL(redex_f.1-1-1(x_1, x_2, x_3)) = 0 POL(redex_g.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(redex_g.1-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(reduce.0(x_1)) = x_1 POL(reduce.1(x_1)) = x_1 POL(result_f.0(x_1)) = x_1 POL(result_f.1(x_1)) = 1 + x_1 POL(result_g.0(x_1)) = 1 + x_1 POL(result_g.1(x_1)) = 1 + x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: redex_g.0-0-0(x, x, y) -> result_g.0(y) redex_g.0-0-0(x, y, y) -> result_g.0(x) check_g.0(result_g.0(x)) -> go_up.0(x) check_g.0(result_g.1(x)) -> go_up.1(x) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_1.0-0-0(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_1.0-0-1(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_1.0-1-0(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_1.0-1-1(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_1.0-0-0(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_1.0-0-1(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_1.0-1-0(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_1.0-1-1(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_2.0-0-0(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_2.0-0-1(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_2.0-0-0(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_2.0-0-1(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_2.1-0-0(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_2.1-0-1(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_2.1-0-0(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_2.1-0-1(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_3.0-0-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_3.0-0-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_3.0-1-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_3.0-1-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_3.1-0-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_3.1-0-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_3.1-1-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_3.1-1-0(x_1, x_2, reduce.1(x_3)) redex_g.0-0-1(x, x, y) -> result_g.1(y) redex_g.0-1-1(x, y, y) -> result_g.0(x) redex_g.1-0-0(x, y, y) -> result_g.1(x) redex_g.1-1-0(x, x, y) -> result_g.0(y) redex_g.1-1-1(x, x, y) -> result_g.1(y) redex_g.1-1-1(x, y, y) -> result_g.1(x) reduce.0(g.0-0-0(x_1, x_2, x_3)) -> check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) reduce.0(f.0-0-0(x_1, x_2, x_3)) -> check_f.0(redex_f.0-0-0(x_1, x_2, x_3)) reduce.0(f.0-0-1(x_1, x_2, x_3)) -> check_f.0(redex_f.0-0-1(x_1, x_2, x_3)) reduce.0(f.0-1-0(x_1, x_2, x_3)) -> check_f.0(redex_f.0-1-0(x_1, x_2, x_3)) reduce.0(f.0-1-1(x_1, x_2, x_3)) -> check_f.0(redex_f.0-1-1(x_1, x_2, x_3)) reduce.0(f.1-0-0(x_1, x_2, x_3)) -> check_f.0(redex_f.1-0-0(x_1, x_2, x_3)) reduce.0(f.1-0-1(x_1, x_2, x_3)) -> check_f.0(redex_f.1-0-1(x_1, x_2, x_3)) reduce.0(f.1-1-0(x_1, x_2, x_3)) -> check_f.0(redex_f.1-1-0(x_1, x_2, x_3)) reduce.0(f.1-1-1(x_1, x_2, x_3)) -> check_f.0(redex_f.1-1-1(x_1, x_2, x_3)) reduce.0(0.) -> go_up.0(2.) in_g_1.0-0-0(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_1.0-0-0(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) reduce.0(g.0-0-1(x_1, x_2, x_3)) -> check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) in_g_1.0-0-1(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_1.0-0-1(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) reduce.0(g.0-1-0(x_1, x_2, x_3)) -> check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) in_g_1.0-1-0(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_1.0-1-0(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) reduce.0(g.0-1-1(x_1, x_2, x_3)) -> check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) in_g_1.0-1-1(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_1.0-1-1(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) reduce.0(g.1-0-0(x_1, x_2, x_3)) -> check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) in_g_2.0-0-0(x_1, go_up.0(x_2), x_3) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_2.0-0-0(x_1, go_up.1(x_2), x_3) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) reduce.0(g.1-0-1(x_1, x_2, x_3)) -> check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) in_g_2.1-0-1(x_1, go_up.0(x_2), x_3) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_2.1-0-1(x_1, go_up.1(x_2), x_3) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) reduce.0(g.1-1-0(x_1, x_2, x_3)) -> check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) in_g_2.0-0-1(x_1, go_up.0(x_2), x_3) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_2.0-0-1(x_1, go_up.1(x_2), x_3) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) reduce.0(g.1-1-1(x_1, x_2, x_3)) -> check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) in_g_2.1-0-0(x_1, go_up.0(x_2), x_3) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_2.1-0-0(x_1, go_up.1(x_2), x_3) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_3.0-0-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_3.0-0-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_3.0-1-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_3.0-1-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_3.1-0-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_3.1-0-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_3.1-1-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_3.1-1-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) redex_f.0-0-0(x, y, z) -> result_f.0(2.) check_f.0(result_f.0(x)) -> go_up.0(x) check_f.0(result_f.1(x)) -> go_up.1(x) redex_f.0-0-1(x, y, z) -> result_f.0(2.) redex_f.0-1-0(0., 1., x) -> result_f.0(f.0-0-0(x, x, x)) redex_f.0-1-0(x, y, z) -> result_f.0(2.) redex_f.0-1-1(0., 1., x) -> result_f.0(f.1-1-1(x, x, x)) redex_f.0-1-1(x, y, z) -> result_f.0(2.) redex_f.1-0-0(x, y, z) -> result_f.0(2.) redex_f.1-0-1(x, y, z) -> result_f.0(2.) redex_f.1-1-0(x, y, z) -> result_f.0(2.) redex_f.1-1-1(x, y, z) -> result_f.0(2.) reduce.1(1.) -> go_up.0(2.) ---------------------------------------- (36) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: reduce.0(f.0-0-0(x_1, x_2, x_3)) -> check_f.0(redex_f.0-0-0(x_1, x_2, x_3)) reduce.0(f.0-0-1(x_1, x_2, x_3)) -> check_f.0(redex_f.0-0-1(x_1, x_2, x_3)) reduce.0(f.0-1-0(x_1, x_2, x_3)) -> check_f.0(redex_f.0-1-0(x_1, x_2, x_3)) reduce.0(f.0-1-1(x_1, x_2, x_3)) -> check_f.0(redex_f.0-1-1(x_1, x_2, x_3)) reduce.0(f.1-0-0(x_1, x_2, x_3)) -> check_f.0(redex_f.1-0-0(x_1, x_2, x_3)) reduce.0(f.1-0-1(x_1, x_2, x_3)) -> check_f.0(redex_f.1-0-1(x_1, x_2, x_3)) reduce.0(f.1-1-0(x_1, x_2, x_3)) -> check_f.0(redex_f.1-1-0(x_1, x_2, x_3)) reduce.0(f.1-1-1(x_1, x_2, x_3)) -> check_f.0(redex_f.1-1-1(x_1, x_2, x_3)) reduce.0(g.0-0-0(x_1, x_2, x_3)) -> check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) reduce.0(g.0-0-1(x_1, x_2, x_3)) -> check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) reduce.0(g.0-1-0(x_1, x_2, x_3)) -> check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) reduce.0(g.0-1-1(x_1, x_2, x_3)) -> check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) reduce.0(g.1-0-0(x_1, x_2, x_3)) -> check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) reduce.0(g.1-0-1(x_1, x_2, x_3)) -> check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) reduce.0(g.1-1-0(x_1, x_2, x_3)) -> check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) reduce.0(g.1-1-1(x_1, x_2, x_3)) -> check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) reduce.0(0.) -> go_up.0(2.) reduce.1(1.) -> go_up.0(2.) redex_g.0-0-0(x, x, y) -> result_g.0(y) redex_g.0-0-1(x, x, y) -> result_g.1(y) redex_g.1-1-0(x, x, y) -> result_g.0(y) redex_g.1-1-1(x, x, y) -> result_g.1(y) redex_g.0-0-0(x, y, y) -> result_g.0(x) redex_g.0-1-1(x, y, y) -> result_g.0(x) redex_g.1-0-0(x, y, y) -> result_g.1(x) redex_g.1-1-1(x, y, y) -> result_g.1(x) check_g.0(result_g.0(x)) -> go_up.0(x) check_g.0(result_g.1(x)) -> go_up.1(x) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_1.0-0-0(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_1.0-0-1(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_1.0-1-0(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_1.0-1-1(reduce.0(x_1), x_2, x_3) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_1.0-0-0(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_1.0-0-1(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_1.0-1-0(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_1.0-1-1(reduce.1(x_1), x_2, x_3) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_2.0-0-0(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_2.0-0-1(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_2.0-0-0(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_2.0-0-1(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_2.1-0-0(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_2.1-0-1(x_1, reduce.0(x_2), x_3) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_2.1-0-0(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_2.1-0-1(x_1, reduce.1(x_2), x_3) check_g.0(redex_g.0-0-0(x_1, x_2, x_3)) -> in_g_3.0-0-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.0-0-1(x_1, x_2, x_3)) -> in_g_3.0-0-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.0-1-0(x_1, x_2, x_3)) -> in_g_3.0-1-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.0-1-1(x_1, x_2, x_3)) -> in_g_3.0-1-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.1-0-0(x_1, x_2, x_3)) -> in_g_3.1-0-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.1-0-1(x_1, x_2, x_3)) -> in_g_3.1-0-0(x_1, x_2, reduce.1(x_3)) check_g.0(redex_g.1-1-0(x_1, x_2, x_3)) -> in_g_3.1-1-0(x_1, x_2, reduce.0(x_3)) check_g.0(redex_g.1-1-1(x_1, x_2, x_3)) -> in_g_3.1-1-0(x_1, x_2, reduce.1(x_3)) in_g_3.0-0-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_3.0-0-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_3.0-1-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_3.0-1-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_3.1-0-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_3.1-0-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_3.1-1-0(x_1, x_2, go_up.0(x_3)) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_3.1-1-0(x_1, x_2, go_up.1(x_3)) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) in_g_2.0-0-0(x_1, go_up.0(x_2), x_3) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_2.0-0-1(x_1, go_up.0(x_2), x_3) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_2.0-0-0(x_1, go_up.1(x_2), x_3) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_2.0-0-1(x_1, go_up.1(x_2), x_3) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_2.1-0-0(x_1, go_up.0(x_2), x_3) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_2.1-0-1(x_1, go_up.0(x_2), x_3) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_2.1-0-0(x_1, go_up.1(x_2), x_3) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_2.1-0-1(x_1, go_up.1(x_2), x_3) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) in_g_1.0-0-0(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-0-0(x_1, x_2, x_3)) in_g_1.0-0-1(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-0-1(x_1, x_2, x_3)) in_g_1.0-1-0(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-1-0(x_1, x_2, x_3)) in_g_1.0-1-1(go_up.0(x_1), x_2, x_3) -> go_up.0(g.0-1-1(x_1, x_2, x_3)) in_g_1.0-0-0(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-0-0(x_1, x_2, x_3)) in_g_1.0-0-1(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-0-1(x_1, x_2, x_3)) in_g_1.0-1-0(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-1-0(x_1, x_2, x_3)) in_g_1.0-1-1(go_up.1(x_1), x_2, x_3) -> go_up.0(g.1-1-1(x_1, x_2, x_3)) redex_f.0-1-0(0., 1., x) -> result_f.0(f.0-0-0(x, x, x)) redex_f.0-1-1(0., 1., x) -> result_f.0(f.1-1-1(x, x, x)) redex_f.0-0-0(x, y, z) -> result_f.0(2.) redex_f.0-0-1(x, y, z) -> result_f.0(2.) redex_f.0-1-0(x, y, z) -> result_f.0(2.) redex_f.0-1-1(x, y, z) -> result_f.0(2.) redex_f.1-0-0(x, y, z) -> result_f.0(2.) redex_f.1-0-1(x, y, z) -> result_f.0(2.) redex_f.1-1-0(x, y, z) -> result_f.0(2.) redex_f.1-1-1(x, y, z) -> result_f.0(2.) check_f.0(result_f.0(x)) -> go_up.0(x) check_f.0(result_f.1(x)) -> go_up.1(x) The set Q consists of the following terms: reduce.0(f.0-0-0(x0, x1, x2)) reduce.0(f.0-0-1(x0, x1, x2)) reduce.0(f.0-1-0(x0, x1, x2)) reduce.0(f.0-1-1(x0, x1, x2)) reduce.0(f.1-0-0(x0, x1, x2)) reduce.0(f.1-0-1(x0, x1, x2)) reduce.0(f.1-1-0(x0, x1, x2)) reduce.0(f.1-1-1(x0, x1, x2)) reduce.0(g.0-0-0(x0, x1, x2)) reduce.0(g.0-0-1(x0, x1, x2)) reduce.0(g.0-1-0(x0, x1, x2)) reduce.0(g.0-1-1(x0, x1, x2)) reduce.0(g.1-0-0(x0, x1, x2)) reduce.0(g.1-0-1(x0, x1, x2)) reduce.0(g.1-1-0(x0, x1, x2)) reduce.0(g.1-1-1(x0, x1, x2)) redex_f.0-0-0(x0, x1, x2) redex_f.0-0-1(x0, x1, x2) redex_f.0-1-0(x0, x1, x2) redex_f.0-1-1(x0, x1, x2) redex_f.1-0-0(x0, x1, x2) redex_f.1-0-1(x0, x1, x2) redex_f.1-1-0(x0, x1, x2) redex_f.1-1-1(x0, x1, x2) reduce.0(0.) reduce.1(1.) redex_g.0-0-0(x0, x0, x1) redex_g.0-0-1(x0, x0, x1) redex_g.1-1-0(x0, x0, x1) redex_g.1-1-1(x0, x0, x1) redex_g.0-0-0(x0, x1, x1) redex_g.0-1-1(x0, x1, x1) redex_g.1-0-0(x0, x1, x1) redex_g.1-1-1(x0, x1, x1) check_f.0(result_f.0(x0)) check_f.0(result_f.1(x0)) check_g.0(result_g.0(x0)) check_g.0(result_g.1(x0)) check_g.0(redex_g.0-0-0(x0, x1, x2)) check_g.0(redex_g.0-0-1(x0, x1, x2)) check_g.0(redex_g.0-1-0(x0, x1, x2)) check_g.0(redex_g.0-1-1(x0, x1, x2)) check_g.0(redex_g.1-0-0(x0, x1, x2)) check_g.0(redex_g.1-0-1(x0, x1, x2)) check_g.0(redex_g.1-1-0(x0, x1, x2)) check_g.0(redex_g.1-1-1(x0, x1, x2)) in_g_1.0-0-0(go_up.0(x0), x1, x2) in_g_1.0-0-1(go_up.0(x0), x1, x2) in_g_1.0-1-0(go_up.0(x0), x1, x2) in_g_1.0-1-1(go_up.0(x0), x1, x2) in_g_1.0-0-0(go_up.1(x0), x1, x2) in_g_1.0-0-1(go_up.1(x0), x1, x2) in_g_1.0-1-0(go_up.1(x0), x1, x2) in_g_1.0-1-1(go_up.1(x0), x1, x2) in_g_2.0-0-0(x0, go_up.0(x1), x2) in_g_2.0-0-1(x0, go_up.0(x1), x2) in_g_2.0-0-0(x0, go_up.1(x1), x2) in_g_2.0-0-1(x0, go_up.1(x1), x2) in_g_2.1-0-0(x0, go_up.0(x1), x2) in_g_2.1-0-1(x0, go_up.0(x1), x2) in_g_2.1-0-0(x0, go_up.1(x1), x2) in_g_2.1-0-1(x0, go_up.1(x1), x2) in_g_3.0-0-0(x0, x1, go_up.0(x2)) in_g_3.0-0-0(x0, x1, go_up.1(x2)) in_g_3.0-1-0(x0, x1, go_up.0(x2)) in_g_3.0-1-0(x0, x1, go_up.1(x2)) in_g_3.1-0-0(x0, x1, go_up.0(x2)) in_g_3.1-0-0(x0, x1, go_up.1(x2)) in_g_3.1-1-0(x0, x1, go_up.0(x2)) in_g_3.1-1-0(x0, x1, go_up.1(x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (38) YES