49.40/20.44 YES 49.40/20.45 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 49.40/20.45 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 49.40/20.45 49.40/20.45 49.40/20.45 Outermost Termination of the given OTRS could be proven: 49.40/20.45 49.40/20.45 (0) OTRS 49.40/20.45 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 49.40/20.45 (2) QTRS 49.40/20.45 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 49.40/20.45 (4) QDP 49.40/20.45 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 49.40/20.45 (6) AND 49.40/20.45 (7) QDP 49.40/20.45 (8) UsableRulesProof [EQUIVALENT, 0 ms] 49.40/20.45 (9) QDP 49.40/20.45 (10) QReductionProof [EQUIVALENT, 0 ms] 49.40/20.45 (11) QDP 49.40/20.45 (12) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] 49.40/20.45 (13) QDP 49.40/20.45 (14) DependencyGraphProof [EQUIVALENT, 0 ms] 49.40/20.45 (15) TRUE 49.40/20.45 (16) QDP 49.40/20.45 (17) UsableRulesProof [EQUIVALENT, 0 ms] 49.40/20.45 (18) QDP 49.40/20.45 (19) QReductionProof [EQUIVALENT, 0 ms] 49.40/20.45 (20) QDP 49.40/20.45 (21) TransformationProof [EQUIVALENT, 0 ms] 49.40/20.45 (22) QDP 49.40/20.45 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 49.40/20.45 (24) QDP 49.40/20.45 (25) TransformationProof [EQUIVALENT, 0 ms] 49.40/20.45 (26) QDP 49.40/20.45 (27) TransformationProof [EQUIVALENT, 0 ms] 49.40/20.45 (28) QDP 49.40/20.45 (29) TransformationProof [EQUIVALENT, 0 ms] 49.40/20.45 (30) QDP 49.40/20.45 (31) DependencyGraphProof [EQUIVALENT, 0 ms] 49.40/20.45 (32) QDP 49.40/20.45 (33) SemLabProof [SOUND, 141 ms] 49.40/20.45 (34) QDP 49.40/20.45 (35) QDPOrderProof [EQUIVALENT, 32 ms] 49.40/20.45 (36) QDP 49.40/20.45 (37) PisEmptyProof [EQUIVALENT, 0 ms] 49.40/20.45 (38) YES 49.40/20.45 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (0) 49.40/20.45 Obligation: 49.40/20.45 Term rewrite system R: 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 f(0, 1, x) -> f(x, x, x) 49.40/20.45 f(x, y, z) -> 2 49.40/20.45 0 -> 2 49.40/20.45 1 -> 2 49.40/20.45 g(x, x, y) -> y 49.40/20.45 g(x, y, y) -> x 49.40/20.45 49.40/20.45 49.40/20.45 49.40/20.45 Outermost Strategy. 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 49.40/20.45 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (2) 49.40/20.45 Obligation: 49.40/20.45 Q restricted rewrite system: 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 top(go_up(x)) -> top(reduce(x)) 49.40/20.45 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.45 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.45 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.45 redex_f(x, y, z) -> result_f(2) 49.40/20.45 reduce(0) -> go_up(2) 49.40/20.45 reduce(1) -> go_up(2) 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 check_f(result_f(x)) -> go_up(x) 49.40/20.45 check_g(result_g(x)) -> go_up(x) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.45 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (3) DependencyPairsProof (EQUIVALENT) 49.40/20.45 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (4) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 TOP(go_up(x)) -> TOP(reduce(x)) 49.40/20.45 TOP(go_up(x)) -> REDUCE(x) 49.40/20.45 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 49.40/20.45 REDUCE(f(x_1, x_2, x_3)) -> REDEX_F(x_1, x_2, x_3) 49.40/20.45 REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) 49.40/20.45 REDUCE(g(x_1, x_2, x_3)) -> REDEX_G(x_1, x_2, x_3) 49.40/20.45 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_1(reduce(x_1), x_2, x_3) 49.40/20.45 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 49.40/20.45 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_2(x_1, reduce(x_2), x_3) 49.40/20.45 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 49.40/20.45 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_3(x_1, x_2, reduce(x_3)) 49.40/20.45 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> IN_G_1(reduce(x_1), x_2, x_3) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> IN_G_2(x_1, reduce(x_2), x_3) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> IN_G_3(x_1, x_2, reduce(x_3)) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 top(go_up(x)) -> top(reduce(x)) 49.40/20.45 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.45 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.45 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.45 redex_f(x, y, z) -> result_f(2) 49.40/20.45 reduce(0) -> go_up(2) 49.40/20.45 reduce(1) -> go_up(2) 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 check_f(result_f(x)) -> go_up(x) 49.40/20.45 check_g(result_g(x)) -> go_up(x) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.45 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (5) DependencyGraphProof (EQUIVALENT) 49.40/20.45 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 13 less nodes. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (6) 49.40/20.45 Complex Obligation (AND) 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (7) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 top(go_up(x)) -> top(reduce(x)) 49.40/20.45 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.45 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.45 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.45 redex_f(x, y, z) -> result_f(2) 49.40/20.45 reduce(0) -> go_up(2) 49.40/20.45 reduce(1) -> go_up(2) 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 check_f(result_f(x)) -> go_up(x) 49.40/20.45 check_g(result_g(x)) -> go_up(x) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.45 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (8) UsableRulesProof (EQUIVALENT) 49.40/20.45 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. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (9) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (10) QReductionProof (EQUIVALENT) 49.40/20.45 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (11) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (12) UsableRulesReductionPairsProof (EQUIVALENT) 49.40/20.45 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. 49.40/20.45 49.40/20.45 The following dependency pairs can be deleted: 49.40/20.45 49.40/20.45 REDUCE(g(x_1, x_2, x_3)) -> CHECK_G(redex_g(x_1, x_2, x_3)) 49.40/20.45 No rules are removed from R. 49.40/20.45 49.40/20.45 Used ordering: POLO with Polynomial interpretation [POLO]: 49.40/20.45 49.40/20.45 POL(CHECK_G(x_1)) = 2*x_1 49.40/20.45 POL(REDUCE(x_1)) = 2*x_1 49.40/20.45 POL(g(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 49.40/20.45 POL(redex_g(x_1, x_2, x_3)) = x_1 + x_2 + x_3 49.40/20.45 POL(result_g(x_1)) = x_1 49.40/20.45 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (13) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_1) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_2) 49.40/20.45 CHECK_G(redex_g(x_1, x_2, x_3)) -> REDUCE(x_3) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (14) DependencyGraphProof (EQUIVALENT) 49.40/20.45 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (15) 49.40/20.45 TRUE 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (16) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 TOP(go_up(x)) -> TOP(reduce(x)) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 top(go_up(x)) -> top(reduce(x)) 49.40/20.45 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.45 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.45 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.45 redex_f(x, y, z) -> result_f(2) 49.40/20.45 reduce(0) -> go_up(2) 49.40/20.45 reduce(1) -> go_up(2) 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 check_f(result_f(x)) -> go_up(x) 49.40/20.45 check_g(result_g(x)) -> go_up(x) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.45 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 49.40/20.45 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (17) UsableRulesProof (EQUIVALENT) 49.40/20.45 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. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (18) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 TOP(go_up(x)) -> TOP(reduce(x)) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.45 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.45 reduce(0) -> go_up(2) 49.40/20.45 reduce(1) -> go_up(2) 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.45 check_g(result_g(x)) -> go_up(x) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.45 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.45 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.45 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.45 redex_f(x, y, z) -> result_f(2) 49.40/20.45 check_f(result_f(x)) -> go_up(x) 49.40/20.45 49.40/20.45 The set Q consists of the following terms: 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 reduce(f(x0, x1, x2)) 49.40/20.45 reduce(g(x0, x1, x2)) 49.40/20.45 redex_f(x0, x1, x2) 49.40/20.45 reduce(0) 49.40/20.45 reduce(1) 49.40/20.45 redex_g(x0, x0, x1) 49.40/20.45 redex_g(x0, x1, x1) 49.40/20.45 check_f(result_f(x0)) 49.40/20.45 check_g(result_g(x0)) 49.40/20.45 check_g(redex_g(x0, x1, x2)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 in_g_1(go_up(x0), x1, x2) 49.40/20.45 in_g_2(x0, go_up(x1), x2) 49.40/20.45 in_g_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 We have to consider all minimal (P,Q,R)-chains. 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (19) QReductionProof (EQUIVALENT) 49.40/20.45 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 49.40/20.45 49.40/20.45 top(go_up(x0)) 49.40/20.45 in_f_1(go_up(x0), x1, x2) 49.40/20.45 in_f_2(x0, go_up(x1), x2) 49.40/20.45 in_f_3(x0, x1, go_up(x2)) 49.40/20.45 49.40/20.45 49.40/20.45 ---------------------------------------- 49.40/20.45 49.40/20.45 (20) 49.40/20.45 Obligation: 49.40/20.45 Q DP problem: 49.40/20.45 The TRS P consists of the following rules: 49.40/20.45 49.40/20.45 TOP(go_up(x)) -> TOP(reduce(x)) 49.40/20.45 49.40/20.45 The TRS R consists of the following rules: 49.40/20.45 49.40/20.45 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.45 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.45 reduce(0) -> go_up(2) 49.40/20.45 reduce(1) -> go_up(2) 49.40/20.45 redex_g(x, x, y) -> result_g(y) 49.40/20.45 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (21) TransformationProof (EQUIVALENT) 49.40/20.46 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 49.40/20.46 49.40/20.46 (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)))) 49.40/20.46 (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)))) 49.40/20.46 (TOP(go_up(0)) -> TOP(go_up(2)),TOP(go_up(0)) -> TOP(go_up(2))) 49.40/20.46 (TOP(go_up(1)) -> TOP(go_up(2)),TOP(go_up(1)) -> TOP(go_up(2))) 49.40/20.46 49.40/20.46 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (22) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) 49.40/20.46 TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) 49.40/20.46 TOP(go_up(0)) -> TOP(go_up(2)) 49.40/20.46 TOP(go_up(1)) -> TOP(go_up(2)) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.46 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.46 reduce(0) -> go_up(2) 49.40/20.46 reduce(1) -> go_up(2) 49.40/20.46 redex_g(x, x, y) -> result_g(y) 49.40/20.46 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (23) DependencyGraphProof (EQUIVALENT) 49.40/20.46 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (24) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) 49.40/20.46 TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.46 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.46 reduce(0) -> go_up(2) 49.40/20.46 reduce(1) -> go_up(2) 49.40/20.46 redex_g(x, x, y) -> result_g(y) 49.40/20.46 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (25) TransformationProof (EQUIVALENT) 49.40/20.46 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]: 49.40/20.46 49.40/20.46 (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))))) 49.40/20.46 (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)))) 49.40/20.46 49.40/20.46 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (26) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) 49.40/20.46 TOP(go_up(f(0, 1, x0))) -> TOP(check_f(result_f(f(x0, x0, x0)))) 49.40/20.46 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2))) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.46 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.46 reduce(0) -> go_up(2) 49.40/20.46 reduce(1) -> go_up(2) 49.40/20.46 redex_g(x, x, y) -> result_g(y) 49.40/20.46 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (27) TransformationProof (EQUIVALENT) 49.40/20.46 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]: 49.40/20.46 49.40/20.46 (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)))) 49.40/20.46 49.40/20.46 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (28) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) 49.40/20.46 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(result_f(2))) 49.40/20.46 TOP(go_up(f(0, 1, x0))) -> TOP(go_up(f(x0, x0, x0))) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.46 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.46 reduce(0) -> go_up(2) 49.40/20.46 reduce(1) -> go_up(2) 49.40/20.46 redex_g(x, x, y) -> result_g(y) 49.40/20.46 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (29) TransformationProof (EQUIVALENT) 49.40/20.46 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]: 49.40/20.46 49.40/20.46 (TOP(go_up(f(x0, x1, x2))) -> TOP(go_up(2)),TOP(go_up(f(x0, x1, x2))) -> TOP(go_up(2))) 49.40/20.46 49.40/20.46 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (30) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) 49.40/20.46 TOP(go_up(f(0, 1, x0))) -> TOP(go_up(f(x0, x0, x0))) 49.40/20.46 TOP(go_up(f(x0, x1, x2))) -> TOP(go_up(2)) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.46 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.46 reduce(0) -> go_up(2) 49.40/20.46 reduce(1) -> go_up(2) 49.40/20.46 redex_g(x, x, y) -> result_g(y) 49.40/20.46 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (31) DependencyGraphProof (EQUIVALENT) 49.40/20.46 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (32) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 TOP(go_up(g(x0, x1, x2))) -> TOP(check_g(redex_g(x0, x1, x2))) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 49.40/20.46 reduce(g(x_1, x_2, x_3)) -> check_g(redex_g(x_1, x_2, x_3)) 49.40/20.46 reduce(0) -> go_up(2) 49.40/20.46 reduce(1) -> go_up(2) 49.40/20.46 redex_g(x, x, y) -> result_g(y) 49.40/20.46 redex_g(x, y, y) -> result_g(x) 49.40/20.46 check_g(result_g(x)) -> go_up(x) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_1(reduce(x_1), x_2, x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_2(x_1, reduce(x_2), x_3) 49.40/20.46 check_g(redex_g(x_1, x_2, x_3)) -> in_g_3(x_1, x_2, reduce(x_3)) 49.40/20.46 in_g_3(x_1, x_2, go_up(x_3)) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_2(x_1, go_up(x_2), x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 in_g_1(go_up(x_1), x_2, x_3) -> go_up(g(x_1, x_2, x_3)) 49.40/20.46 redex_f(0, 1, x) -> result_f(f(x, x, x)) 49.40/20.46 redex_f(x, y, z) -> result_f(2) 49.40/20.46 check_f(result_f(x)) -> go_up(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce(f(x0, x1, x2)) 49.40/20.46 reduce(g(x0, x1, x2)) 49.40/20.46 redex_f(x0, x1, x2) 49.40/20.46 reduce(0) 49.40/20.46 reduce(1) 49.40/20.46 redex_g(x0, x0, x1) 49.40/20.46 redex_g(x0, x1, x1) 49.40/20.46 check_f(result_f(x0)) 49.40/20.46 check_g(result_g(x0)) 49.40/20.46 check_g(redex_g(x0, x1, x2)) 49.40/20.46 in_g_1(go_up(x0), x1, x2) 49.40/20.46 in_g_2(x0, go_up(x1), x2) 49.40/20.46 in_g_3(x0, x1, go_up(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (33) SemLabProof (SOUND) 49.40/20.46 We found the following model for the rules of the TRSs R and P. 49.40/20.46 Interpretation over the domain with elements from 0 to 1. 49.40/20.46 result_f: 0 49.40/20.46 reduce: 0 49.40/20.46 in_g_1: 0 49.40/20.46 in_g_3: 0 49.40/20.46 redex_f: 0 49.40/20.46 2: 0 49.40/20.46 check_f: 0 49.40/20.46 in_g_2: 0 49.40/20.46 TOP: 0 49.40/20.46 g: 0 49.40/20.46 go_up: 0 49.40/20.46 result_g: 0 49.40/20.46 f: 0 49.40/20.46 0: 0 49.40/20.46 1: 1 49.40/20.46 check_g: 0 49.40/20.46 redex_g: 0 49.40/20.46 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (34) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 The TRS P consists of the following rules: 49.40/20.46 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 reduce.0(0.) -> go_up.0(2.) 49.40/20.46 reduce.1(1.) -> go_up.0(2.) 49.40/20.46 redex_g.0-0-0(x, x, y) -> result_g.0(y) 49.40/20.46 redex_g.0-0-1(x, x, y) -> result_g.1(y) 49.40/20.46 redex_g.1-1-0(x, x, y) -> result_g.0(y) 49.40/20.46 redex_g.1-1-1(x, x, y) -> result_g.1(y) 49.40/20.46 redex_g.0-0-0(x, y, y) -> result_g.0(x) 49.40/20.46 redex_g.0-1-1(x, y, y) -> result_g.0(x) 49.40/20.46 redex_g.1-0-0(x, y, y) -> result_g.1(x) 49.40/20.46 redex_g.1-1-1(x, y, y) -> result_g.1(x) 49.40/20.46 check_g.0(result_g.0(x)) -> go_up.0(x) 49.40/20.46 check_g.0(result_g.1(x)) -> go_up.1(x) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 redex_f.0-1-0(0., 1., x) -> result_f.0(f.0-0-0(x, x, x)) 49.40/20.46 redex_f.0-1-1(0., 1., x) -> result_f.0(f.1-1-1(x, x, x)) 49.40/20.46 redex_f.0-0-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-0-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-1-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-1-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-0-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-0-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-1-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-1-1(x, y, z) -> result_f.0(2.) 49.40/20.46 check_f.0(result_f.0(x)) -> go_up.0(x) 49.40/20.46 check_f.0(result_f.1(x)) -> go_up.1(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce.0(f.0-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.0-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(f.0-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.0-1-1(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-1-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-1-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-1-1(x0, x1, x2)) 49.40/20.46 redex_f.0-0-0(x0, x1, x2) 49.40/20.46 redex_f.0-0-1(x0, x1, x2) 49.40/20.46 redex_f.0-1-0(x0, x1, x2) 49.40/20.46 redex_f.0-1-1(x0, x1, x2) 49.40/20.46 redex_f.1-0-0(x0, x1, x2) 49.40/20.46 redex_f.1-0-1(x0, x1, x2) 49.40/20.46 redex_f.1-1-0(x0, x1, x2) 49.40/20.46 redex_f.1-1-1(x0, x1, x2) 49.40/20.46 reduce.0(0.) 49.40/20.46 reduce.1(1.) 49.40/20.46 redex_g.0-0-0(x0, x0, x1) 49.40/20.46 redex_g.0-0-1(x0, x0, x1) 49.40/20.46 redex_g.1-1-0(x0, x0, x1) 49.40/20.46 redex_g.1-1-1(x0, x0, x1) 49.40/20.46 redex_g.0-0-0(x0, x1, x1) 49.40/20.46 redex_g.0-1-1(x0, x1, x1) 49.40/20.46 redex_g.1-0-0(x0, x1, x1) 49.40/20.46 redex_g.1-1-1(x0, x1, x1) 49.40/20.46 check_f.0(result_f.0(x0)) 49.40/20.46 check_f.0(result_f.1(x0)) 49.40/20.46 check_g.0(result_g.0(x0)) 49.40/20.46 check_g.0(result_g.1(x0)) 49.40/20.46 check_g.0(redex_g.0-0-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.0-0-1(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.0-1-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.0-1-1(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-0-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-0-1(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-1-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-1-1(x0, x1, x2)) 49.40/20.46 in_g_1.0-0-0(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-0-1(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-1-0(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-1-1(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-0-0(go_up.1(x0), x1, x2) 49.40/20.46 in_g_1.0-0-1(go_up.1(x0), x1, x2) 49.40/20.46 in_g_1.0-1-0(go_up.1(x0), x1, x2) 49.40/20.46 in_g_1.0-1-1(go_up.1(x0), x1, x2) 49.40/20.46 in_g_2.0-0-0(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.0-0-1(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.0-0-0(x0, go_up.1(x1), x2) 49.40/20.46 in_g_2.0-0-1(x0, go_up.1(x1), x2) 49.40/20.46 in_g_2.1-0-0(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.1-0-1(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.1-0-0(x0, go_up.1(x1), x2) 49.40/20.46 in_g_2.1-0-1(x0, go_up.1(x1), x2) 49.40/20.46 in_g_3.0-0-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.0-0-0(x0, x1, go_up.1(x2)) 49.40/20.46 in_g_3.0-1-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.0-1-0(x0, x1, go_up.1(x2)) 49.40/20.46 in_g_3.1-0-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.1-0-0(x0, x1, go_up.1(x2)) 49.40/20.46 in_g_3.1-1-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.1-1-0(x0, x1, go_up.1(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (35) QDPOrderProof (EQUIVALENT) 49.40/20.46 We use the reduction pair processor [LPAR04,JAR06]. 49.40/20.46 49.40/20.46 49.40/20.46 The following pairs can be oriented strictly and are deleted. 49.40/20.46 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 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))) 49.40/20.46 The remaining pairs can at least be oriented weakly. 49.40/20.46 Used ordering: Polynomial interpretation [POLO]: 49.40/20.46 49.40/20.46 POL(0.) = 1 49.40/20.46 POL(1.) = 1 49.40/20.46 POL(2.) = 0 49.40/20.46 POL(TOP.0(x_1)) = x_1 49.40/20.46 POL(check_f.0(x_1)) = 1 + x_1 49.40/20.46 POL(check_g.0(x_1)) = x_1 49.40/20.46 POL(f.0-0-0(x_1, x_2, x_3)) = 1 + x_2 49.40/20.46 POL(f.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(f.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(f.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(f.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(f.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(f.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(f.1-1-1(x_1, x_2, x_3)) = 1 + x_1 49.40/20.46 POL(g.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(g.1-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(go_up.0(x_1)) = 1 + x_1 49.40/20.46 POL(go_up.1(x_1)) = 1 + x_1 49.40/20.46 POL(in_g_1.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_1.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_1.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_1.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_2.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_2.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_2.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_2.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_3.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_3.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_3.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(in_g_3.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_f.0-0-0(x_1, x_2, x_3)) = 0 49.40/20.46 POL(redex_f.0-0-1(x_1, x_2, x_3)) = 0 49.40/20.46 POL(redex_f.0-1-0(x_1, x_2, x_3)) = x_1 + x_2 + x_3 49.40/20.46 POL(redex_f.0-1-1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 49.40/20.46 POL(redex_f.1-0-0(x_1, x_2, x_3)) = 0 49.40/20.46 POL(redex_f.1-0-1(x_1, x_2, x_3)) = 0 49.40/20.46 POL(redex_f.1-1-0(x_1, x_2, x_3)) = 0 49.40/20.46 POL(redex_f.1-1-1(x_1, x_2, x_3)) = 0 49.40/20.46 POL(redex_g.0-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.0-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.0-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.0-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.1-0-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.1-0-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.1-1-0(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(redex_g.1-1-1(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 49.40/20.46 POL(reduce.0(x_1)) = x_1 49.40/20.46 POL(reduce.1(x_1)) = x_1 49.40/20.46 POL(result_f.0(x_1)) = x_1 49.40/20.46 POL(result_f.1(x_1)) = 1 + x_1 49.40/20.46 POL(result_g.0(x_1)) = 1 + x_1 49.40/20.46 POL(result_g.1(x_1)) = 1 + x_1 49.40/20.46 49.40/20.46 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 49.40/20.46 49.40/20.46 redex_g.0-0-0(x, x, y) -> result_g.0(y) 49.40/20.46 redex_g.0-0-0(x, y, y) -> result_g.0(x) 49.40/20.46 check_g.0(result_g.0(x)) -> go_up.0(x) 49.40/20.46 check_g.0(result_g.1(x)) -> go_up.1(x) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 redex_g.0-0-1(x, x, y) -> result_g.1(y) 49.40/20.46 redex_g.0-1-1(x, y, y) -> result_g.0(x) 49.40/20.46 redex_g.1-0-0(x, y, y) -> result_g.1(x) 49.40/20.46 redex_g.1-1-0(x, x, y) -> result_g.0(y) 49.40/20.46 redex_g.1-1-1(x, x, y) -> result_g.1(y) 49.40/20.46 redex_g.1-1-1(x, y, y) -> result_g.1(x) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 reduce.0(0.) -> go_up.0(2.) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 redex_f.0-0-0(x, y, z) -> result_f.0(2.) 49.40/20.46 check_f.0(result_f.0(x)) -> go_up.0(x) 49.40/20.46 check_f.0(result_f.1(x)) -> go_up.1(x) 49.40/20.46 redex_f.0-0-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-1-0(0., 1., x) -> result_f.0(f.0-0-0(x, x, x)) 49.40/20.46 redex_f.0-1-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-1-1(0., 1., x) -> result_f.0(f.1-1-1(x, x, x)) 49.40/20.46 redex_f.0-1-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-0-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-0-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-1-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-1-1(x, y, z) -> result_f.0(2.) 49.40/20.46 reduce.1(1.) -> go_up.0(2.) 49.40/20.46 49.40/20.46 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (36) 49.40/20.46 Obligation: 49.40/20.46 Q DP problem: 49.40/20.46 P is empty. 49.40/20.46 The TRS R consists of the following rules: 49.40/20.46 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 reduce.0(0.) -> go_up.0(2.) 49.40/20.46 reduce.1(1.) -> go_up.0(2.) 49.40/20.46 redex_g.0-0-0(x, x, y) -> result_g.0(y) 49.40/20.46 redex_g.0-0-1(x, x, y) -> result_g.1(y) 49.40/20.46 redex_g.1-1-0(x, x, y) -> result_g.0(y) 49.40/20.46 redex_g.1-1-1(x, x, y) -> result_g.1(y) 49.40/20.46 redex_g.0-0-0(x, y, y) -> result_g.0(x) 49.40/20.46 redex_g.0-1-1(x, y, y) -> result_g.0(x) 49.40/20.46 redex_g.1-0-0(x, y, y) -> result_g.1(x) 49.40/20.46 redex_g.1-1-1(x, y, y) -> result_g.1(x) 49.40/20.46 check_g.0(result_g.0(x)) -> go_up.0(x) 49.40/20.46 check_g.0(result_g.1(x)) -> go_up.1(x) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 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)) 49.40/20.46 redex_f.0-1-0(0., 1., x) -> result_f.0(f.0-0-0(x, x, x)) 49.40/20.46 redex_f.0-1-1(0., 1., x) -> result_f.0(f.1-1-1(x, x, x)) 49.40/20.46 redex_f.0-0-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-0-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-1-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.0-1-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-0-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-0-1(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-1-0(x, y, z) -> result_f.0(2.) 49.40/20.46 redex_f.1-1-1(x, y, z) -> result_f.0(2.) 49.40/20.46 check_f.0(result_f.0(x)) -> go_up.0(x) 49.40/20.46 check_f.0(result_f.1(x)) -> go_up.1(x) 49.40/20.46 49.40/20.46 The set Q consists of the following terms: 49.40/20.46 49.40/20.46 reduce.0(f.0-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.0-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(f.0-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.0-1-1(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(f.1-1-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.0-1-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-0-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-0-1(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-1-0(x0, x1, x2)) 49.40/20.46 reduce.0(g.1-1-1(x0, x1, x2)) 49.40/20.46 redex_f.0-0-0(x0, x1, x2) 49.40/20.46 redex_f.0-0-1(x0, x1, x2) 49.40/20.46 redex_f.0-1-0(x0, x1, x2) 49.40/20.46 redex_f.0-1-1(x0, x1, x2) 49.40/20.46 redex_f.1-0-0(x0, x1, x2) 49.40/20.46 redex_f.1-0-1(x0, x1, x2) 49.40/20.46 redex_f.1-1-0(x0, x1, x2) 49.40/20.46 redex_f.1-1-1(x0, x1, x2) 49.40/20.46 reduce.0(0.) 49.40/20.46 reduce.1(1.) 49.40/20.46 redex_g.0-0-0(x0, x0, x1) 49.40/20.46 redex_g.0-0-1(x0, x0, x1) 49.40/20.46 redex_g.1-1-0(x0, x0, x1) 49.40/20.46 redex_g.1-1-1(x0, x0, x1) 49.40/20.46 redex_g.0-0-0(x0, x1, x1) 49.40/20.46 redex_g.0-1-1(x0, x1, x1) 49.40/20.46 redex_g.1-0-0(x0, x1, x1) 49.40/20.46 redex_g.1-1-1(x0, x1, x1) 49.40/20.46 check_f.0(result_f.0(x0)) 49.40/20.46 check_f.0(result_f.1(x0)) 49.40/20.46 check_g.0(result_g.0(x0)) 49.40/20.46 check_g.0(result_g.1(x0)) 49.40/20.46 check_g.0(redex_g.0-0-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.0-0-1(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.0-1-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.0-1-1(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-0-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-0-1(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-1-0(x0, x1, x2)) 49.40/20.46 check_g.0(redex_g.1-1-1(x0, x1, x2)) 49.40/20.46 in_g_1.0-0-0(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-0-1(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-1-0(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-1-1(go_up.0(x0), x1, x2) 49.40/20.46 in_g_1.0-0-0(go_up.1(x0), x1, x2) 49.40/20.46 in_g_1.0-0-1(go_up.1(x0), x1, x2) 49.40/20.46 in_g_1.0-1-0(go_up.1(x0), x1, x2) 49.40/20.46 in_g_1.0-1-1(go_up.1(x0), x1, x2) 49.40/20.46 in_g_2.0-0-0(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.0-0-1(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.0-0-0(x0, go_up.1(x1), x2) 49.40/20.46 in_g_2.0-0-1(x0, go_up.1(x1), x2) 49.40/20.46 in_g_2.1-0-0(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.1-0-1(x0, go_up.0(x1), x2) 49.40/20.46 in_g_2.1-0-0(x0, go_up.1(x1), x2) 49.40/20.46 in_g_2.1-0-1(x0, go_up.1(x1), x2) 49.40/20.46 in_g_3.0-0-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.0-0-0(x0, x1, go_up.1(x2)) 49.40/20.46 in_g_3.0-1-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.0-1-0(x0, x1, go_up.1(x2)) 49.40/20.46 in_g_3.1-0-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.1-0-0(x0, x1, go_up.1(x2)) 49.40/20.46 in_g_3.1-1-0(x0, x1, go_up.0(x2)) 49.40/20.46 in_g_3.1-1-0(x0, x1, go_up.1(x2)) 49.40/20.46 49.40/20.46 We have to consider all minimal (P,Q,R)-chains. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (37) PisEmptyProof (EQUIVALENT) 49.40/20.46 The TRS P is empty. Hence, there is no (P,Q,R) chain. 49.40/20.46 ---------------------------------------- 49.40/20.46 49.40/20.46 (38) 49.40/20.46 YES 49.53/20.54 EOF