5.87/2.13 YES 5.87/2.14 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 5.87/2.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.87/2.14 5.87/2.14 5.87/2.14 Outermost Termination of the given OTRS could be proven: 5.87/2.14 5.87/2.14 (0) OTRS 5.87/2.14 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 5.87/2.14 (2) QTRS 5.87/2.14 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.87/2.14 (4) QDP 5.87/2.14 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.87/2.14 (6) QDP 5.87/2.14 (7) UsableRulesProof [EQUIVALENT, 0 ms] 5.87/2.14 (8) QDP 5.87/2.14 (9) QReductionProof [EQUIVALENT, 0 ms] 5.87/2.14 (10) QDP 5.87/2.14 (11) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (12) QDP 5.87/2.14 (13) UsableRulesProof [EQUIVALENT, 0 ms] 5.87/2.14 (14) QDP 5.87/2.14 (15) TransformationProof [SOUND, 0 ms] 5.87/2.14 (16) QDP 5.87/2.14 (17) MRRProof [EQUIVALENT, 20 ms] 5.87/2.14 (18) QDP 5.87/2.14 (19) QReductionProof [EQUIVALENT, 0 ms] 5.87/2.14 (20) QDP 5.87/2.14 (21) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (22) QDP 5.87/2.14 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 5.87/2.14 (24) QDP 5.87/2.14 (25) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (26) QDP 5.87/2.14 (27) DependencyGraphProof [EQUIVALENT, 0 ms] 5.87/2.14 (28) QDP 5.87/2.14 (29) UsableRulesProof [EQUIVALENT, 0 ms] 5.87/2.14 (30) QDP 5.87/2.14 (31) QReductionProof [EQUIVALENT, 0 ms] 5.87/2.14 (32) QDP 5.87/2.14 (33) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (34) QDP 5.87/2.14 (35) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (36) QDP 5.87/2.14 (37) UsableRulesProof [EQUIVALENT, 0 ms] 5.87/2.14 (38) QDP 5.87/2.14 (39) QReductionProof [EQUIVALENT, 0 ms] 5.87/2.14 (40) QDP 5.87/2.14 (41) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (42) QDP 5.87/2.14 (43) UsableRulesProof [EQUIVALENT, 0 ms] 5.87/2.14 (44) QDP 5.87/2.14 (45) QReductionProof [EQUIVALENT, 0 ms] 5.87/2.14 (46) QDP 5.87/2.14 (47) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (48) QDP 5.87/2.14 (49) UsableRulesProof [EQUIVALENT, 0 ms] 5.87/2.14 (50) QDP 5.87/2.14 (51) QReductionProof [EQUIVALENT, 0 ms] 5.87/2.14 (52) QDP 5.87/2.14 (53) TransformationProof [EQUIVALENT, 0 ms] 5.87/2.14 (54) QDP 5.87/2.14 (55) DependencyGraphProof [EQUIVALENT, 0 ms] 5.87/2.14 (56) TRUE 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (0) 5.87/2.14 Obligation: 5.87/2.14 Term rewrite system R: 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 0 -> b(0, 0) 5.87/2.14 b(b(x, y), z) -> c 5.87/2.14 b(x, b(y, z)) -> c 5.87/2.14 5.87/2.14 5.87/2.14 5.87/2.14 Outermost Strategy. 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 5.87/2.14 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (2) 5.87/2.14 Obligation: 5.87/2.14 Q restricted rewrite system: 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 top(go_up(x)) -> top(reduce(x)) 5.87/2.14 reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 top(go_up(x0)) 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (3) DependencyPairsProof (EQUIVALENT) 5.87/2.14 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (4) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(x)) -> TOP(reduce(x)) 5.87/2.14 TOP(go_up(x)) -> REDUCE(x) 5.87/2.14 REDUCE(b(x_1, x_2)) -> CHECK_B(redex_b(x_1, x_2)) 5.87/2.14 REDUCE(b(x_1, x_2)) -> REDEX_B(x_1, x_2) 5.87/2.14 CHECK_B(redex_b(x_1, x_2)) -> IN_B_1(reduce(x_1), x_2) 5.87/2.14 CHECK_B(redex_b(x_1, x_2)) -> REDUCE(x_1) 5.87/2.14 CHECK_B(redex_b(x_1, x_2)) -> IN_B_2(x_1, reduce(x_2)) 5.87/2.14 CHECK_B(redex_b(x_1, x_2)) -> REDUCE(x_2) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 top(go_up(x)) -> top(reduce(x)) 5.87/2.14 reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 top(go_up(x0)) 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (5) DependencyGraphProof (EQUIVALENT) 5.87/2.14 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (6) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(x)) -> TOP(reduce(x)) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 top(go_up(x)) -> top(reduce(x)) 5.87/2.14 reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 top(go_up(x0)) 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (7) UsableRulesProof (EQUIVALENT) 5.87/2.14 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. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (8) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(x)) -> TOP(reduce(x)) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 top(go_up(x0)) 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (9) QReductionProof (EQUIVALENT) 5.87/2.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.87/2.14 5.87/2.14 top(go_up(x0)) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (10) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(x)) -> TOP(reduce(x)) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (11) TransformationProof (EQUIVALENT) 5.87/2.14 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))),TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1)))) 5.87/2.14 (TOP(go_up(0)) -> TOP(go_up(b(0, 0))),TOP(go_up(0)) -> TOP(go_up(b(0, 0)))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (12) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))) 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(b(x_1, x_2)) -> check_b(redex_b(x_1, x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (13) UsableRulesProof (EQUIVALENT) 5.87/2.14 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. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (14) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))) 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (15) TransformationProof (SOUND) 5.87/2.14 By narrowing [LPAR04] the rule TOP(go_up(b(x0, x1))) -> TOP(check_b(redex_b(x0, x1))) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)),TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1))) 5.87/2.14 (TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))),TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1)))) 5.87/2.14 (TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))),TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c)))) 5.87/2.14 (TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))),TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c)))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (16) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) 5.87/2.14 TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (17) MRRProof (EQUIVALENT) 5.87/2.14 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.87/2.14 5.87/2.14 5.87/2.14 Strictly oriented rules of the TRS R: 5.87/2.14 5.87/2.14 redex_b(b(x, y), z) -> result_b(c) 5.87/2.14 redex_b(x, b(y, z)) -> result_b(c) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_1(reduce(x_1), x_2) 5.87/2.14 check_b(redex_b(x_1, x_2)) -> in_b_2(x_1, reduce(x_2)) 5.87/2.14 5.87/2.14 Used ordering: Polynomial interpretation [POLO]: 5.87/2.14 5.87/2.14 POL(0) = 0 5.87/2.14 POL(TOP(x_1)) = 2*x_1 5.87/2.14 POL(b(x_1, x_2)) = 2*x_1 + 2*x_2 5.87/2.14 POL(c) = 0 5.87/2.14 POL(check_b(x_1)) = 2*x_1 5.87/2.14 POL(go_up(x_1)) = x_1 5.87/2.14 POL(in_b_1(x_1, x_2)) = 2*x_1 + 2*x_2 5.87/2.14 POL(in_b_2(x_1, x_2)) = 2*x_1 + 2*x_2 5.87/2.14 POL(redex_b(x_1, x_2)) = 2 + x_1 + x_2 5.87/2.14 POL(reduce(x_1)) = x_1 5.87/2.14 POL(result_b(x_1)) = x_1 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (18) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) 5.87/2.14 TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (19) QReductionProof (EQUIVALENT) 5.87/2.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.87/2.14 5.87/2.14 redex_b(b(x0, x1), x2) 5.87/2.14 redex_b(x0, b(x1, x2)) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (20) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) 5.87/2.14 TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (21) TransformationProof (EQUIVALENT) 5.87/2.14 By rewriting [LPAR04] the rule TOP(go_up(b(b(x0, x1), x2))) -> TOP(check_b(result_b(c))) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(b(x0, x1), x2))) -> TOP(go_up(c)),TOP(go_up(b(b(x0, x1), x2))) -> TOP(go_up(c))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (22) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) 5.87/2.14 TOP(go_up(b(b(x0, x1), x2))) -> TOP(go_up(c)) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (23) DependencyGraphProof (EQUIVALENT) 5.87/2.14 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (24) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (25) TransformationProof (EQUIVALENT) 5.87/2.14 By rewriting [LPAR04] the rule TOP(go_up(b(x0, b(x1, x2)))) -> TOP(check_b(result_b(c))) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(x0, b(x1, x2)))) -> TOP(go_up(c)),TOP(go_up(b(x0, b(x1, x2)))) -> TOP(go_up(c))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (26) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(0)) -> TOP(go_up(b(0, 0))) 5.87/2.14 TOP(go_up(b(x0, b(x1, x2)))) -> TOP(go_up(c)) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (27) DependencyGraphProof (EQUIVALENT) 5.87/2.14 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (28) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 check_b(result_b(x)) -> go_up(x) 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (29) UsableRulesProof (EQUIVALENT) 5.87/2.14 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. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (30) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (31) QReductionProof (EQUIVALENT) 5.87/2.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.87/2.14 5.87/2.14 check_b(result_b(x0)) 5.87/2.14 check_b(redex_b(x0, x1)) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (32) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (33) TransformationProof (EQUIVALENT) 5.87/2.14 By narrowing [LPAR04] the rule TOP(go_up(b(x0, x1))) -> TOP(in_b_1(reduce(x0), x1)) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1)),TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (34) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1)) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (35) TransformationProof (EQUIVALENT) 5.87/2.14 By rewriting [LPAR04] the rule TOP(go_up(b(0, y1))) -> TOP(in_b_1(go_up(b(0, 0)), y1)) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))),TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1)))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (36) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 in_b_1(go_up(x_1), x_2) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (37) UsableRulesProof (EQUIVALENT) 5.87/2.14 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. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (38) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (39) QReductionProof (EQUIVALENT) 5.87/2.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.87/2.14 5.87/2.14 in_b_1(go_up(x0), x1) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (40) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (41) TransformationProof (EQUIVALENT) 5.87/2.14 By narrowing [LPAR04] the rule TOP(go_up(b(x0, x1))) -> TOP(in_b_2(x0, reduce(x1))) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))),TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0))))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (42) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 reduce(0) -> go_up(b(0, 0)) 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (43) UsableRulesProof (EQUIVALENT) 5.87/2.14 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. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (44) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (45) QReductionProof (EQUIVALENT) 5.87/2.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.87/2.14 5.87/2.14 reduce(b(x0, x1)) 5.87/2.14 reduce(0) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (46) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (47) TransformationProof (EQUIVALENT) 5.87/2.14 By rewriting [LPAR04] the rule TOP(go_up(b(y0, 0))) -> TOP(in_b_2(y0, go_up(b(0, 0)))) at position [0] we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))),TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0))))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (48) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) 5.87/2.14 5.87/2.14 The TRS R consists of the following rules: 5.87/2.14 5.87/2.14 in_b_2(x_1, go_up(x_2)) -> go_up(b(x_1, x_2)) 5.87/2.14 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (49) UsableRulesProof (EQUIVALENT) 5.87/2.14 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. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (50) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) 5.87/2.14 5.87/2.14 R is empty. 5.87/2.14 The set Q consists of the following terms: 5.87/2.14 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (51) QReductionProof (EQUIVALENT) 5.87/2.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.87/2.14 5.87/2.14 in_b_2(x0, go_up(x1)) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (52) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) 5.87/2.14 5.87/2.14 R is empty. 5.87/2.14 Q is empty. 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (53) TransformationProof (EQUIVALENT) 5.87/2.14 By instantiating [LPAR04] the rule TOP(go_up(b(0, y1))) -> TOP(go_up(b(b(0, 0), y1))) we obtained the following new rules [LPAR04]: 5.87/2.14 5.87/2.14 (TOP(go_up(b(0, b(0, 0)))) -> TOP(go_up(b(b(0, 0), b(0, 0)))),TOP(go_up(b(0, b(0, 0)))) -> TOP(go_up(b(b(0, 0), b(0, 0))))) 5.87/2.14 5.87/2.14 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (54) 5.87/2.14 Obligation: 5.87/2.14 Q DP problem: 5.87/2.14 The TRS P consists of the following rules: 5.87/2.14 5.87/2.14 TOP(go_up(b(y0, 0))) -> TOP(go_up(b(y0, b(0, 0)))) 5.87/2.14 TOP(go_up(b(0, b(0, 0)))) -> TOP(go_up(b(b(0, 0), b(0, 0)))) 5.87/2.14 5.87/2.14 R is empty. 5.87/2.14 Q is empty. 5.87/2.14 We have to consider all minimal (P,Q,R)-chains. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (55) DependencyGraphProof (EQUIVALENT) 5.87/2.14 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 5.87/2.14 ---------------------------------------- 5.87/2.14 5.87/2.14 (56) 5.87/2.14 TRUE 6.16/2.18 EOF