92.35/64.99 MAYBE 92.35/65.00 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 92.35/65.00 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 92.35/65.00 92.35/65.00 92.35/65.00 Outermost Termination of the given OTRS could not be shown: 92.35/65.00 92.35/65.00 (0) OTRS 92.35/65.00 (1) Trivial-Transformation [SOUND, 0 ms] 92.35/65.00 (2) QTRS 92.35/65.00 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 92.35/65.00 (4) QDP 92.35/65.00 (5) TransformationProof [EQUIVALENT, 0 ms] 92.35/65.00 (6) QDP 92.35/65.00 (7) NonTerminationLoopProof [COMPLETE, 0 ms] 92.35/65.00 (8) NO 92.35/65.00 (9) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 92.35/65.00 (10) QTRS 92.35/65.00 (11) DependencyPairsProof [EQUIVALENT, 10 ms] 92.35/65.00 (12) QDP 92.35/65.00 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 92.35/65.00 (14) AND 92.35/65.00 (15) QDP 92.35/65.00 (16) UsableRulesProof [EQUIVALENT, 0 ms] 92.35/65.00 (17) QDP 92.35/65.00 (18) QReductionProof [EQUIVALENT, 0 ms] 92.35/65.00 (19) QDP 92.35/65.00 (20) QDPOrderProof [EQUIVALENT, 0 ms] 92.35/65.00 (21) QDP 92.35/65.00 (22) DependencyGraphProof [EQUIVALENT, 0 ms] 92.35/65.00 (23) QDP 92.35/65.00 (24) UsableRulesProof [EQUIVALENT, 0 ms] 92.35/65.00 (25) QDP 92.35/65.00 (26) QReductionProof [EQUIVALENT, 0 ms] 92.35/65.00 (27) QDP 92.35/65.00 (28) QDPOrderProof [EQUIVALENT, 5 ms] 92.35/65.00 (29) QDP 92.35/65.00 (30) DependencyGraphProof [EQUIVALENT, 0 ms] 92.35/65.00 (31) TRUE 92.35/65.00 (32) QDP 92.35/65.00 (33) UsableRulesProof [EQUIVALENT, 0 ms] 92.35/65.00 (34) QDP 92.35/65.00 (35) QReductionProof [EQUIVALENT, 0 ms] 92.35/65.00 (36) QDP 92.35/65.00 (37) TransformationProof [EQUIVALENT, 0 ms] 92.35/65.00 (38) QDP 92.35/65.00 (39) DependencyGraphProof [EQUIVALENT, 0 ms] 92.35/65.00 (40) QDP 92.35/65.00 (41) UsableRulesProof [EQUIVALENT, 0 ms] 92.35/65.00 (42) QDP 92.35/65.00 (43) QReductionProof [EQUIVALENT, 0 ms] 92.35/65.00 (44) QDP 92.35/65.00 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (0) 92.35/65.00 Obligation: 92.35/65.00 Term rewrite system R: 92.35/65.00 The TRS R consists of the following rules: 92.35/65.00 92.35/65.00 f(X, g(X), Y) -> f(Y, Y, Y) 92.35/65.00 g(b) -> c 92.35/65.00 b -> c 92.35/65.00 92.35/65.00 92.35/65.00 92.35/65.00 Outermost Strategy. 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (1) Trivial-Transformation (SOUND) 92.35/65.00 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (2) 92.35/65.00 Obligation: 92.35/65.00 Q restricted rewrite system: 92.35/65.00 The TRS R consists of the following rules: 92.35/65.00 92.35/65.00 f(X, g(X), Y) -> f(Y, Y, Y) 92.35/65.00 g(b) -> c 92.35/65.00 b -> c 92.35/65.00 92.35/65.00 Q is empty. 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (3) DependencyPairsProof (EQUIVALENT) 92.35/65.00 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (4) 92.35/65.00 Obligation: 92.35/65.00 Q DP problem: 92.35/65.00 The TRS P consists of the following rules: 92.35/65.00 92.35/65.00 F(X, g(X), Y) -> F(Y, Y, Y) 92.35/65.00 92.35/65.00 The TRS R consists of the following rules: 92.35/65.00 92.35/65.00 f(X, g(X), Y) -> f(Y, Y, Y) 92.35/65.00 g(b) -> c 92.35/65.00 b -> c 92.35/65.00 92.35/65.00 Q is empty. 92.35/65.00 We have to consider all minimal (P,Q,R)-chains. 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (5) TransformationProof (EQUIVALENT) 92.35/65.00 By forward instantiating [JAR06] the rule F(X, g(X), Y) -> F(Y, Y, Y) we obtained the following new rules [LPAR04]: 92.35/65.00 92.35/65.00 (F(x0, g(x0), g(y_1)) -> F(g(y_1), g(y_1), g(y_1)),F(x0, g(x0), g(y_1)) -> F(g(y_1), g(y_1), g(y_1))) 92.35/65.00 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (6) 92.35/65.00 Obligation: 92.35/65.00 Q DP problem: 92.35/65.00 The TRS P consists of the following rules: 92.35/65.00 92.35/65.00 F(x0, g(x0), g(y_1)) -> F(g(y_1), g(y_1), g(y_1)) 92.35/65.00 92.35/65.00 The TRS R consists of the following rules: 92.35/65.00 92.35/65.00 f(X, g(X), Y) -> f(Y, Y, Y) 92.35/65.00 g(b) -> c 92.35/65.00 b -> c 92.35/65.00 92.35/65.00 Q is empty. 92.35/65.00 We have to consider all minimal (P,Q,R)-chains. 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (7) NonTerminationLoopProof (COMPLETE) 92.35/65.00 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 92.35/65.00 Found a loop by narrowing to the right: 92.35/65.00 92.35/65.00 s = F(x0, g(x0), g(b)) evaluates to t =F(c, g(c), g(b)) 92.35/65.00 92.35/65.00 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 92.35/65.00 * Matcher: [x0 / c] 92.35/65.00 * Semiunifier: [ ] 92.35/65.00 92.35/65.00 -------------------------------------------------------------------------------- 92.35/65.00 Rewriting sequence 92.35/65.00 92.35/65.00 F(x0, g(x0), g(b)) -> F(g(b), g(b), g(b)) 92.35/65.00 with rule F(x0, g(x0), g(y_1)) -> F(g(y_1), g(y_1), g(y_1)) and matcher [y_1 / b]. 92.35/65.00 92.35/65.00 F(g(b), g(b), g(b)) -> F(c, g(b), g(b)) 92.35/65.00 with rule g(b) -> c at position [0] and matcher [ ] 92.35/65.00 92.35/65.00 F(c, g(b), g(b)) -> F(c, g(c), g(b)) 92.35/65.00 with rule b -> c at position [1,0] and matcher [ ] 92.35/65.00 92.35/65.00 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 92.35/65.00 92.35/65.00 92.35/65.00 All these steps are and every following step will be a correct step w.r.t to Q. 92.35/65.00 92.35/65.00 92.35/65.00 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (8) 92.35/65.00 NO 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (9) Thiemann-SpecialC-Transformation (EQUIVALENT) 92.35/65.00 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (10) 92.35/65.00 Obligation: 92.35/65.00 Q restricted rewrite system: 92.35/65.00 The TRS R consists of the following rules: 92.35/65.00 92.35/65.00 top(go_up(x)) -> top(reduce(x)) 92.35/65.00 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.00 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.00 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.00 redex_g(b) -> result_g(c) 92.35/65.00 reduce(b) -> go_up(c) 92.35/65.00 check_f(result_f(x)) -> go_up(x) 92.35/65.00 check_g(result_g(x)) -> go_up(x) 92.35/65.00 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.00 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.00 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.00 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.00 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.00 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.00 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.00 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.00 92.35/65.00 The set Q consists of the following terms: 92.35/65.00 92.35/65.00 top(go_up(x0)) 92.35/65.00 reduce(f(x0, x1, x2)) 92.35/65.00 reduce(g(x0)) 92.35/65.00 redex_f(x0, g(x0), x1) 92.35/65.00 redex_g(b) 92.35/65.00 reduce(b) 92.35/65.00 check_f(result_f(x0)) 92.35/65.00 check_g(result_g(x0)) 92.35/65.00 check_f(redex_f(x0, x1, x2)) 92.35/65.00 check_g(redex_g(x0)) 92.35/65.00 in_f_1(go_up(x0), x1, x2) 92.35/65.00 in_f_2(x0, go_up(x1), x2) 92.35/65.00 in_f_3(x0, x1, go_up(x2)) 92.35/65.00 in_g_1(go_up(x0)) 92.35/65.00 92.35/65.00 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (11) DependencyPairsProof (EQUIVALENT) 92.35/65.00 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 92.35/65.00 ---------------------------------------- 92.35/65.00 92.35/65.00 (12) 92.35/65.00 Obligation: 92.35/65.00 Q DP problem: 92.35/65.00 The TRS P consists of the following rules: 92.35/65.00 92.35/65.00 TOP(go_up(x)) -> TOP(reduce(x)) 92.35/65.00 TOP(go_up(x)) -> REDUCE(x) 92.35/65.00 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.00 REDUCE(f(x_1, x_2, x_3)) -> REDEX_F(x_1, x_2, x_3) 92.35/65.00 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 92.35/65.00 REDUCE(g(x_1)) -> REDEX_G(x_1) 92.35/65.00 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_1(reduce(x_1), x_2, x_3) 92.35/65.00 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.00 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_2(x_1, reduce(x_2), x_3) 92.35/65.00 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.00 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_3(x_1, x_2, reduce(x_3)) 92.35/65.00 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.00 CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1)) 92.35/65.00 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 92.35/65.00 92.35/65.00 The TRS R consists of the following rules: 92.35/65.00 92.35/65.00 top(go_up(x)) -> top(reduce(x)) 92.35/65.00 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.00 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.00 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.00 redex_g(b) -> result_g(c) 92.35/65.00 reduce(b) -> go_up(c) 92.35/65.00 check_f(result_f(x)) -> go_up(x) 92.35/65.00 check_g(result_g(x)) -> go_up(x) 92.35/65.00 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.00 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.00 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.00 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.00 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.00 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.00 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.00 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.00 92.35/65.00 The set Q consists of the following terms: 92.35/65.00 92.35/65.00 top(go_up(x0)) 92.35/65.00 reduce(f(x0, x1, x2)) 92.35/65.00 reduce(g(x0)) 92.35/65.00 redex_f(x0, g(x0), x1) 92.35/65.00 redex_g(b) 92.35/65.00 reduce(b) 92.35/65.00 check_f(result_f(x0)) 92.35/65.00 check_g(result_g(x0)) 92.35/65.00 check_f(redex_f(x0, x1, x2)) 92.35/65.00 check_g(redex_g(x0)) 92.35/65.00 in_f_1(go_up(x0), x1, x2) 92.35/65.00 in_f_2(x0, go_up(x1), x2) 92.35/65.00 in_f_3(x0, x1, go_up(x2)) 92.35/65.00 in_g_1(go_up(x0)) 92.35/65.00 92.35/65.00 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (13) DependencyGraphProof (EQUIVALENT) 92.35/65.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 7 less nodes. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (14) 92.35/65.01 Complex Obligation (AND) 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (15) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 92.35/65.01 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 top(go_up(x)) -> top(reduce(x)) 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (16) UsableRulesProof (EQUIVALENT) 92.35/65.01 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. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (17) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 92.35/65.01 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (18) QReductionProof (EQUIVALENT) 92.35/65.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (19) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 92.35/65.01 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (20) QDPOrderProof (EQUIVALENT) 92.35/65.01 We use the reduction pair processor [LPAR04,JAR06]. 92.35/65.01 92.35/65.01 92.35/65.01 The following pairs can be oriented strictly and are deleted. 92.35/65.01 92.35/65.01 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 92.35/65.01 The remaining pairs can at least be oriented weakly. 92.35/65.01 Used ordering: Polynomial interpretation [POLO]: 92.35/65.01 92.35/65.01 POL(CHECK_F(x_1)) = x_1 92.35/65.01 POL(CHECK_G(x_1)) = x_1 92.35/65.01 POL(REDUCE(x_1)) = x_1 92.35/65.01 POL(b) = 1 92.35/65.01 POL(c) = 1 92.35/65.01 POL(f(x_1, x_2, x_3)) = x_1 + x_2 + x_3 92.35/65.01 POL(g(x_1)) = 1 + x_1 92.35/65.01 POL(redex_f(x_1, x_2, x_3)) = x_1 + x_2 + x_3 92.35/65.01 POL(redex_g(x_1)) = x_1 92.35/65.01 POL(result_f(x_1)) = 1 92.35/65.01 POL(result_g(x_1)) = x_1 92.35/65.01 92.35/65.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 92.35/65.01 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (21) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (22) DependencyGraphProof (EQUIVALENT) 92.35/65.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (23) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (24) UsableRulesProof (EQUIVALENT) 92.35/65.01 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. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (25) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (26) QReductionProof (EQUIVALENT) 92.35/65.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 92.35/65.01 92.35/65.01 redex_g(b) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (27) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (28) QDPOrderProof (EQUIVALENT) 92.35/65.01 We use the reduction pair processor [LPAR04,JAR06]. 92.35/65.01 92.35/65.01 92.35/65.01 The following pairs can be oriented strictly and are deleted. 92.35/65.01 92.35/65.01 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 92.35/65.01 The remaining pairs can at least be oriented weakly. 92.35/65.01 Used ordering: Polynomial interpretation [POLO]: 92.35/65.01 92.35/65.01 POL(CHECK_F(x_1)) = x_1 92.35/65.01 POL(REDUCE(x_1)) = x_1 92.35/65.01 POL(f(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 92.35/65.01 POL(g(x_1)) = 1 92.35/65.01 POL(redex_f(x_1, x_2, x_3)) = x_1 + x_2 + x_3 92.35/65.01 POL(result_f(x_1)) = 1 92.35/65.01 92.35/65.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 92.35/65.01 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (29) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 92.35/65.01 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (30) DependencyGraphProof (EQUIVALENT) 92.35/65.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (31) 92.35/65.01 TRUE 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (32) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(x)) -> TOP(reduce(x)) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 top(go_up(x)) -> top(reduce(x)) 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (33) UsableRulesProof (EQUIVALENT) 92.35/65.01 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. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (34) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(x)) -> TOP(reduce(x)) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (35) QReductionProof (EQUIVALENT) 92.35/65.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (36) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(x)) -> TOP(reduce(x)) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (37) TransformationProof (EQUIVALENT) 92.35/65.01 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 92.35/65.01 92.35/65.01 (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)))) 92.35/65.01 (TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))) 92.35/65.01 (TOP(go_up(b)) -> TOP(go_up(c)),TOP(go_up(b)) -> TOP(go_up(c))) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (38) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) 92.35/65.01 TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) 92.35/65.01 TOP(go_up(b)) -> TOP(go_up(c)) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (39) DependencyGraphProof (EQUIVALENT) 92.35/65.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (40) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) 92.35/65.01 TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (41) UsableRulesProof (EQUIVALENT) 92.35/65.01 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. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (42) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(x)) -> TOP(reduce(x)) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (43) QReductionProof (EQUIVALENT) 92.35/65.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 92.35/65.01 92.35/65.01 top(go_up(x0)) 92.35/65.01 92.35/65.01 92.35/65.01 ---------------------------------------- 92.35/65.01 92.35/65.01 (44) 92.35/65.01 Obligation: 92.35/65.01 Q DP problem: 92.35/65.01 The TRS P consists of the following rules: 92.35/65.01 92.35/65.01 TOP(go_up(x)) -> TOP(reduce(x)) 92.35/65.01 92.35/65.01 The TRS R consists of the following rules: 92.35/65.01 92.35/65.01 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 92.35/65.01 reduce(g(x_1)) -> check_g(redex_g(x_1)) 92.35/65.01 reduce(b) -> go_up(c) 92.35/65.01 redex_g(b) -> result_g(c) 92.35/65.01 check_g(result_g(x)) -> go_up(x) 92.35/65.01 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 92.35/65.01 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 92.35/65.01 redex_f(X, g(X), Y) -> result_f(f(Y, Y, Y)) 92.35/65.01 check_f(result_f(x)) -> go_up(x) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 92.35/65.01 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 92.35/65.01 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 92.35/65.01 92.35/65.01 The set Q consists of the following terms: 92.35/65.01 92.35/65.01 reduce(f(x0, x1, x2)) 92.35/65.01 reduce(g(x0)) 92.35/65.01 redex_f(x0, g(x0), x1) 92.35/65.01 redex_g(b) 92.35/65.01 reduce(b) 92.35/65.01 check_f(result_f(x0)) 92.35/65.01 check_g(result_g(x0)) 92.35/65.01 check_f(redex_f(x0, x1, x2)) 92.35/65.01 check_g(redex_g(x0)) 92.35/65.01 in_f_1(go_up(x0), x1, x2) 92.35/65.01 in_f_2(x0, go_up(x1), x2) 92.35/65.01 in_f_3(x0, x1, go_up(x2)) 92.35/65.01 in_g_1(go_up(x0)) 92.35/65.01 92.35/65.01 We have to consider all minimal (P,Q,R)-chains. 92.51/65.08 EOF