111.22/91.57 MAYBE 111.22/91.58 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 111.22/91.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 111.22/91.58 111.22/91.58 111.22/91.58 Outermost Termination of the given OTRS could not be shown: 111.22/91.58 111.22/91.58 (0) OTRS 111.22/91.58 (1) Trivial-Transformation [SOUND, 0 ms] 111.22/91.58 (2) QTRS 111.22/91.58 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 111.22/91.58 (4) QDP 111.22/91.58 (5) MNOCProof [EQUIVALENT, 0 ms] 111.22/91.58 (6) QDP 111.22/91.58 (7) TransformationProof [EQUIVALENT, 0 ms] 111.22/91.58 (8) QDP 111.22/91.58 (9) MNOCProof [EQUIVALENT, 0 ms] 111.22/91.58 (10) QDP 111.22/91.58 (11) NonTerminationLoopProof [COMPLETE, 0 ms] 111.22/91.58 (12) NO 111.22/91.58 (13) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 111.22/91.58 (14) QTRS 111.22/91.58 (15) DependencyPairsProof [EQUIVALENT, 0 ms] 111.22/91.58 (16) QDP 111.22/91.58 (17) DependencyGraphProof [EQUIVALENT, 0 ms] 111.22/91.58 (18) AND 111.22/91.58 (19) QDP 111.22/91.58 (20) UsableRulesProof [EQUIVALENT, 0 ms] 111.22/91.58 (21) QDP 111.22/91.58 (22) QReductionProof [EQUIVALENT, 0 ms] 111.22/91.58 (23) QDP 111.22/91.58 (24) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 111.22/91.58 (25) QDP 111.22/91.58 (26) DependencyGraphProof [EQUIVALENT, 0 ms] 111.22/91.58 (27) TRUE 111.22/91.58 (28) QDP 111.22/91.58 (29) UsableRulesProof [EQUIVALENT, 0 ms] 111.22/91.58 (30) QDP 111.22/91.58 (31) QReductionProof [EQUIVALENT, 0 ms] 111.22/91.58 (32) QDP 111.22/91.58 (33) TransformationProof [EQUIVALENT, 0 ms] 111.22/91.58 (34) QDP 111.22/91.58 (35) TransformationProof [EQUIVALENT, 0 ms] 111.22/91.58 (36) QDP 111.22/91.58 (37) TransformationProof [EQUIVALENT, 0 ms] 111.22/91.58 (38) QDP 111.22/91.58 (39) TransformationProof [EQUIVALENT, 0 ms] 111.22/91.58 (40) QDP 111.22/91.58 (41) TransformationProof [EQUIVALENT, 0 ms] 111.22/91.58 (42) QDP 111.22/91.58 (43) QDPOrderProof [EQUIVALENT, 12 ms] 111.22/91.58 (44) QDP 111.22/91.58 (45) SplitQDPProof [EQUIVALENT, 0 ms] 111.22/91.58 (46) AND 111.22/91.58 (47) QDP 111.22/91.58 (48) SemLabProof [SOUND, 0 ms] 111.22/91.58 (49) QDP 111.22/91.58 (50) QDPOrderProof [EQUIVALENT, 0 ms] 111.22/91.58 (51) QDP 111.22/91.58 (52) PisEmptyProof [SOUND, 0 ms] 111.22/91.58 (53) TRUE 111.22/91.58 (54) QDP 111.22/91.58 (55) UsableRulesProof [EQUIVALENT, 0 ms] 111.22/91.58 (56) QDP 111.22/91.58 (57) QReductionProof [EQUIVALENT, 0 ms] 111.22/91.58 (58) QDP 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (0) 111.22/91.58 Obligation: 111.22/91.58 Term rewrite system R: 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 g(x, x) -> f(f(x, x), x) 111.22/91.58 f(x, x) -> g(x, x) 111.22/91.58 f(x, y) -> y 111.22/91.58 111.22/91.58 111.22/91.58 111.22/91.58 Outermost Strategy. 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (1) Trivial-Transformation (SOUND) 111.22/91.58 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (2) 111.22/91.58 Obligation: 111.22/91.58 Q restricted rewrite system: 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 g(x, x) -> f(f(x, x), x) 111.22/91.58 f(x, x) -> g(x, x) 111.22/91.58 f(x, y) -> y 111.22/91.58 111.22/91.58 Q is empty. 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (3) DependencyPairsProof (EQUIVALENT) 111.22/91.58 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (4) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 G(x, x) -> F(f(x, x), x) 111.22/91.58 G(x, x) -> F(x, x) 111.22/91.58 F(x, x) -> G(x, x) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 g(x, x) -> f(f(x, x), x) 111.22/91.58 f(x, x) -> g(x, x) 111.22/91.58 f(x, y) -> y 111.22/91.58 111.22/91.58 Q is empty. 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (5) MNOCProof (EQUIVALENT) 111.22/91.58 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (6) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 G(x, x) -> F(f(x, x), x) 111.22/91.58 G(x, x) -> F(x, x) 111.22/91.58 F(x, x) -> G(x, x) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 g(x, x) -> f(f(x, x), x) 111.22/91.58 f(x, x) -> g(x, x) 111.22/91.58 f(x, y) -> y 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 g(x0, x0) 111.22/91.58 f(x0, x1) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (7) TransformationProof (EQUIVALENT) 111.22/91.58 By narrowing [LPAR04] the rule G(x, x) -> F(f(x, x), x) at position [0] we obtained the following new rules [LPAR04]: 111.22/91.58 111.22/91.58 (G(x0, x0) -> F(g(x0, x0), x0),G(x0, x0) -> F(g(x0, x0), x0)) 111.22/91.58 (G(x0, x0) -> F(x0, x0),G(x, x) -> F(x, x)) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (8) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 G(x, x) -> F(x, x) 111.22/91.58 F(x, x) -> G(x, x) 111.22/91.58 G(x0, x0) -> F(g(x0, x0), x0) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 g(x, x) -> f(f(x, x), x) 111.22/91.58 f(x, x) -> g(x, x) 111.22/91.58 f(x, y) -> y 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 g(x0, x0) 111.22/91.58 f(x0, x1) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (9) MNOCProof (EQUIVALENT) 111.22/91.58 We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (10) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 G(x, x) -> F(x, x) 111.22/91.58 F(x, x) -> G(x, x) 111.22/91.58 G(x0, x0) -> F(g(x0, x0), x0) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 g(x, x) -> f(f(x, x), x) 111.22/91.58 f(x, x) -> g(x, x) 111.22/91.58 f(x, y) -> y 111.22/91.58 111.22/91.58 Q is empty. 111.22/91.58 We have to consider all (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (11) NonTerminationLoopProof (COMPLETE) 111.22/91.58 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 111.22/91.58 Found a loop by narrowing to the right: 111.22/91.58 111.22/91.58 s = G(x', x') evaluates to t =G(x', x') 111.22/91.58 111.22/91.58 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 111.22/91.58 * Matcher: [ ] 111.22/91.58 * Semiunifier: [ ] 111.22/91.58 111.22/91.58 -------------------------------------------------------------------------------- 111.22/91.58 Rewriting sequence 111.22/91.58 111.22/91.58 G(x', x') -> F(x', x') 111.22/91.58 with rule G(x, x) -> F(x, x) and matcher [x / x']. 111.22/91.58 111.22/91.58 F(x', x') -> G(x', x') 111.22/91.58 with rule F(x'', x'') -> G(x'', x'') at position [] and matcher [x'' / x'] 111.22/91.58 111.22/91.58 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 111.22/91.58 111.22/91.58 111.22/91.58 All these steps are and every following step will be a correct step w.r.t to Q. 111.22/91.58 111.22/91.58 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (12) 111.22/91.58 NO 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (13) Thiemann-SpecialC-Transformation (EQUIVALENT) 111.22/91.58 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (14) 111.22/91.58 Obligation: 111.22/91.58 Q restricted rewrite system: 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 top(go_up(x)) -> top(reduce(x)) 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 111.22/91.58 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (15) DependencyPairsProof (EQUIVALENT) 111.22/91.58 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (16) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(x)) -> TOP(reduce(x)) 111.22/91.58 TOP(go_up(x)) -> REDUCE(x) 111.22/91.58 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 111.22/91.58 REDUCE(g(x_1, x_2)) -> REDEX_G(x_1, x_2) 111.22/91.58 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 111.22/91.58 REDUCE(f(x_1, x_2)) -> REDEX_F(x_1, x_2) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> IN_G_1(reduce(x_1), x_2) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> IN_G_2(x_1, reduce(x_2)) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 111.22/91.58 CHECK_F(redex_f(x_1, x_2)) -> IN_F_1(reduce(x_1), x_2) 111.22/91.58 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 111.22/91.58 CHECK_F(redex_f(x_1, x_2)) -> IN_F_2(x_1, reduce(x_2)) 111.22/91.58 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 top(go_up(x)) -> top(reduce(x)) 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 111.22/91.58 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (17) DependencyGraphProof (EQUIVALENT) 111.22/91.58 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 10 less nodes. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (18) 111.22/91.58 Complex Obligation (AND) 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (19) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 111.22/91.58 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 top(go_up(x)) -> top(reduce(x)) 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 111.22/91.58 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (20) UsableRulesProof (EQUIVALENT) 111.22/91.58 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. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (21) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 111.22/91.58 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (22) QReductionProof (EQUIVALENT) 111.22/91.58 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (23) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 111.22/91.58 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 redex_g(x0, x0) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (24) UsableRulesReductionPairsProof (EQUIVALENT) 111.22/91.58 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. 111.22/91.58 111.22/91.58 The following dependency pairs can be deleted: 111.22/91.58 111.22/91.58 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 111.22/91.58 No rules are removed from R. 111.22/91.58 111.22/91.58 Used ordering: POLO with Polynomial interpretation [POLO]: 111.22/91.58 111.22/91.58 POL(CHECK_G(x_1)) = 2*x_1 111.22/91.58 POL(REDUCE(x_1)) = 2*x_1 111.22/91.58 POL(f(x_1, x_2)) = x_1 + x_2 111.22/91.58 POL(g(x_1, x_2)) = 2*x_1 + 2*x_2 111.22/91.58 POL(redex_g(x_1, x_2)) = 2*x_1 + x_2 111.22/91.58 POL(result_g(x_1)) = x_1 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (25) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 111.22/91.58 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 redex_g(x0, x0) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (26) DependencyGraphProof (EQUIVALENT) 111.22/91.58 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (27) 111.22/91.58 TRUE 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (28) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(x)) -> TOP(reduce(x)) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 top(go_up(x)) -> top(reduce(x)) 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 111.22/91.58 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 111.22/91.58 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (29) UsableRulesProof (EQUIVALENT) 111.22/91.58 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. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (30) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(x)) -> TOP(reduce(x)) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (31) QReductionProof (EQUIVALENT) 111.22/91.58 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (32) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(x)) -> TOP(reduce(x)) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (33) TransformationProof (EQUIVALENT) 111.22/91.58 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 111.22/91.58 111.22/91.58 (TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))),TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1)))) 111.22/91.58 (TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))),TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1)))) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (34) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (35) TransformationProof (EQUIVALENT) 111.22/91.58 By narrowing [LPAR04] the rule TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) at position [0,0] we obtained the following new rules [LPAR04]: 111.22/91.58 111.22/91.58 (TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(g(x0, x0)))),TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(g(x0, x0))))) 111.22/91.58 (TOP(go_up(f(x0, x1))) -> TOP(check_f(result_f(x1))),TOP(go_up(f(x0, x1))) -> TOP(check_f(result_f(x1)))) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (36) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(g(x0, x0)))) 111.22/91.58 TOP(go_up(f(x0, x1))) -> TOP(check_f(result_f(x1))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (37) TransformationProof (EQUIVALENT) 111.22/91.58 By rewriting [LPAR04] the rule TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(g(x0, x0)))) at position [0] we obtained the following new rules [LPAR04]: 111.22/91.58 111.22/91.58 (TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0))),TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0)))) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (38) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x1))) -> TOP(check_f(result_f(x1))) 111.22/91.58 TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (39) TransformationProof (EQUIVALENT) 111.22/91.58 By rewriting [LPAR04] the rule TOP(go_up(f(x0, x1))) -> TOP(check_f(result_f(x1))) at position [0] we obtained the following new rules [LPAR04]: 111.22/91.58 111.22/91.58 (TOP(go_up(f(x0, x1))) -> TOP(go_up(x1)),TOP(go_up(f(x0, x1))) -> TOP(go_up(x1))) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (40) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0))) 111.22/91.58 TOP(go_up(f(x0, x1))) -> TOP(go_up(x1)) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (41) TransformationProof (EQUIVALENT) 111.22/91.58 By forward instantiating [JAR06] the rule TOP(go_up(f(x0, x1))) -> TOP(go_up(x1)) we obtained the following new rules [LPAR04]: 111.22/91.58 111.22/91.58 (TOP(go_up(f(x0, g(y_0, y_1)))) -> TOP(go_up(g(y_0, y_1))),TOP(go_up(f(x0, g(y_0, y_1)))) -> TOP(go_up(g(y_0, y_1)))) 111.22/91.58 (TOP(go_up(f(x0, f(y_0, y_1)))) -> TOP(go_up(f(y_0, y_1))),TOP(go_up(f(x0, f(y_0, y_1)))) -> TOP(go_up(f(y_0, y_1)))) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (42) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0))) 111.22/91.58 TOP(go_up(f(x0, g(y_0, y_1)))) -> TOP(go_up(g(y_0, y_1))) 111.22/91.58 TOP(go_up(f(x0, f(y_0, y_1)))) -> TOP(go_up(f(y_0, y_1))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (43) QDPOrderProof (EQUIVALENT) 111.22/91.58 We use the reduction pair processor [LPAR04,JAR06]. 111.22/91.58 111.22/91.58 111.22/91.58 The following pairs can be oriented strictly and are deleted. 111.22/91.58 111.22/91.58 TOP(go_up(f(x0, g(y_0, y_1)))) -> TOP(go_up(g(y_0, y_1))) 111.22/91.58 TOP(go_up(f(x0, f(y_0, y_1)))) -> TOP(go_up(f(y_0, y_1))) 111.22/91.58 The remaining pairs can at least be oriented weakly. 111.22/91.58 Used ordering: Polynomial interpretation [POLO]: 111.22/91.58 111.22/91.58 POL(TOP(x_1)) = x_1 111.22/91.58 POL(check_f(x_1)) = x_1 111.22/91.58 POL(check_g(x_1)) = x_1 111.22/91.58 POL(f(x_1, x_2)) = 1 + x_2 111.22/91.58 POL(g(x_1, x_2)) = 1 + x_1 111.22/91.58 POL(go_up(x_1)) = x_1 111.22/91.58 POL(in_g_1(x_1, x_2)) = 1 + x_1 111.22/91.58 POL(in_g_2(x_1, x_2)) = 1 + x_1 111.22/91.58 POL(redex_f(x_1, x_2)) = 1 + x_2 111.22/91.58 POL(redex_g(x_1, x_2)) = 1 + x_1 111.22/91.58 POL(reduce(x_1)) = x_1 111.22/91.58 POL(result_f(x_1)) = x_1 111.22/91.58 POL(result_g(x_1)) = x_1 111.22/91.58 111.22/91.58 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 111.22/91.58 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (44) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (45) SplitQDPProof (EQUIVALENT) 111.22/91.58 We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (46) 111.22/91.58 Complex Obligation (AND) 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (47) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 TOP(go_up(f(x0, x0))) -> TOP(go_up(g(x0, x0))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (48) SemLabProof (SOUND) 111.22/91.58 We found the following model for the rules of the TRSs R and P. 111.22/91.58 Interpretation over the domain with elements from 0 to 1. 111.22/91.58 result_f: 0 111.22/91.58 reduce: 0 111.22/91.58 in_g_1: 0 111.22/91.58 redex_f: 0 111.22/91.58 check_f: 0 111.22/91.58 in_g_2: 0 111.22/91.58 TOP: 0 111.22/91.58 g: 0 111.22/91.58 go_up: 0 111.22/91.58 result_g: 0 111.22/91.58 f: 1 + x0 111.22/91.58 check_g: 0 111.22/91.58 redex_g: 0 111.22/91.58 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (49) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP.0(go_up.0(g.0-0(x0, x1))) -> TOP.0(check_g.0(redex_g.0-0(x0, x1))) 111.22/91.58 TOP.0(go_up.0(g.0-1(x0, x1))) -> TOP.0(check_g.0(redex_g.0-1(x0, x1))) 111.22/91.58 TOP.0(go_up.0(g.1-0(x0, x1))) -> TOP.0(check_g.0(redex_g.1-0(x0, x1))) 111.22/91.58 TOP.0(go_up.0(g.1-1(x0, x1))) -> TOP.0(check_g.0(redex_g.1-1(x0, x1))) 111.22/91.58 TOP.0(go_up.1(f.0-0(x0, x0))) -> TOP.0(go_up.0(g.0-0(x0, x0))) 111.22/91.58 TOP.0(go_up.0(f.1-1(x0, x0))) -> TOP.0(go_up.0(g.1-1(x0, x0))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce.0(g.0-0(x_1, x_2)) -> check_g.0(redex_g.0-0(x_1, x_2)) 111.22/91.58 reduce.0(g.0-1(x_1, x_2)) -> check_g.0(redex_g.0-1(x_1, x_2)) 111.22/91.58 reduce.0(g.1-0(x_1, x_2)) -> check_g.0(redex_g.1-0(x_1, x_2)) 111.22/91.58 reduce.0(g.1-1(x_1, x_2)) -> check_g.0(redex_g.1-1(x_1, x_2)) 111.22/91.58 reduce.1(f.0-0(x_1, x_2)) -> check_f.0(redex_f.0-0(x_1, x_2)) 111.22/91.58 reduce.1(f.0-1(x_1, x_2)) -> check_f.0(redex_f.0-1(x_1, x_2)) 111.22/91.58 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 111.22/91.58 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 111.22/91.58 redex_f.0-0(x, x) -> result_f.0(g.0-0(x, x)) 111.22/91.58 redex_f.1-1(x, x) -> result_f.0(g.1-1(x, x)) 111.22/91.58 redex_f.0-0(x, y) -> result_f.0(y) 111.22/91.58 redex_f.0-1(x, y) -> result_f.1(y) 111.22/91.58 redex_f.1-0(x, y) -> result_f.0(y) 111.22/91.58 redex_f.1-1(x, y) -> result_f.1(y) 111.22/91.58 check_f.0(result_f.0(x)) -> go_up.0(x) 111.22/91.58 check_f.0(result_f.1(x)) -> go_up.1(x) 111.22/91.58 redex_g.0-0(x, x) -> result_g.0(f.1-0(f.0-0(x, x), x)) 111.22/91.58 redex_g.1-1(x, x) -> result_g.1(f.0-1(f.1-1(x, x), x)) 111.22/91.58 check_g.0(result_g.0(x)) -> go_up.0(x) 111.22/91.58 check_g.0(result_g.1(x)) -> go_up.1(x) 111.22/91.58 check_g.0(redex_g.0-0(x_1, x_2)) -> in_g_1.0-0(reduce.0(x_1), x_2) 111.22/91.58 check_g.0(redex_g.0-1(x_1, x_2)) -> in_g_1.0-1(reduce.0(x_1), x_2) 111.22/91.58 check_g.0(redex_g.1-0(x_1, x_2)) -> in_g_1.0-0(reduce.1(x_1), x_2) 111.22/91.58 check_g.0(redex_g.1-1(x_1, x_2)) -> in_g_1.0-1(reduce.1(x_1), x_2) 111.22/91.58 check_g.0(redex_g.0-0(x_1, x_2)) -> in_g_2.0-0(x_1, reduce.0(x_2)) 111.22/91.58 check_g.0(redex_g.0-1(x_1, x_2)) -> in_g_2.0-0(x_1, reduce.1(x_2)) 111.22/91.58 check_g.0(redex_g.1-0(x_1, x_2)) -> in_g_2.1-0(x_1, reduce.0(x_2)) 111.22/91.58 check_g.0(redex_g.1-1(x_1, x_2)) -> in_g_2.1-0(x_1, reduce.1(x_2)) 111.22/91.58 in_g_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(g.0-0(x_1, x_2)) 111.22/91.58 in_g_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(g.0-1(x_1, x_2)) 111.22/91.58 in_g_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(g.1-0(x_1, x_2)) 111.22/91.58 in_g_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(g.1-1(x_1, x_2)) 111.22/91.58 in_g_1.0-0(go_up.0(x_1), x_2) -> go_up.0(g.0-0(x_1, x_2)) 111.22/91.58 in_g_1.0-1(go_up.0(x_1), x_2) -> go_up.0(g.0-1(x_1, x_2)) 111.22/91.58 in_g_1.0-0(go_up.1(x_1), x_2) -> go_up.0(g.1-0(x_1, x_2)) 111.22/91.58 in_g_1.0-1(go_up.1(x_1), x_2) -> go_up.0(g.1-1(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce.0(g.0-0(x0, x1)) 111.22/91.58 reduce.0(g.0-1(x0, x1)) 111.22/91.58 reduce.0(g.1-0(x0, x1)) 111.22/91.58 reduce.0(g.1-1(x0, x1)) 111.22/91.58 reduce.1(f.0-0(x0, x1)) 111.22/91.58 reduce.1(f.0-1(x0, x1)) 111.22/91.58 reduce.0(f.1-0(x0, x1)) 111.22/91.58 reduce.0(f.1-1(x0, x1)) 111.22/91.58 redex_g.0-0(x0, x0) 111.22/91.58 redex_g.1-1(x0, x0) 111.22/91.58 redex_f.0-0(x0, x1) 111.22/91.58 redex_f.0-1(x0, x1) 111.22/91.58 redex_f.1-0(x0, x1) 111.22/91.58 redex_f.1-1(x0, x1) 111.22/91.58 check_g.0(result_g.0(x0)) 111.22/91.58 check_g.0(result_g.1(x0)) 111.22/91.58 check_f.0(result_f.0(x0)) 111.22/91.58 check_f.0(result_f.1(x0)) 111.22/91.58 check_g.0(redex_g.0-0(x0, x1)) 111.22/91.58 check_g.0(redex_g.0-1(x0, x1)) 111.22/91.58 check_g.0(redex_g.1-0(x0, x1)) 111.22/91.58 check_g.0(redex_g.1-1(x0, x1)) 111.22/91.58 in_g_1.0-0(go_up.0(x0), x1) 111.22/91.58 in_g_1.0-1(go_up.0(x0), x1) 111.22/91.58 in_g_1.0-0(go_up.1(x0), x1) 111.22/91.58 in_g_1.0-1(go_up.1(x0), x1) 111.22/91.58 in_g_2.0-0(x0, go_up.0(x1)) 111.22/91.58 in_g_2.0-0(x0, go_up.1(x1)) 111.22/91.58 in_g_2.1-0(x0, go_up.0(x1)) 111.22/91.58 in_g_2.1-0(x0, go_up.1(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (50) QDPOrderProof (EQUIVALENT) 111.22/91.58 We use the reduction pair processor [LPAR04,JAR06]. 111.22/91.58 111.22/91.58 111.22/91.58 The following pairs can be oriented strictly and are deleted. 111.22/91.58 111.22/91.58 TOP.0(go_up.1(f.0-0(x0, x0))) -> TOP.0(go_up.0(g.0-0(x0, x0))) 111.22/91.58 TOP.0(go_up.0(f.1-1(x0, x0))) -> TOP.0(go_up.0(g.1-1(x0, x0))) 111.22/91.58 The remaining pairs can at least be oriented weakly. 111.22/91.58 Used ordering: Polynomial interpretation [POLO]: 111.22/91.58 111.22/91.58 POL(TOP.0(x_1)) = x_1 111.22/91.58 POL(check_f.0(x_1)) = 0 111.22/91.58 POL(check_g.0(x_1)) = x_1 111.22/91.58 POL(f.0-0(x_1, x_2)) = 1 + x_2 111.22/91.58 POL(f.0-1(x_1, x_2)) = 0 111.22/91.58 POL(f.1-0(x_1, x_2)) = 0 111.22/91.58 POL(f.1-1(x_1, x_2)) = 1 + x_2 111.22/91.58 POL(g.0-0(x_1, x_2)) = 0 111.22/91.58 POL(g.0-1(x_1, x_2)) = 0 111.22/91.58 POL(g.1-0(x_1, x_2)) = 0 111.22/91.58 POL(g.1-1(x_1, x_2)) = 0 111.22/91.58 POL(go_up.0(x_1)) = x_1 111.22/91.58 POL(go_up.1(x_1)) = x_1 111.22/91.58 POL(in_g_1.0-0(x_1, x_2)) = 0 111.22/91.58 POL(in_g_1.0-1(x_1, x_2)) = 0 111.22/91.58 POL(in_g_2.0-0(x_1, x_2)) = 0 111.22/91.58 POL(in_g_2.1-0(x_1, x_2)) = 0 111.22/91.58 POL(redex_f.0-0(x_1, x_2)) = x_1 + x_2 111.22/91.58 POL(redex_f.0-1(x_1, x_2)) = 1 + x_1 + x_2 111.22/91.58 POL(redex_f.1-0(x_1, x_2)) = 1 + x_1 + x_2 111.22/91.58 POL(redex_f.1-1(x_1, x_2)) = x_1 111.22/91.58 POL(redex_g.0-0(x_1, x_2)) = 0 111.22/91.58 POL(redex_g.0-1(x_1, x_2)) = 0 111.22/91.58 POL(redex_g.1-0(x_1, x_2)) = 0 111.22/91.58 POL(redex_g.1-1(x_1, x_2)) = 0 111.22/91.58 POL(reduce.0(x_1)) = 0 111.22/91.58 POL(reduce.1(x_1)) = 0 111.22/91.58 POL(result_f.0(x_1)) = 1 111.22/91.58 POL(result_f.1(x_1)) = 1 + x_1 111.22/91.58 POL(result_g.0(x_1)) = x_1 111.22/91.58 POL(result_g.1(x_1)) = x_1 111.22/91.58 111.22/91.58 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 111.22/91.58 111.22/91.58 redex_g.0-0(x, x) -> result_g.0(f.1-0(f.0-0(x, x), x)) 111.22/91.58 check_g.0(result_g.0(x)) -> go_up.0(x) 111.22/91.58 check_g.0(result_g.1(x)) -> go_up.1(x) 111.22/91.58 check_g.0(redex_g.0-0(x_1, x_2)) -> in_g_1.0-0(reduce.0(x_1), x_2) 111.22/91.58 check_g.0(redex_g.0-1(x_1, x_2)) -> in_g_1.0-1(reduce.0(x_1), x_2) 111.22/91.58 check_g.0(redex_g.1-0(x_1, x_2)) -> in_g_1.0-0(reduce.1(x_1), x_2) 111.22/91.58 check_g.0(redex_g.1-1(x_1, x_2)) -> in_g_1.0-1(reduce.1(x_1), x_2) 111.22/91.58 check_g.0(redex_g.0-0(x_1, x_2)) -> in_g_2.0-0(x_1, reduce.0(x_2)) 111.22/91.58 check_g.0(redex_g.0-1(x_1, x_2)) -> in_g_2.0-0(x_1, reduce.1(x_2)) 111.22/91.58 check_g.0(redex_g.1-0(x_1, x_2)) -> in_g_2.1-0(x_1, reduce.0(x_2)) 111.22/91.58 check_g.0(redex_g.1-1(x_1, x_2)) -> in_g_2.1-0(x_1, reduce.1(x_2)) 111.22/91.58 redex_g.1-1(x, x) -> result_g.1(f.0-1(f.1-1(x, x), x)) 111.22/91.58 in_g_1.0-0(go_up.0(x_1), x_2) -> go_up.0(g.0-0(x_1, x_2)) 111.22/91.58 in_g_1.0-0(go_up.1(x_1), x_2) -> go_up.0(g.1-0(x_1, x_2)) 111.22/91.58 reduce.0(g.0-0(x_1, x_2)) -> check_g.0(redex_g.0-0(x_1, x_2)) 111.22/91.58 in_g_1.0-1(go_up.0(x_1), x_2) -> go_up.0(g.0-1(x_1, x_2)) 111.22/91.58 in_g_1.0-1(go_up.1(x_1), x_2) -> go_up.0(g.1-1(x_1, x_2)) 111.22/91.58 reduce.0(g.0-1(x_1, x_2)) -> check_g.0(redex_g.0-1(x_1, x_2)) 111.22/91.58 reduce.0(g.1-0(x_1, x_2)) -> check_g.0(redex_g.1-0(x_1, x_2)) 111.22/91.58 in_g_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(g.1-0(x_1, x_2)) 111.22/91.58 in_g_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(g.1-1(x_1, x_2)) 111.22/91.58 reduce.0(g.1-1(x_1, x_2)) -> check_g.0(redex_g.1-1(x_1, x_2)) 111.22/91.58 in_g_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(g.0-0(x_1, x_2)) 111.22/91.58 in_g_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(g.0-1(x_1, x_2)) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (51) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP.0(go_up.0(g.0-0(x0, x1))) -> TOP.0(check_g.0(redex_g.0-0(x0, x1))) 111.22/91.58 TOP.0(go_up.0(g.0-1(x0, x1))) -> TOP.0(check_g.0(redex_g.0-1(x0, x1))) 111.22/91.58 TOP.0(go_up.0(g.1-0(x0, x1))) -> TOP.0(check_g.0(redex_g.1-0(x0, x1))) 111.22/91.58 TOP.0(go_up.0(g.1-1(x0, x1))) -> TOP.0(check_g.0(redex_g.1-1(x0, x1))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce.0(g.0-0(x_1, x_2)) -> check_g.0(redex_g.0-0(x_1, x_2)) 111.22/91.58 reduce.0(g.0-1(x_1, x_2)) -> check_g.0(redex_g.0-1(x_1, x_2)) 111.22/91.58 reduce.0(g.1-0(x_1, x_2)) -> check_g.0(redex_g.1-0(x_1, x_2)) 111.22/91.58 reduce.0(g.1-1(x_1, x_2)) -> check_g.0(redex_g.1-1(x_1, x_2)) 111.22/91.58 reduce.1(f.0-0(x_1, x_2)) -> check_f.0(redex_f.0-0(x_1, x_2)) 111.22/91.58 reduce.1(f.0-1(x_1, x_2)) -> check_f.0(redex_f.0-1(x_1, x_2)) 111.22/91.58 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 111.22/91.58 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 111.22/91.58 redex_f.0-0(x, x) -> result_f.0(g.0-0(x, x)) 111.22/91.58 redex_f.1-1(x, x) -> result_f.0(g.1-1(x, x)) 111.22/91.58 redex_f.0-0(x, y) -> result_f.0(y) 111.22/91.58 redex_f.0-1(x, y) -> result_f.1(y) 111.22/91.58 redex_f.1-0(x, y) -> result_f.0(y) 111.22/91.58 redex_f.1-1(x, y) -> result_f.1(y) 111.22/91.58 check_f.0(result_f.0(x)) -> go_up.0(x) 111.22/91.58 check_f.0(result_f.1(x)) -> go_up.1(x) 111.22/91.58 redex_g.0-0(x, x) -> result_g.0(f.1-0(f.0-0(x, x), x)) 111.22/91.58 redex_g.1-1(x, x) -> result_g.1(f.0-1(f.1-1(x, x), x)) 111.22/91.58 check_g.0(result_g.0(x)) -> go_up.0(x) 111.22/91.58 check_g.0(result_g.1(x)) -> go_up.1(x) 111.22/91.58 check_g.0(redex_g.0-0(x_1, x_2)) -> in_g_1.0-0(reduce.0(x_1), x_2) 111.22/91.58 check_g.0(redex_g.0-1(x_1, x_2)) -> in_g_1.0-1(reduce.0(x_1), x_2) 111.22/91.58 check_g.0(redex_g.1-0(x_1, x_2)) -> in_g_1.0-0(reduce.1(x_1), x_2) 111.22/91.58 check_g.0(redex_g.1-1(x_1, x_2)) -> in_g_1.0-1(reduce.1(x_1), x_2) 111.22/91.58 check_g.0(redex_g.0-0(x_1, x_2)) -> in_g_2.0-0(x_1, reduce.0(x_2)) 111.22/91.58 check_g.0(redex_g.0-1(x_1, x_2)) -> in_g_2.0-0(x_1, reduce.1(x_2)) 111.22/91.58 check_g.0(redex_g.1-0(x_1, x_2)) -> in_g_2.1-0(x_1, reduce.0(x_2)) 111.22/91.58 check_g.0(redex_g.1-1(x_1, x_2)) -> in_g_2.1-0(x_1, reduce.1(x_2)) 111.22/91.58 in_g_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(g.0-0(x_1, x_2)) 111.22/91.58 in_g_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(g.0-1(x_1, x_2)) 111.22/91.58 in_g_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(g.1-0(x_1, x_2)) 111.22/91.58 in_g_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(g.1-1(x_1, x_2)) 111.22/91.58 in_g_1.0-0(go_up.0(x_1), x_2) -> go_up.0(g.0-0(x_1, x_2)) 111.22/91.58 in_g_1.0-1(go_up.0(x_1), x_2) -> go_up.0(g.0-1(x_1, x_2)) 111.22/91.58 in_g_1.0-0(go_up.1(x_1), x_2) -> go_up.0(g.1-0(x_1, x_2)) 111.22/91.58 in_g_1.0-1(go_up.1(x_1), x_2) -> go_up.0(g.1-1(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce.0(g.0-0(x0, x1)) 111.22/91.58 reduce.0(g.0-1(x0, x1)) 111.22/91.58 reduce.0(g.1-0(x0, x1)) 111.22/91.58 reduce.0(g.1-1(x0, x1)) 111.22/91.58 reduce.1(f.0-0(x0, x1)) 111.22/91.58 reduce.1(f.0-1(x0, x1)) 111.22/91.58 reduce.0(f.1-0(x0, x1)) 111.22/91.58 reduce.0(f.1-1(x0, x1)) 111.22/91.58 redex_g.0-0(x0, x0) 111.22/91.58 redex_g.1-1(x0, x0) 111.22/91.58 redex_f.0-0(x0, x1) 111.22/91.58 redex_f.0-1(x0, x1) 111.22/91.58 redex_f.1-0(x0, x1) 111.22/91.58 redex_f.1-1(x0, x1) 111.22/91.58 check_g.0(result_g.0(x0)) 111.22/91.58 check_g.0(result_g.1(x0)) 111.22/91.58 check_f.0(result_f.0(x0)) 111.22/91.58 check_f.0(result_f.1(x0)) 111.22/91.58 check_g.0(redex_g.0-0(x0, x1)) 111.22/91.58 check_g.0(redex_g.0-1(x0, x1)) 111.22/91.58 check_g.0(redex_g.1-0(x0, x1)) 111.22/91.58 check_g.0(redex_g.1-1(x0, x1)) 111.22/91.58 in_g_1.0-0(go_up.0(x0), x1) 111.22/91.58 in_g_1.0-1(go_up.0(x0), x1) 111.22/91.58 in_g_1.0-0(go_up.1(x0), x1) 111.22/91.58 in_g_1.0-1(go_up.1(x0), x1) 111.22/91.58 in_g_2.0-0(x0, go_up.0(x1)) 111.22/91.58 in_g_2.0-0(x0, go_up.1(x1)) 111.22/91.58 in_g_2.1-0(x0, go_up.0(x1)) 111.22/91.58 in_g_2.1-0(x0, go_up.1(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (52) PisEmptyProof (SOUND) 111.22/91.58 The TRS P is empty. Hence, there is no (P,Q,R) chain. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (53) 111.22/91.58 TRUE 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (54) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (55) UsableRulesProof (EQUIVALENT) 111.22/91.58 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. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (56) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(x)) -> TOP(reduce(x)) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (57) QReductionProof (EQUIVALENT) 111.22/91.58 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 111.22/91.58 111.22/91.58 top(go_up(x0)) 111.22/91.58 in_f_1(go_up(x0), x1) 111.22/91.58 in_f_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 111.22/91.58 ---------------------------------------- 111.22/91.58 111.22/91.58 (58) 111.22/91.58 Obligation: 111.22/91.58 Q DP problem: 111.22/91.58 The TRS P consists of the following rules: 111.22/91.58 111.22/91.58 TOP(go_up(x)) -> TOP(reduce(x)) 111.22/91.58 111.22/91.58 The TRS R consists of the following rules: 111.22/91.58 111.22/91.58 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 111.22/91.58 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 111.22/91.58 redex_f(x, x) -> result_f(g(x, x)) 111.22/91.58 redex_f(x, y) -> result_f(y) 111.22/91.58 check_f(result_f(x)) -> go_up(x) 111.22/91.58 redex_g(x, x) -> result_g(f(f(x, x), x)) 111.22/91.58 check_g(result_g(x)) -> go_up(x) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 111.22/91.58 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 111.22/91.58 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 111.22/91.58 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 111.22/91.58 111.22/91.58 The set Q consists of the following terms: 111.22/91.58 111.22/91.58 reduce(g(x0, x1)) 111.22/91.58 reduce(f(x0, x1)) 111.22/91.58 redex_g(x0, x0) 111.22/91.58 redex_f(x0, x1) 111.22/91.58 check_g(result_g(x0)) 111.22/91.58 check_f(result_f(x0)) 111.22/91.58 check_g(redex_g(x0, x1)) 111.22/91.58 in_g_1(go_up(x0), x1) 111.22/91.58 in_g_2(x0, go_up(x1)) 111.22/91.58 111.22/91.58 We have to consider all minimal (P,Q,R)-chains. 111.22/91.63 EOF