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