54.07/20.62 YES 54.07/20.63 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 54.07/20.63 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 54.07/20.63 54.07/20.63 54.07/20.63 Outermost Termination of the given OTRS could be proven: 54.07/20.63 54.07/20.63 (0) OTRS 54.07/20.63 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 54.07/20.63 (2) QTRS 54.07/20.63 (3) QTRSRRRProof [EQUIVALENT, 82 ms] 54.07/20.63 (4) QTRS 54.07/20.63 (5) QTRSRRRProof [EQUIVALENT, 43 ms] 54.07/20.63 (6) QTRS 54.07/20.63 (7) QTRSRRRProof [EQUIVALENT, 33 ms] 54.07/20.63 (8) QTRS 54.07/20.63 (9) DependencyPairsProof [EQUIVALENT, 0 ms] 54.07/20.63 (10) QDP 54.07/20.63 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 54.07/20.63 (12) AND 54.07/20.63 (13) QDP 54.07/20.63 (14) UsableRulesProof [EQUIVALENT, 0 ms] 54.07/20.63 (15) QDP 54.07/20.63 (16) QReductionProof [EQUIVALENT, 0 ms] 54.07/20.63 (17) QDP 54.07/20.63 (18) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 54.07/20.63 (19) QDP 54.07/20.63 (20) DependencyGraphProof [EQUIVALENT, 0 ms] 54.07/20.63 (21) TRUE 54.07/20.63 (22) QDP 54.07/20.63 (23) UsableRulesProof [EQUIVALENT, 0 ms] 54.07/20.63 (24) QDP 54.07/20.63 (25) QReductionProof [EQUIVALENT, 0 ms] 54.07/20.63 (26) QDP 54.07/20.63 (27) TransformationProof [SOUND, 0 ms] 54.07/20.63 (28) QDP 54.07/20.63 (29) TransformationProof [EQUIVALENT, 0 ms] 54.07/20.63 (30) QDP 54.07/20.63 (31) TransformationProof [EQUIVALENT, 0 ms] 54.07/20.63 (32) QDP 54.07/20.63 (33) TransformationProof [SOUND, 0 ms] 54.07/20.63 (34) QDP 54.07/20.63 (35) TransformationProof [EQUIVALENT, 0 ms] 54.07/20.63 (36) QDP 54.07/20.63 (37) DependencyGraphProof [EQUIVALENT, 0 ms] 54.07/20.63 (38) QDP 54.07/20.63 (39) TransformationProof [EQUIVALENT, 0 ms] 54.07/20.63 (40) QDP 54.07/20.63 (41) DependencyGraphProof [EQUIVALENT, 0 ms] 54.07/20.63 (42) QDP 54.07/20.63 (43) QDPOrderProof [EQUIVALENT, 4 ms] 54.07/20.63 (44) QDP 54.07/20.63 (45) SemLabProof [SOUND, 227 ms] 54.07/20.63 (46) QDP 54.07/20.63 (47) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 54.07/20.63 (48) QDP 54.07/20.63 (49) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 54.07/20.63 (50) QDP 54.07/20.63 (51) MRRProof [EQUIVALENT, 0 ms] 54.07/20.63 (52) QDP 54.07/20.63 (53) MRRProof [EQUIVALENT, 9 ms] 54.07/20.63 (54) QDP 54.07/20.63 (55) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 54.07/20.63 (56) QDP 54.07/20.63 (57) MRRProof [EQUIVALENT, 0 ms] 54.07/20.63 (58) QDP 54.07/20.63 (59) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 54.07/20.63 (60) QDP 54.07/20.63 (61) UsableRulesReductionPairsProof [EQUIVALENT, 8 ms] 54.07/20.63 (62) QDP 54.07/20.63 (63) MRRProof [EQUIVALENT, 0 ms] 54.07/20.63 (64) QDP 54.07/20.63 (65) PisEmptyProof [EQUIVALENT, 0 ms] 54.07/20.63 (66) YES 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (0) 54.07/20.63 Obligation: 54.07/20.63 Term rewrite system R: 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 f(x, x) -> f(i(x), g(g(x))) 54.07/20.63 f(x, y) -> x 54.07/20.63 g(x) -> i(x) 54.07/20.63 f(x, i(x)) -> f(x, x) 54.07/20.63 f(i(x), i(g(x))) -> a 54.07/20.63 h(x, x) -> a 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 Outermost Strategy. 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 54.07/20.63 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (2) 54.07/20.63 Obligation: 54.07/20.63 Q restricted rewrite system: 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_f(x, y) -> result_f(x) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 redex_f(i(x), i(g(x))) -> result_f(a) 54.07/20.63 redex_h(x, x) -> result_h(a) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_h(result_h(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (3) QTRSRRRProof (EQUIVALENT) 54.07/20.63 Used ordering: 54.07/20.63 Polynomial interpretation [POLO]: 54.07/20.63 54.07/20.63 POL(a) = 0 54.07/20.63 POL(check_f(x_1)) = x_1 54.07/20.63 POL(check_g(x_1)) = x_1 54.07/20.63 POL(check_h(x_1)) = 1 + 2*x_1 54.07/20.63 POL(f(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 POL(g(x_1)) = x_1 54.07/20.63 POL(go_up(x_1)) = x_1 54.07/20.63 POL(h(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 54.07/20.63 POL(i(x_1)) = x_1 54.07/20.63 POL(in_f_1(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 POL(in_f_2(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 POL(in_g_1(x_1)) = x_1 54.07/20.63 POL(in_h_1(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 54.07/20.63 POL(in_h_2(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 54.07/20.63 POL(in_i_1(x_1)) = x_1 54.07/20.63 POL(redex_f(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 POL(redex_g(x_1)) = x_1 54.07/20.63 POL(redex_h(x_1, x_2)) = x_1 + x_2 54.07/20.63 POL(reduce(x_1)) = x_1 54.07/20.63 POL(result_f(x_1)) = x_1 54.07/20.63 POL(result_g(x_1)) = x_1 54.07/20.63 POL(result_h(x_1)) = 2*x_1 54.07/20.63 POL(top(x_1)) = 2*x_1 54.07/20.63 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 54.07/20.63 54.07/20.63 check_h(result_h(x)) -> go_up(x) 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (4) 54.07/20.63 Obligation: 54.07/20.63 Q restricted rewrite system: 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_f(x, y) -> result_f(x) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 redex_f(i(x), i(g(x))) -> result_f(a) 54.07/20.63 redex_h(x, x) -> result_h(a) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (5) QTRSRRRProof (EQUIVALENT) 54.07/20.63 Used ordering: 54.07/20.63 Polynomial interpretation [POLO]: 54.07/20.63 54.07/20.63 POL(a) = 0 54.07/20.63 POL(check_f(x_1)) = x_1 54.07/20.63 POL(check_g(x_1)) = x_1 54.07/20.63 POL(check_h(x_1)) = x_1 54.07/20.63 POL(f(x_1, x_2)) = x_1 + x_2 54.07/20.63 POL(g(x_1)) = x_1 54.07/20.63 POL(go_up(x_1)) = 2*x_1 54.07/20.63 POL(h(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.63 POL(i(x_1)) = x_1 54.07/20.63 POL(in_f_1(x_1, x_2)) = x_1 + 2*x_2 54.07/20.63 POL(in_f_2(x_1, x_2)) = 2*x_1 + x_2 54.07/20.63 POL(in_g_1(x_1)) = x_1 54.07/20.63 POL(in_h_1(x_1, x_2)) = 2 + x_1 + 2*x_2 54.07/20.63 POL(in_h_2(x_1, x_2)) = 2 + 2*x_1 + x_2 54.07/20.63 POL(in_i_1(x_1)) = x_1 54.07/20.63 POL(redex_f(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 POL(redex_g(x_1)) = 2*x_1 54.07/20.63 POL(redex_h(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 54.07/20.63 POL(reduce(x_1)) = 2*x_1 54.07/20.63 POL(result_f(x_1)) = 2*x_1 54.07/20.63 POL(result_g(x_1)) = 2*x_1 54.07/20.63 POL(result_h(x_1)) = 1 + 2*x_1 54.07/20.63 POL(top(x_1)) = 2*x_1 54.07/20.63 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 54.07/20.63 54.07/20.63 redex_h(x, x) -> result_h(a) 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (6) 54.07/20.63 Obligation: 54.07/20.63 Q restricted rewrite system: 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_f(x, y) -> result_f(x) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 redex_f(i(x), i(g(x))) -> result_f(a) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (7) QTRSRRRProof (EQUIVALENT) 54.07/20.63 Used ordering: 54.07/20.63 Polynomial interpretation [POLO]: 54.07/20.63 54.07/20.63 POL(a) = 0 54.07/20.63 POL(check_f(x_1)) = x_1 54.07/20.63 POL(check_g(x_1)) = x_1 54.07/20.63 POL(check_h(x_1)) = x_1 54.07/20.63 POL(f(x_1, x_2)) = 1 + 2*x_1 + x_2 54.07/20.63 POL(g(x_1)) = x_1 54.07/20.63 POL(go_up(x_1)) = x_1 54.07/20.63 POL(h(x_1, x_2)) = 2*x_1 + x_2 54.07/20.63 POL(i(x_1)) = x_1 54.07/20.63 POL(in_f_1(x_1, x_2)) = 1 + 2*x_1 + x_2 54.07/20.63 POL(in_f_2(x_1, x_2)) = 1 + 2*x_1 + x_2 54.07/20.63 POL(in_g_1(x_1)) = x_1 54.07/20.63 POL(in_h_1(x_1, x_2)) = 2*x_1 + x_2 54.07/20.63 POL(in_h_2(x_1, x_2)) = 2*x_1 + x_2 54.07/20.63 POL(in_i_1(x_1)) = x_1 54.07/20.63 POL(redex_f(x_1, x_2)) = 1 + 2*x_1 + x_2 54.07/20.63 POL(redex_g(x_1)) = x_1 54.07/20.63 POL(redex_h(x_1, x_2)) = 2*x_1 + x_2 54.07/20.63 POL(reduce(x_1)) = x_1 54.07/20.63 POL(result_f(x_1)) = x_1 54.07/20.63 POL(result_g(x_1)) = x_1 54.07/20.63 POL(top(x_1)) = 2*x_1 54.07/20.63 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 54.07/20.63 54.07/20.63 redex_f(x, y) -> result_f(x) 54.07/20.63 redex_f(i(x), i(g(x))) -> result_f(a) 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (8) 54.07/20.63 Obligation: 54.07/20.63 Q restricted rewrite system: 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (9) DependencyPairsProof (EQUIVALENT) 54.07/20.63 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (10) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 TOP(go_up(x)) -> TOP(reduce(x)) 54.07/20.63 TOP(go_up(x)) -> REDUCE(x) 54.07/20.63 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 54.07/20.63 REDUCE(f(x_1, x_2)) -> REDEX_F(x_1, x_2) 54.07/20.63 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 54.07/20.63 REDUCE(g(x_1)) -> REDEX_G(x_1) 54.07/20.63 REDUCE(h(x_1, x_2)) -> CHECK_H(redex_h(x_1, x_2)) 54.07/20.63 CHECK_F(redex_f(x_1, x_2)) -> IN_F_1(reduce(x_1), x_2) 54.07/20.63 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 54.07/20.63 CHECK_F(redex_f(x_1, x_2)) -> IN_F_2(x_1, reduce(x_2)) 54.07/20.63 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 54.07/20.63 CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1)) 54.07/20.63 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> IN_H_1(reduce(x_1), x_2) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_1) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> IN_H_2(x_1, reduce(x_2)) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_2) 54.07/20.63 REDUCE(i(x_1)) -> IN_I_1(reduce(x_1)) 54.07/20.63 REDUCE(i(x_1)) -> REDUCE(x_1) 54.07/20.63 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 We have to consider all minimal (P,Q,R)-chains. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (11) DependencyGraphProof (EQUIVALENT) 54.07/20.63 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 14 less nodes. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (12) 54.07/20.63 Complex Obligation (AND) 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (13) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 REDUCE(h(x_1, x_2)) -> CHECK_H(redex_h(x_1, x_2)) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_1) 54.07/20.63 REDUCE(i(x_1)) -> REDUCE(x_1) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_2) 54.07/20.63 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 We have to consider all minimal (P,Q,R)-chains. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (14) UsableRulesProof (EQUIVALENT) 54.07/20.63 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. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (15) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 REDUCE(h(x_1, x_2)) -> CHECK_H(redex_h(x_1, x_2)) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_1) 54.07/20.63 REDUCE(i(x_1)) -> REDUCE(x_1) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_2) 54.07/20.63 54.07/20.63 R is empty. 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 We have to consider all minimal (P,Q,R)-chains. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (16) QReductionProof (EQUIVALENT) 54.07/20.63 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (17) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 REDUCE(h(x_1, x_2)) -> CHECK_H(redex_h(x_1, x_2)) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_1) 54.07/20.63 REDUCE(i(x_1)) -> REDUCE(x_1) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_2) 54.07/20.63 54.07/20.63 R is empty. 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 redex_h(x0, x0) 54.07/20.63 54.07/20.63 We have to consider all minimal (P,Q,R)-chains. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (18) UsableRulesReductionPairsProof (EQUIVALENT) 54.07/20.63 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. 54.07/20.63 54.07/20.63 The following dependency pairs can be deleted: 54.07/20.63 54.07/20.63 REDUCE(h(x_1, x_2)) -> CHECK_H(redex_h(x_1, x_2)) 54.07/20.63 REDUCE(i(x_1)) -> REDUCE(x_1) 54.07/20.63 No rules are removed from R. 54.07/20.63 54.07/20.63 Used ordering: POLO with Polynomial interpretation [POLO]: 54.07/20.63 54.07/20.63 POL(CHECK_H(x_1)) = x_1 54.07/20.63 POL(REDUCE(x_1)) = 2*x_1 54.07/20.63 POL(h(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 POL(i(x_1)) = 2*x_1 54.07/20.63 POL(redex_h(x_1, x_2)) = 2*x_1 + 2*x_2 54.07/20.63 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (19) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_1) 54.07/20.63 CHECK_H(redex_h(x_1, x_2)) -> REDUCE(x_2) 54.07/20.63 54.07/20.63 R is empty. 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 redex_h(x0, x0) 54.07/20.63 54.07/20.63 We have to consider all minimal (P,Q,R)-chains. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (20) DependencyGraphProof (EQUIVALENT) 54.07/20.63 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (21) 54.07/20.63 TRUE 54.07/20.63 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (22) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 TOP(go_up(x)) -> TOP(reduce(x)) 54.07/20.63 54.07/20.63 The TRS R consists of the following rules: 54.07/20.63 54.07/20.63 top(go_up(x)) -> top(reduce(x)) 54.07/20.63 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.63 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.63 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.63 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.63 redex_g(x) -> result_g(i(x)) 54.07/20.63 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.63 check_f(result_f(x)) -> go_up(x) 54.07/20.63 check_g(result_g(x)) -> go_up(x) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 54.07/20.63 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 54.07/20.63 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.63 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.63 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.63 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 54.07/20.63 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 54.07/20.63 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.63 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 54.07/20.63 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.63 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.63 54.07/20.63 The set Q consists of the following terms: 54.07/20.63 54.07/20.63 top(go_up(x0)) 54.07/20.63 reduce(f(x0, x1)) 54.07/20.63 reduce(g(x0)) 54.07/20.63 reduce(h(x0, x1)) 54.07/20.63 redex_f(x0, x1) 54.07/20.63 redex_g(x0) 54.07/20.63 redex_h(x0, x0) 54.07/20.63 check_f(result_f(x0)) 54.07/20.63 check_g(result_g(x0)) 54.07/20.63 check_h(result_h(x0)) 54.07/20.63 check_h(redex_h(x0, x1)) 54.07/20.63 reduce(i(x0)) 54.07/20.63 in_f_1(go_up(x0), x1) 54.07/20.63 in_f_2(x0, go_up(x1)) 54.07/20.63 in_i_1(go_up(x0)) 54.07/20.63 in_g_1(go_up(x0)) 54.07/20.63 in_h_1(go_up(x0), x1) 54.07/20.63 in_h_2(x0, go_up(x1)) 54.07/20.63 54.07/20.63 We have to consider all minimal (P,Q,R)-chains. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (23) UsableRulesProof (EQUIVALENT) 54.07/20.63 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. 54.07/20.63 ---------------------------------------- 54.07/20.63 54.07/20.63 (24) 54.07/20.63 Obligation: 54.07/20.63 Q DP problem: 54.07/20.63 The TRS P consists of the following rules: 54.07/20.63 54.07/20.63 TOP(go_up(x)) -> TOP(reduce(x)) 54.07/20.63 54.07/20.63 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 top(go_up(x0)) 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_f_1(go_up(x0), x1) 54.07/20.64 in_f_2(x0, go_up(x1)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_g_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (25) QReductionProof (EQUIVALENT) 54.07/20.64 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 54.07/20.64 54.07/20.64 top(go_up(x0)) 54.07/20.64 in_f_1(go_up(x0), x1) 54.07/20.64 in_f_2(x0, go_up(x1)) 54.07/20.64 in_g_1(go_up(x0)) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (26) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(x)) -> TOP(reduce(x)) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (27) TransformationProof (SOUND) 54.07/20.64 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 54.07/20.64 54.07/20.64 (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)))) 54.07/20.64 (TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))) 54.07/20.64 (TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))),TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1)))) 54.07/20.64 (TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))),TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0)))) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (28) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (29) TransformationProof (EQUIVALENT) 54.07/20.64 By rewriting [LPAR04] the rule TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) at position [0,0] we obtained the following new rules [LPAR04]: 54.07/20.64 54.07/20.64 (TOP(go_up(g(x0))) -> TOP(check_g(result_g(i(x0)))),TOP(go_up(g(x0))) -> TOP(check_g(result_g(i(x0))))) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (30) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(check_g(result_g(i(x0)))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (31) TransformationProof (EQUIVALENT) 54.07/20.64 By rewriting [LPAR04] the rule TOP(go_up(g(x0))) -> TOP(check_g(result_g(i(x0)))) at position [0] we obtained the following new rules [LPAR04]: 54.07/20.64 54.07/20.64 (TOP(go_up(g(x0))) -> TOP(go_up(i(x0))),TOP(go_up(g(x0))) -> TOP(go_up(i(x0)))) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (32) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (33) TransformationProof (SOUND) 54.07/20.64 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]: 54.07/20.64 54.07/20.64 (TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(f(i(x0), g(g(x0)))))),TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(f(i(x0), g(g(x0))))))) 54.07/20.64 (TOP(go_up(f(x0, i(x0)))) -> TOP(check_f(result_f(f(x0, x0)))),TOP(go_up(f(x0, i(x0)))) -> TOP(check_f(result_f(f(x0, x0))))) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (34) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(f(i(x0), g(g(x0)))))) 54.07/20.64 TOP(go_up(f(x0, i(x0)))) -> TOP(check_f(result_f(f(x0, x0)))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (35) TransformationProof (EQUIVALENT) 54.07/20.64 By rewriting [LPAR04] the rule TOP(go_up(f(x0, x0))) -> TOP(check_f(result_f(f(i(x0), g(g(x0)))))) at position [0] we obtained the following new rules [LPAR04]: 54.07/20.64 54.07/20.64 (TOP(go_up(f(x0, x0))) -> TOP(go_up(f(i(x0), g(g(x0))))),TOP(go_up(f(x0, x0))) -> TOP(go_up(f(i(x0), g(g(x0)))))) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (36) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 TOP(go_up(f(x0, i(x0)))) -> TOP(check_f(result_f(f(x0, x0)))) 54.07/20.64 TOP(go_up(f(x0, x0))) -> TOP(go_up(f(i(x0), g(g(x0))))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (37) DependencyGraphProof (EQUIVALENT) 54.07/20.64 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (38) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 TOP(go_up(f(x0, i(x0)))) -> TOP(check_f(result_f(f(x0, x0)))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (39) TransformationProof (EQUIVALENT) 54.07/20.64 By rewriting [LPAR04] the rule TOP(go_up(f(x0, i(x0)))) -> TOP(check_f(result_f(f(x0, x0)))) at position [0] we obtained the following new rules [LPAR04]: 54.07/20.64 54.07/20.64 (TOP(go_up(f(x0, i(x0)))) -> TOP(go_up(f(x0, x0))),TOP(go_up(f(x0, i(x0)))) -> TOP(go_up(f(x0, x0)))) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (40) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 TOP(go_up(f(x0, i(x0)))) -> TOP(go_up(f(x0, x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (41) DependencyGraphProof (EQUIVALENT) 54.07/20.64 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (42) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (43) QDPOrderProof (EQUIVALENT) 54.07/20.64 We use the reduction pair processor [LPAR04,JAR06]. 54.07/20.64 54.07/20.64 54.07/20.64 The following pairs can be oriented strictly and are deleted. 54.07/20.64 54.07/20.64 TOP(go_up(g(x0))) -> TOP(go_up(i(x0))) 54.07/20.64 The remaining pairs can at least be oriented weakly. 54.07/20.64 Used ordering: Polynomial interpretation [POLO]: 54.07/20.64 54.07/20.64 POL(TOP(x_1)) = x_1 54.07/20.64 POL(check_f(x_1)) = 1 54.07/20.64 POL(check_g(x_1)) = 1 54.07/20.64 POL(check_h(x_1)) = 0 54.07/20.64 POL(f(x_1, x_2)) = 0 54.07/20.64 POL(g(x_1)) = 1 54.07/20.64 POL(go_up(x_1)) = x_1 54.07/20.64 POL(h(x_1, x_2)) = 0 54.07/20.64 POL(i(x_1)) = 0 54.07/20.64 POL(in_h_1(x_1, x_2)) = 0 54.07/20.64 POL(in_h_2(x_1, x_2)) = 0 54.07/20.64 POL(in_i_1(x_1)) = 0 54.07/20.64 POL(redex_f(x_1, x_2)) = x_1 54.07/20.64 POL(redex_g(x_1)) = 1 + x_1 54.07/20.64 POL(redex_h(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(reduce(x_1)) = 0 54.07/20.64 POL(result_f(x_1)) = 0 54.07/20.64 POL(result_g(x_1)) = 1 + x_1 54.07/20.64 54.07/20.64 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 54.07/20.64 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (44) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP(go_up(h(x0, x1))) -> TOP(check_h(redex_h(x0, x1))) 54.07/20.64 TOP(go_up(i(x0))) -> TOP(in_i_1(reduce(x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 54.07/20.64 reduce(g(x_1)) -> check_g(redex_g(x_1)) 54.07/20.64 reduce(h(x_1, x_2)) -> check_h(redex_h(x_1, x_2)) 54.07/20.64 reduce(i(x_1)) -> in_i_1(reduce(x_1)) 54.07/20.64 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 54.07/20.64 check_h(redex_h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 54.07/20.64 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 54.07/20.64 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 54.07/20.64 redex_g(x) -> result_g(i(x)) 54.07/20.64 check_g(result_g(x)) -> go_up(x) 54.07/20.64 redex_f(x, x) -> result_f(f(i(x), g(g(x)))) 54.07/20.64 redex_f(x, i(x)) -> result_f(f(x, x)) 54.07/20.64 check_f(result_f(x)) -> go_up(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce(f(x0, x1)) 54.07/20.64 reduce(g(x0)) 54.07/20.64 reduce(h(x0, x1)) 54.07/20.64 redex_f(x0, x1) 54.07/20.64 redex_g(x0) 54.07/20.64 redex_h(x0, x0) 54.07/20.64 check_f(result_f(x0)) 54.07/20.64 check_g(result_g(x0)) 54.07/20.64 check_h(result_h(x0)) 54.07/20.64 check_h(redex_h(x0, x1)) 54.07/20.64 reduce(i(x0)) 54.07/20.64 in_i_1(go_up(x0)) 54.07/20.64 in_h_1(go_up(x0), x1) 54.07/20.64 in_h_2(x0, go_up(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (45) SemLabProof (SOUND) 54.07/20.64 We found the following model for the rules of the TRSs R and P. 54.07/20.64 Interpretation over the domain with elements from 0 to 1. 54.07/20.64 result_f: 0 54.07/20.64 result_h: 0 54.07/20.64 reduce: 0 54.07/20.64 in_i_1: 0 54.07/20.64 in_h_2: 0 54.07/20.64 redex_f: 0 54.07/20.64 check_f: 0 54.07/20.64 TOP: 0 54.07/20.64 in_h_1: 0 54.07/20.64 g: 0 54.07/20.64 go_up: 0 54.07/20.64 result_g: 0 54.07/20.64 check_h: 0 54.07/20.64 f: 0 54.07/20.64 redex_h: 0 54.07/20.64 i: 1 54.07/20.64 h: 0 54.07/20.64 check_g: 0 54.07/20.64 redex_g: 0 54.07/20.64 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (46) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.64 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.64 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.64 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.64 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.64 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce.0(f.0-0(x_1, x_2)) -> check_f.0(redex_f.0-0(x_1, x_2)) 54.07/20.64 reduce.0(f.0-1(x_1, x_2)) -> check_f.0(redex_f.0-1(x_1, x_2)) 54.07/20.64 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 54.07/20.64 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.64 reduce.0(g.0(x_1)) -> check_g.0(redex_g.0(x_1)) 54.07/20.64 reduce.0(g.1(x_1)) -> check_g.0(redex_g.1(x_1)) 54.07/20.64 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.64 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.64 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.64 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.64 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.64 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.64 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.64 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.64 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.64 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.64 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.64 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.64 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.64 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.64 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.64 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.64 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.64 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.64 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.64 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.64 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.64 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.64 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.64 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.64 redex_g.0(x) -> result_g.1(i.0(x)) 54.07/20.64 redex_g.1(x) -> result_g.1(i.1(x)) 54.07/20.64 check_g.0(result_g.0(x)) -> go_up.0(x) 54.07/20.64 check_g.0(result_g.1(x)) -> go_up.1(x) 54.07/20.64 redex_f.0-0(x, x) -> result_f.0(f.1-0(i.0(x), g.0(g.0(x)))) 54.07/20.64 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.64 redex_f.0-1(x, i.0(x)) -> result_f.0(f.0-0(x, x)) 54.07/20.64 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.64 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.64 check_f.0(result_f.1(x)) -> go_up.1(x) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce.0(f.0-0(x0, x1)) 54.07/20.64 reduce.0(f.0-1(x0, x1)) 54.07/20.64 reduce.0(f.1-0(x0, x1)) 54.07/20.64 reduce.0(f.1-1(x0, x1)) 54.07/20.64 reduce.0(g.0(x0)) 54.07/20.64 reduce.0(g.1(x0)) 54.07/20.64 reduce.0(h.0-0(x0, x1)) 54.07/20.64 reduce.0(h.0-1(x0, x1)) 54.07/20.64 reduce.0(h.1-0(x0, x1)) 54.07/20.64 reduce.0(h.1-1(x0, x1)) 54.07/20.64 redex_f.0-0(x0, x1) 54.07/20.64 redex_f.0-1(x0, x1) 54.07/20.64 redex_f.1-0(x0, x1) 54.07/20.64 redex_f.1-1(x0, x1) 54.07/20.64 redex_g.0(x0) 54.07/20.64 redex_g.1(x0) 54.07/20.64 redex_h.0-0(x0, x0) 54.07/20.64 redex_h.1-1(x0, x0) 54.07/20.64 check_f.0(result_f.0(x0)) 54.07/20.64 check_f.0(result_f.1(x0)) 54.07/20.64 check_g.0(result_g.0(x0)) 54.07/20.64 check_g.0(result_g.1(x0)) 54.07/20.64 check_h.0(result_h.0(x0)) 54.07/20.64 check_h.0(result_h.1(x0)) 54.07/20.64 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.64 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.64 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.64 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.64 reduce.1(i.0(x0)) 54.07/20.64 reduce.1(i.1(x0)) 54.07/20.64 in_i_1.0(go_up.0(x0)) 54.07/20.64 in_i_1.0(go_up.1(x0)) 54.07/20.64 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.64 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.64 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.64 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.64 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.64 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.64 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.64 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (47) UsableRulesReductionPairsProof (EQUIVALENT) 54.07/20.64 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. 54.07/20.64 54.07/20.64 No dependency pairs are removed. 54.07/20.64 54.07/20.64 The following rules are removed from R: 54.07/20.64 54.07/20.64 reduce.0(f.0-1(x_1, x_2)) -> check_f.0(redex_f.0-1(x_1, x_2)) 54.07/20.64 redex_g.1(x) -> result_g.1(i.1(x)) 54.07/20.64 check_g.0(result_g.0(x)) -> go_up.0(x) 54.07/20.64 redex_f.0-0(x, x) -> result_f.0(f.1-0(i.0(x), g.0(g.0(x)))) 54.07/20.64 check_f.0(result_f.1(x)) -> go_up.1(x) 54.07/20.64 Used ordering: POLO with Polynomial interpretation [POLO]: 54.07/20.64 54.07/20.64 POL(TOP.0(x_1)) = x_1 54.07/20.64 POL(check_f.0(x_1)) = x_1 54.07/20.64 POL(check_g.0(x_1)) = x_1 54.07/20.64 POL(check_h.0(x_1)) = x_1 54.07/20.64 POL(f.0-0(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(f.0-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(g.0(x_1)) = x_1 54.07/20.64 POL(g.1(x_1)) = 1 + x_1 54.07/20.64 POL(go_up.0(x_1)) = x_1 54.07/20.64 POL(go_up.1(x_1)) = x_1 54.07/20.64 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(i.0(x_1)) = x_1 54.07/20.64 POL(i.1(x_1)) = x_1 54.07/20.64 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_i_1.0(x_1)) = x_1 54.07/20.64 POL(redex_f.0-0(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(redex_f.0-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(redex_f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(redex_g.0(x_1)) = x_1 54.07/20.64 POL(redex_g.1(x_1)) = 1 + x_1 54.07/20.64 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(reduce.0(x_1)) = x_1 54.07/20.64 POL(reduce.1(x_1)) = x_1 54.07/20.64 POL(result_f.0(x_1)) = x_1 54.07/20.64 POL(result_f.1(x_1)) = x_1 54.07/20.64 POL(result_g.0(x_1)) = x_1 54.07/20.64 POL(result_g.1(x_1)) = x_1 54.07/20.64 54.07/20.64 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (48) 54.07/20.64 Obligation: 54.07/20.64 Q DP problem: 54.07/20.64 The TRS P consists of the following rules: 54.07/20.64 54.07/20.64 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.64 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.64 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.64 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.64 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.64 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.64 54.07/20.64 The TRS R consists of the following rules: 54.07/20.64 54.07/20.64 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.64 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.64 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.64 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.64 reduce.0(f.0-0(x_1, x_2)) -> check_f.0(redex_f.0-0(x_1, x_2)) 54.07/20.64 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 54.07/20.64 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.64 reduce.0(g.0(x_1)) -> check_g.0(redex_g.0(x_1)) 54.07/20.64 reduce.0(g.1(x_1)) -> check_g.0(redex_g.1(x_1)) 54.07/20.64 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.64 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.64 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.64 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.64 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.64 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.64 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.64 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.64 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.64 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.64 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.64 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.64 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.64 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.64 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.64 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.64 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.64 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.64 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.64 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.64 check_g.0(result_g.1(x)) -> go_up.1(x) 54.07/20.64 redex_g.0(x) -> result_g.1(i.0(x)) 54.07/20.64 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.64 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.64 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.64 redex_f.0-1(x, i.0(x)) -> result_f.0(f.0-0(x, x)) 54.07/20.64 54.07/20.64 The set Q consists of the following terms: 54.07/20.64 54.07/20.64 reduce.0(f.0-0(x0, x1)) 54.07/20.64 reduce.0(f.0-1(x0, x1)) 54.07/20.64 reduce.0(f.1-0(x0, x1)) 54.07/20.64 reduce.0(f.1-1(x0, x1)) 54.07/20.64 reduce.0(g.0(x0)) 54.07/20.64 reduce.0(g.1(x0)) 54.07/20.64 reduce.0(h.0-0(x0, x1)) 54.07/20.64 reduce.0(h.0-1(x0, x1)) 54.07/20.64 reduce.0(h.1-0(x0, x1)) 54.07/20.64 reduce.0(h.1-1(x0, x1)) 54.07/20.64 redex_f.0-0(x0, x1) 54.07/20.64 redex_f.0-1(x0, x1) 54.07/20.64 redex_f.1-0(x0, x1) 54.07/20.64 redex_f.1-1(x0, x1) 54.07/20.64 redex_g.0(x0) 54.07/20.64 redex_g.1(x0) 54.07/20.64 redex_h.0-0(x0, x0) 54.07/20.64 redex_h.1-1(x0, x0) 54.07/20.64 check_f.0(result_f.0(x0)) 54.07/20.64 check_f.0(result_f.1(x0)) 54.07/20.64 check_g.0(result_g.0(x0)) 54.07/20.64 check_g.0(result_g.1(x0)) 54.07/20.64 check_h.0(result_h.0(x0)) 54.07/20.64 check_h.0(result_h.1(x0)) 54.07/20.64 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.64 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.64 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.64 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.64 reduce.1(i.0(x0)) 54.07/20.64 reduce.1(i.1(x0)) 54.07/20.64 in_i_1.0(go_up.0(x0)) 54.07/20.64 in_i_1.0(go_up.1(x0)) 54.07/20.64 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.64 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.64 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.64 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.64 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.64 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.64 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.64 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.64 54.07/20.64 We have to consider all minimal (P,Q,R)-chains. 54.07/20.64 ---------------------------------------- 54.07/20.64 54.07/20.64 (49) UsableRulesReductionPairsProof (EQUIVALENT) 54.07/20.64 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. 54.07/20.64 54.07/20.64 No dependency pairs are removed. 54.07/20.64 54.07/20.64 The following rules are removed from R: 54.07/20.64 54.07/20.64 reduce.0(f.0-0(x_1, x_2)) -> check_f.0(redex_f.0-0(x_1, x_2)) 54.07/20.64 check_g.0(result_g.1(x)) -> go_up.1(x) 54.07/20.64 redex_f.0-1(x, i.0(x)) -> result_f.0(f.0-0(x, x)) 54.07/20.64 Used ordering: POLO with Polynomial interpretation [POLO]: 54.07/20.64 54.07/20.64 POL(TOP.0(x_1)) = x_1 54.07/20.64 POL(check_f.0(x_1)) = x_1 54.07/20.64 POL(check_g.0(x_1)) = x_1 54.07/20.64 POL(check_h.0(x_1)) = x_1 54.07/20.64 POL(f.0-0(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(g.0(x_1)) = 1 + x_1 54.07/20.64 POL(g.1(x_1)) = x_1 54.07/20.64 POL(go_up.0(x_1)) = x_1 54.07/20.64 POL(go_up.1(x_1)) = x_1 54.07/20.64 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(i.0(x_1)) = x_1 54.07/20.64 POL(i.1(x_1)) = x_1 54.07/20.64 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(in_i_1.0(x_1)) = x_1 54.07/20.64 POL(redex_f.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.64 POL(redex_g.0(x_1)) = 1 + x_1 54.07/20.64 POL(redex_g.1(x_1)) = x_1 54.07/20.64 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.64 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 POL(result_f.0(x_1)) = x_1 54.07/20.65 POL(result_g.1(x_1)) = 1 + x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (50) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 54.07/20.65 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.65 reduce.0(g.0(x_1)) -> check_g.0(redex_g.0(x_1)) 54.07/20.65 reduce.0(g.1(x_1)) -> check_g.0(redex_g.1(x_1)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 redex_g.0(x) -> result_g.1(i.0(x)) 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.65 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (51) MRRProof (EQUIVALENT) 54.07/20.65 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 54.07/20.65 54.07/20.65 54.07/20.65 Strictly oriented rules of the TRS R: 54.07/20.65 54.07/20.65 reduce.0(g.1(x_1)) -> check_g.0(redex_g.1(x_1)) 54.07/20.65 54.07/20.65 Used ordering: Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_f.0(x_1)) = x_1 54.07/20.65 POL(check_g.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(g.0(x_1)) = x_1 54.07/20.65 POL(g.1(x_1)) = 1 + x_1 54.07/20.65 POL(go_up.0(x_1)) = x_1 54.07/20.65 POL(go_up.1(x_1)) = x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = x_1 54.07/20.65 POL(i.1(x_1)) = x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = x_1 54.07/20.65 POL(redex_f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(redex_g.0(x_1)) = x_1 54.07/20.65 POL(redex_g.1(x_1)) = x_1 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 POL(result_f.0(x_1)) = x_1 54.07/20.65 POL(result_g.1(x_1)) = x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (52) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 54.07/20.65 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.65 reduce.0(g.0(x_1)) -> check_g.0(redex_g.0(x_1)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 redex_g.0(x) -> result_g.1(i.0(x)) 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.65 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (53) MRRProof (EQUIVALENT) 54.07/20.65 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 54.07/20.65 54.07/20.65 54.07/20.65 Strictly oriented rules of the TRS R: 54.07/20.65 54.07/20.65 reduce.0(g.0(x_1)) -> check_g.0(redex_g.0(x_1)) 54.07/20.65 54.07/20.65 Used ordering: Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_f.0(x_1)) = x_1 54.07/20.65 POL(check_g.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(g.0(x_1)) = 1 + x_1 54.07/20.65 POL(g.1(x_1)) = x_1 54.07/20.65 POL(go_up.0(x_1)) = x_1 54.07/20.65 POL(go_up.1(x_1)) = x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = x_1 54.07/20.65 POL(i.1(x_1)) = x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = x_1 54.07/20.65 POL(redex_f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(redex_g.0(x_1)) = x_1 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 POL(result_f.0(x_1)) = x_1 54.07/20.65 POL(result_g.1(x_1)) = x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (54) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 54.07/20.65 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 redex_g.0(x) -> result_g.1(i.0(x)) 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.65 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (55) UsableRulesReductionPairsProof (EQUIVALENT) 54.07/20.65 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. 54.07/20.65 54.07/20.65 No dependency pairs are removed. 54.07/20.65 54.07/20.65 The following rules are removed from R: 54.07/20.65 54.07/20.65 reduce.0(f.1-0(x_1, x_2)) -> check_f.0(redex_f.1-0(x_1, x_2)) 54.07/20.65 redex_g.0(x) -> result_g.1(i.0(x)) 54.07/20.65 Used ordering: POLO with Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_f.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(f.1-0(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(g.0(x_1)) = x_1 54.07/20.65 POL(g.1(x_1)) = x_1 54.07/20.65 POL(go_up.0(x_1)) = x_1 54.07/20.65 POL(go_up.1(x_1)) = x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = x_1 54.07/20.65 POL(i.1(x_1)) = x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = x_1 54.07/20.65 POL(redex_f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 POL(result_f.0(x_1)) = x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (56) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.65 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (57) MRRProof (EQUIVALENT) 54.07/20.65 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 54.07/20.65 54.07/20.65 54.07/20.65 Strictly oriented rules of the TRS R: 54.07/20.65 54.07/20.65 redex_f.1-1(x, i.1(x)) -> result_f.0(f.1-1(x, x)) 54.07/20.65 54.07/20.65 Used ordering: Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_f.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(g.0(x_1)) = x_1 54.07/20.65 POL(g.1(x_1)) = x_1 54.07/20.65 POL(go_up.0(x_1)) = x_1 54.07/20.65 POL(go_up.1(x_1)) = x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = 1 + x_1 54.07/20.65 POL(i.1(x_1)) = 1 + x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = 1 + x_1 54.07/20.65 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 POL(result_f.0(x_1)) = x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (58) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (59) UsableRulesReductionPairsProof (EQUIVALENT) 54.07/20.65 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. 54.07/20.65 54.07/20.65 No dependency pairs are removed. 54.07/20.65 54.07/20.65 The following rules are removed from R: 54.07/20.65 54.07/20.65 reduce.0(f.1-1(x_1, x_2)) -> check_f.0(redex_f.1-1(x_1, x_2)) 54.07/20.65 check_f.0(result_f.0(x)) -> go_up.0(x) 54.07/20.65 Used ordering: POLO with Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_f.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(f.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(g.0(x_1)) = x_1 54.07/20.65 POL(g.1(x_1)) = x_1 54.07/20.65 POL(go_up.0(x_1)) = x_1 54.07/20.65 POL(go_up.1(x_1)) = x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = x_1 54.07/20.65 POL(i.1(x_1)) = x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = x_1 54.07/20.65 POL(redex_f.1-1(x_1, x_2)) = 1 + x_1 + x_2 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 POL(result_f.0(x_1)) = 1 + x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (60) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (61) UsableRulesReductionPairsProof (EQUIVALENT) 54.07/20.65 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. 54.07/20.65 54.07/20.65 No dependency pairs are removed. 54.07/20.65 54.07/20.65 The following rules are removed from R: 54.07/20.65 54.07/20.65 redex_f.1-1(x, x) -> result_f.0(f.1-0(i.1(x), g.0(g.1(x)))) 54.07/20.65 Used ordering: POLO with Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(go_up.0(x_1)) = x_1 54.07/20.65 POL(go_up.1(x_1)) = x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = x_1 54.07/20.65 POL(i.1(x_1)) = x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = x_1 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (62) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 The TRS P consists of the following rules: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (63) MRRProof (EQUIVALENT) 54.07/20.65 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 54.07/20.65 54.07/20.65 Strictly oriented dependency pairs: 54.07/20.65 54.07/20.65 TOP.0(go_up.0(h.0-0(x0, x1))) -> TOP.0(check_h.0(redex_h.0-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.0-1(x0, x1))) -> TOP.0(check_h.0(redex_h.0-1(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-0(x0, x1))) -> TOP.0(check_h.0(redex_h.1-0(x0, x1))) 54.07/20.65 TOP.0(go_up.0(h.1-1(x0, x1))) -> TOP.0(check_h.0(redex_h.1-1(x0, x1))) 54.07/20.65 TOP.0(go_up.1(i.0(x0))) -> TOP.0(in_i_1.0(reduce.0(x0))) 54.07/20.65 TOP.0(go_up.1(i.1(x0))) -> TOP.0(in_i_1.0(reduce.1(x0))) 54.07/20.65 54.07/20.65 54.07/20.65 Used ordering: Polynomial interpretation [POLO]: 54.07/20.65 54.07/20.65 POL(TOP.0(x_1)) = x_1 54.07/20.65 POL(check_h.0(x_1)) = x_1 54.07/20.65 POL(go_up.0(x_1)) = 1 + x_1 54.07/20.65 POL(go_up.1(x_1)) = 1 + x_1 54.07/20.65 POL(h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(i.0(x_1)) = x_1 54.07/20.65 POL(i.1(x_1)) = x_1 54.07/20.65 POL(in_h_1.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_1.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_h_2.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(in_i_1.0(x_1)) = x_1 54.07/20.65 POL(redex_h.0-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.0-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-0(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(redex_h.1-1(x_1, x_2)) = x_1 + x_2 54.07/20.65 POL(reduce.0(x_1)) = x_1 54.07/20.65 POL(reduce.1(x_1)) = x_1 54.07/20.65 54.07/20.65 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (64) 54.07/20.65 Obligation: 54.07/20.65 Q DP problem: 54.07/20.65 P is empty. 54.07/20.65 The TRS R consists of the following rules: 54.07/20.65 54.07/20.65 reduce.1(i.0(x_1)) -> in_i_1.0(reduce.0(x_1)) 54.07/20.65 reduce.1(i.1(x_1)) -> in_i_1.0(reduce.1(x_1)) 54.07/20.65 in_i_1.0(go_up.0(x_1)) -> go_up.1(i.0(x_1)) 54.07/20.65 in_i_1.0(go_up.1(x_1)) -> go_up.1(i.1(x_1)) 54.07/20.65 reduce.0(h.0-0(x_1, x_2)) -> check_h.0(redex_h.0-0(x_1, x_2)) 54.07/20.65 reduce.0(h.0-1(x_1, x_2)) -> check_h.0(redex_h.0-1(x_1, x_2)) 54.07/20.65 reduce.0(h.1-0(x_1, x_2)) -> check_h.0(redex_h.1-0(x_1, x_2)) 54.07/20.65 reduce.0(h.1-1(x_1, x_2)) -> check_h.0(redex_h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_1.0-1(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-1(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.0(x_2)) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 in_h_2.1-0(x_1, go_up.1(x_2)) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.0(x_1), x_2) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 in_h_1.0-1(go_up.1(x_1), x_2) -> go_up.0(h.1-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_1.0-0(reduce.1(x_1), x_2) 54.07/20.65 check_h.0(redex_h.1-0(x_1, x_2)) -> in_h_2.1-0(x_1, reduce.0(x_2)) 54.07/20.65 in_h_1.0-0(go_up.0(x_1), x_2) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_1.0-0(go_up.1(x_1), x_2) -> go_up.0(h.1-0(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_1.0-1(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-1(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.1(x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.0(x_2)) -> go_up.0(h.0-0(x_1, x_2)) 54.07/20.65 in_h_2.0-0(x_1, go_up.1(x_2)) -> go_up.0(h.0-1(x_1, x_2)) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_1.0-0(reduce.0(x_1), x_2) 54.07/20.65 check_h.0(redex_h.0-0(x_1, x_2)) -> in_h_2.0-0(x_1, reduce.0(x_2)) 54.07/20.65 54.07/20.65 The set Q consists of the following terms: 54.07/20.65 54.07/20.65 reduce.0(f.0-0(x0, x1)) 54.07/20.65 reduce.0(f.0-1(x0, x1)) 54.07/20.65 reduce.0(f.1-0(x0, x1)) 54.07/20.65 reduce.0(f.1-1(x0, x1)) 54.07/20.65 reduce.0(g.0(x0)) 54.07/20.65 reduce.0(g.1(x0)) 54.07/20.65 reduce.0(h.0-0(x0, x1)) 54.07/20.65 reduce.0(h.0-1(x0, x1)) 54.07/20.65 reduce.0(h.1-0(x0, x1)) 54.07/20.65 reduce.0(h.1-1(x0, x1)) 54.07/20.65 redex_f.0-0(x0, x1) 54.07/20.65 redex_f.0-1(x0, x1) 54.07/20.65 redex_f.1-0(x0, x1) 54.07/20.65 redex_f.1-1(x0, x1) 54.07/20.65 redex_g.0(x0) 54.07/20.65 redex_g.1(x0) 54.07/20.65 redex_h.0-0(x0, x0) 54.07/20.65 redex_h.1-1(x0, x0) 54.07/20.65 check_f.0(result_f.0(x0)) 54.07/20.65 check_f.0(result_f.1(x0)) 54.07/20.65 check_g.0(result_g.0(x0)) 54.07/20.65 check_g.0(result_g.1(x0)) 54.07/20.65 check_h.0(result_h.0(x0)) 54.07/20.65 check_h.0(result_h.1(x0)) 54.07/20.65 check_h.0(redex_h.0-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.0-1(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-0(x0, x1)) 54.07/20.65 check_h.0(redex_h.1-1(x0, x1)) 54.07/20.65 reduce.1(i.0(x0)) 54.07/20.65 reduce.1(i.1(x0)) 54.07/20.65 in_i_1.0(go_up.0(x0)) 54.07/20.65 in_i_1.0(go_up.1(x0)) 54.07/20.65 in_h_1.0-0(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.0(x0), x1) 54.07/20.65 in_h_1.0-0(go_up.1(x0), x1) 54.07/20.65 in_h_1.0-1(go_up.1(x0), x1) 54.07/20.65 in_h_2.0-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.0-0(x0, go_up.1(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.0(x1)) 54.07/20.65 in_h_2.1-0(x0, go_up.1(x1)) 54.07/20.65 54.07/20.65 We have to consider all minimal (P,Q,R)-chains. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (65) PisEmptyProof (EQUIVALENT) 54.07/20.65 The TRS P is empty. Hence, there is no (P,Q,R) chain. 54.07/20.65 ---------------------------------------- 54.07/20.65 54.07/20.65 (66) 54.07/20.65 YES 54.21/20.72 EOF