197.47/71.50 MAYBE 197.56/71.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 197.56/71.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 197.56/71.51 197.56/71.51 197.56/71.51 Outermost Termination of the given OTRS could not be shown: 197.56/71.51 197.56/71.51 (0) OTRS 197.56/71.51 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 197.56/71.51 (2) QTRS 197.56/71.51 (3) DependencyPairsProof [EQUIVALENT, 6 ms] 197.56/71.51 (4) QDP 197.56/71.51 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 197.56/71.51 (6) AND 197.56/71.51 (7) QDP 197.56/71.51 (8) UsableRulesProof [EQUIVALENT, 0 ms] 197.56/71.51 (9) QDP 197.56/71.51 (10) QReductionProof [EQUIVALENT, 0 ms] 197.56/71.51 (11) QDP 197.56/71.51 (12) UsableRulesReductionPairsProof [EQUIVALENT, 13 ms] 197.56/71.51 (13) QDP 197.56/71.51 (14) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 197.56/71.51 (15) QDP 197.56/71.51 (16) DependencyGraphProof [EQUIVALENT, 0 ms] 197.56/71.51 (17) TRUE 197.56/71.51 (18) QDP 197.56/71.51 (19) UsableRulesProof [EQUIVALENT, 0 ms] 197.56/71.51 (20) QDP 197.56/71.51 (21) QReductionProof [EQUIVALENT, 0 ms] 197.56/71.51 (22) QDP 197.56/71.51 (23) TransformationProof [EQUIVALENT, 0 ms] 197.56/71.51 (24) QDP 197.56/71.51 (25) TransformationProof [EQUIVALENT, 0 ms] 197.56/71.51 (26) QDP 197.56/71.51 (27) TransformationProof [EQUIVALENT, 0 ms] 197.56/71.51 (28) QDP 197.56/71.51 (29) TransformationProof [EQUIVALENT, 0 ms] 197.56/71.51 (30) QDP 197.56/71.51 (31) TransformationProof [EQUIVALENT, 0 ms] 197.56/71.51 (32) QDP 197.56/71.51 (33) QDPOrderProof [EQUIVALENT, 121 ms] 197.56/71.51 (34) QDP 197.56/71.51 (35) QDPOrderProof [EQUIVALENT, 78 ms] 197.56/71.51 (36) QDP 197.56/71.51 (37) UsableRulesProof [EQUIVALENT, 0 ms] 197.56/71.51 (38) QDP 197.56/71.51 (39) QReductionProof [EQUIVALENT, 0 ms] 197.56/71.51 (40) QDP 197.56/71.51 (41) Trivial-Transformation [SOUND, 0 ms] 197.56/71.51 (42) QTRS 197.56/71.51 (43) DependencyPairsProof [EQUIVALENT, 0 ms] 197.56/71.51 (44) QDP 197.56/71.51 (45) DependencyGraphProof [EQUIVALENT, 0 ms] 197.56/71.51 (46) QDP 197.56/71.51 (47) NonTerminationLoopProof [COMPLETE, 0 ms] 197.56/71.51 (48) NO 197.56/71.51 (49) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 197.56/71.51 (50) QTRS 197.56/71.51 (51) DependencyPairsProof [EQUIVALENT, 30 ms] 197.56/71.51 (52) QDP 197.56/71.51 (53) DependencyGraphProof [EQUIVALENT, 0 ms] 197.56/71.51 (54) AND 197.56/71.51 (55) QDP 197.56/71.51 (56) UsableRulesProof [EQUIVALENT, 0 ms] 197.56/71.51 (57) QDP 197.56/71.51 (58) QDPSizeChangeProof [EQUIVALENT, 0 ms] 197.56/71.51 (59) YES 197.56/71.51 (60) QDP 197.56/71.51 (61) TransformationProof [EQUIVALENT, 0 ms] 197.56/71.51 (62) QDP 197.56/71.51 (63) DependencyGraphProof [EQUIVALENT, 0 ms] 197.56/71.51 (64) QDP 197.56/71.51 (65) QDPOrderProof [EQUIVALENT, 46 ms] 197.56/71.51 (66) QDP 197.56/71.51 (67) DependencyGraphProof [EQUIVALENT, 0 ms] 197.56/71.51 (68) QDP 197.56/71.51 (69) QDPOrderProof [EQUIVALENT, 1072 ms] 197.56/71.51 (70) QDP 197.56/71.51 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (0) 197.56/71.51 Obligation: 197.56/71.51 Term rewrite system R: 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 f(h(x), c) -> f(i(x), s(x)) 197.56/71.51 h(x) -> f(h(x), c) 197.56/71.51 i(x) -> h(x) 197.56/71.51 f(i(x), y) -> x 197.56/71.51 197.56/71.51 197.56/71.51 197.56/71.51 Outermost Strategy. 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 197.56/71.51 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (2) 197.56/71.51 Obligation: 197.56/71.51 Q restricted rewrite system: 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 top(go_up(x)) -> top(reduce(x)) 197.56/71.51 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.51 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.51 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.51 redex_i(x) -> result_i(h(x)) 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 check_f(result_f(x)) -> go_up(x) 197.56/71.51 check_h(result_h(x)) -> go_up(x) 197.56/71.51 check_i(result_i(x)) -> go_up(x) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.51 check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) 197.56/71.51 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 197.56/71.51 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.51 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.51 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.51 in_h_1(go_up(x_1)) -> go_up(h(x_1)) 197.56/71.51 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 197.56/71.51 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 top(go_up(x0)) 197.56/71.51 reduce(f(x0, x1)) 197.56/71.51 reduce(h(x0)) 197.56/71.51 reduce(i(x0)) 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_h(x0) 197.56/71.51 redex_i(x0) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 check_f(result_f(x0)) 197.56/71.51 check_h(result_h(x0)) 197.56/71.51 check_i(result_i(x0)) 197.56/71.51 check_f(redex_f(x0, x1)) 197.56/71.51 reduce(s(x0)) 197.56/71.51 in_f_1(go_up(x0), x1) 197.56/71.51 in_f_2(x0, go_up(x1)) 197.56/71.51 in_h_1(go_up(x0)) 197.56/71.51 in_i_1(go_up(x0)) 197.56/71.51 in_s_1(go_up(x0)) 197.56/71.51 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (3) DependencyPairsProof (EQUIVALENT) 197.56/71.51 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (4) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 TOP(go_up(x)) -> TOP(reduce(x)) 197.56/71.51 TOP(go_up(x)) -> REDUCE(x) 197.56/71.51 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 197.56/71.51 REDUCE(f(x_1, x_2)) -> REDEX_F(x_1, x_2) 197.56/71.51 REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) 197.56/71.51 REDUCE(h(x_1)) -> REDEX_H(x_1) 197.56/71.51 REDUCE(i(x_1)) -> CHECK_I(redex_i(x_1)) 197.56/71.51 REDUCE(i(x_1)) -> REDEX_I(x_1) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> IN_F_1(reduce(x_1), x_2) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> IN_F_2(x_1, reduce(x_2)) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 197.56/71.51 CHECK_H(redex_h(x_1)) -> IN_H_1(reduce(x_1)) 197.56/71.51 CHECK_H(redex_h(x_1)) -> REDUCE(x_1) 197.56/71.51 CHECK_I(redex_i(x_1)) -> IN_I_1(reduce(x_1)) 197.56/71.51 CHECK_I(redex_i(x_1)) -> REDUCE(x_1) 197.56/71.51 REDUCE(s(x_1)) -> IN_S_1(reduce(x_1)) 197.56/71.51 REDUCE(s(x_1)) -> REDUCE(x_1) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 top(go_up(x)) -> top(reduce(x)) 197.56/71.51 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.51 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.51 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.51 redex_i(x) -> result_i(h(x)) 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 check_f(result_f(x)) -> go_up(x) 197.56/71.51 check_h(result_h(x)) -> go_up(x) 197.56/71.51 check_i(result_i(x)) -> go_up(x) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.51 check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) 197.56/71.51 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 197.56/71.51 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.51 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.51 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.51 in_h_1(go_up(x_1)) -> go_up(h(x_1)) 197.56/71.51 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 197.56/71.51 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 top(go_up(x0)) 197.56/71.51 reduce(f(x0, x1)) 197.56/71.51 reduce(h(x0)) 197.56/71.51 reduce(i(x0)) 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_h(x0) 197.56/71.51 redex_i(x0) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 check_f(result_f(x0)) 197.56/71.51 check_h(result_h(x0)) 197.56/71.51 check_i(result_i(x0)) 197.56/71.51 check_f(redex_f(x0, x1)) 197.56/71.51 reduce(s(x0)) 197.56/71.51 in_f_1(go_up(x0), x1) 197.56/71.51 in_f_2(x0, go_up(x1)) 197.56/71.51 in_h_1(go_up(x0)) 197.56/71.51 in_i_1(go_up(x0)) 197.56/71.51 in_s_1(go_up(x0)) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (5) DependencyGraphProof (EQUIVALENT) 197.56/71.51 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 13 less nodes. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (6) 197.56/71.51 Complex Obligation (AND) 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (7) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 197.56/71.51 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 197.56/71.51 REDUCE(s(x_1)) -> REDUCE(x_1) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 top(go_up(x)) -> top(reduce(x)) 197.56/71.51 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.51 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.51 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.51 redex_i(x) -> result_i(h(x)) 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 check_f(result_f(x)) -> go_up(x) 197.56/71.51 check_h(result_h(x)) -> go_up(x) 197.56/71.51 check_i(result_i(x)) -> go_up(x) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.51 check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) 197.56/71.51 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 197.56/71.51 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.51 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.51 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.51 in_h_1(go_up(x_1)) -> go_up(h(x_1)) 197.56/71.51 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 197.56/71.51 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 top(go_up(x0)) 197.56/71.51 reduce(f(x0, x1)) 197.56/71.51 reduce(h(x0)) 197.56/71.51 reduce(i(x0)) 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_h(x0) 197.56/71.51 redex_i(x0) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 check_f(result_f(x0)) 197.56/71.51 check_h(result_h(x0)) 197.56/71.51 check_i(result_i(x0)) 197.56/71.51 check_f(redex_f(x0, x1)) 197.56/71.51 reduce(s(x0)) 197.56/71.51 in_f_1(go_up(x0), x1) 197.56/71.51 in_f_2(x0, go_up(x1)) 197.56/71.51 in_h_1(go_up(x0)) 197.56/71.51 in_i_1(go_up(x0)) 197.56/71.51 in_s_1(go_up(x0)) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (8) UsableRulesProof (EQUIVALENT) 197.56/71.51 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. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (9) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 197.56/71.51 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 197.56/71.51 REDUCE(s(x_1)) -> REDUCE(x_1) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 top(go_up(x0)) 197.56/71.51 reduce(f(x0, x1)) 197.56/71.51 reduce(h(x0)) 197.56/71.51 reduce(i(x0)) 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_h(x0) 197.56/71.51 redex_i(x0) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 check_f(result_f(x0)) 197.56/71.51 check_h(result_h(x0)) 197.56/71.51 check_i(result_i(x0)) 197.56/71.51 check_f(redex_f(x0, x1)) 197.56/71.51 reduce(s(x0)) 197.56/71.51 in_f_1(go_up(x0), x1) 197.56/71.51 in_f_2(x0, go_up(x1)) 197.56/71.51 in_h_1(go_up(x0)) 197.56/71.51 in_i_1(go_up(x0)) 197.56/71.51 in_s_1(go_up(x0)) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (10) QReductionProof (EQUIVALENT) 197.56/71.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 197.56/71.51 197.56/71.51 top(go_up(x0)) 197.56/71.51 reduce(f(x0, x1)) 197.56/71.51 reduce(h(x0)) 197.56/71.51 reduce(i(x0)) 197.56/71.51 redex_h(x0) 197.56/71.51 redex_i(x0) 197.56/71.51 check_f(result_f(x0)) 197.56/71.51 check_h(result_h(x0)) 197.56/71.51 check_i(result_i(x0)) 197.56/71.51 check_f(redex_f(x0, x1)) 197.56/71.51 reduce(s(x0)) 197.56/71.51 in_f_1(go_up(x0), x1) 197.56/71.51 in_f_2(x0, go_up(x1)) 197.56/71.51 in_h_1(go_up(x0)) 197.56/71.51 in_i_1(go_up(x0)) 197.56/71.51 in_s_1(go_up(x0)) 197.56/71.51 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (11) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 197.56/71.51 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 197.56/71.51 REDUCE(s(x_1)) -> REDUCE(x_1) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (12) UsableRulesReductionPairsProof (EQUIVALENT) 197.56/71.51 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. 197.56/71.51 197.56/71.51 No dependency pairs are removed. 197.56/71.51 197.56/71.51 The following rules are removed from R: 197.56/71.51 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 Used ordering: POLO with Polynomial interpretation [POLO]: 197.56/71.51 197.56/71.51 POL(CHECK_F(x_1)) = 2*x_1 197.56/71.51 POL(REDUCE(x_1)) = 2*x_1 197.56/71.51 POL(c) = 2 197.56/71.51 POL(f(x_1, x_2)) = 2*x_1 + 2*x_2 197.56/71.51 POL(h(x_1)) = 2 + 2*x_1 197.56/71.51 POL(i(x_1)) = x_1 197.56/71.51 POL(redex_f(x_1, x_2)) = 2*x_1 + x_2 197.56/71.51 POL(result_f(x_1)) = x_1 197.56/71.51 POL(s(x_1)) = x_1 197.56/71.51 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (13) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 197.56/71.51 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 197.56/71.51 REDUCE(s(x_1)) -> REDUCE(x_1) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (14) UsableRulesReductionPairsProof (EQUIVALENT) 197.56/71.51 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. 197.56/71.51 197.56/71.51 The following dependency pairs can be deleted: 197.56/71.51 197.56/71.51 REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) 197.56/71.51 REDUCE(s(x_1)) -> REDUCE(x_1) 197.56/71.51 The following rules are removed from R: 197.56/71.51 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 Used ordering: POLO with Polynomial interpretation [POLO]: 197.56/71.51 197.56/71.51 POL(CHECK_F(x_1)) = 2*x_1 197.56/71.51 POL(REDUCE(x_1)) = 2*x_1 197.56/71.51 POL(f(x_1, x_2)) = 2*x_1 + 2*x_2 197.56/71.51 POL(i(x_1)) = 1 + x_1 197.56/71.51 POL(redex_f(x_1, x_2)) = 2*x_1 + x_2 197.56/71.51 POL(result_f(x_1)) = 2 + 2*x_1 197.56/71.51 POL(s(x_1)) = 2*x_1 197.56/71.51 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (15) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) 197.56/71.51 CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) 197.56/71.51 197.56/71.51 R is empty. 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (16) DependencyGraphProof (EQUIVALENT) 197.56/71.51 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (17) 197.56/71.51 TRUE 197.56/71.51 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (18) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 TOP(go_up(x)) -> TOP(reduce(x)) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 top(go_up(x)) -> top(reduce(x)) 197.56/71.51 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.51 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.51 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.51 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.51 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.51 redex_i(x) -> result_i(h(x)) 197.56/71.51 redex_f(i(x), y) -> result_f(x) 197.56/71.51 check_f(result_f(x)) -> go_up(x) 197.56/71.51 check_h(result_h(x)) -> go_up(x) 197.56/71.51 check_i(result_i(x)) -> go_up(x) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.51 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.51 check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) 197.56/71.51 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 197.56/71.51 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.51 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.51 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.51 in_h_1(go_up(x_1)) -> go_up(h(x_1)) 197.56/71.51 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 197.56/71.51 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.51 197.56/71.51 The set Q consists of the following terms: 197.56/71.51 197.56/71.51 top(go_up(x0)) 197.56/71.51 reduce(f(x0, x1)) 197.56/71.51 reduce(h(x0)) 197.56/71.51 reduce(i(x0)) 197.56/71.51 redex_f(h(x0), c) 197.56/71.51 redex_h(x0) 197.56/71.51 redex_i(x0) 197.56/71.51 redex_f(i(x0), x1) 197.56/71.51 check_f(result_f(x0)) 197.56/71.51 check_h(result_h(x0)) 197.56/71.51 check_i(result_i(x0)) 197.56/71.51 check_f(redex_f(x0, x1)) 197.56/71.51 reduce(s(x0)) 197.56/71.51 in_f_1(go_up(x0), x1) 197.56/71.51 in_f_2(x0, go_up(x1)) 197.56/71.51 in_h_1(go_up(x0)) 197.56/71.51 in_i_1(go_up(x0)) 197.56/71.51 in_s_1(go_up(x0)) 197.56/71.51 197.56/71.51 We have to consider all minimal (P,Q,R)-chains. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (19) UsableRulesProof (EQUIVALENT) 197.56/71.51 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. 197.56/71.51 ---------------------------------------- 197.56/71.51 197.56/71.51 (20) 197.56/71.51 Obligation: 197.56/71.51 Q DP problem: 197.56/71.51 The TRS P consists of the following rules: 197.56/71.51 197.56/71.51 TOP(go_up(x)) -> TOP(reduce(x)) 197.56/71.51 197.56/71.51 The TRS R consists of the following rules: 197.56/71.51 197.56/71.51 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.51 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.51 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 top(go_up(x0)) 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_h_1(go_up(x0)) 197.56/71.52 in_i_1(go_up(x0)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (21) QReductionProof (EQUIVALENT) 197.56/71.52 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 197.56/71.52 197.56/71.52 top(go_up(x0)) 197.56/71.52 in_h_1(go_up(x0)) 197.56/71.52 in_i_1(go_up(x0)) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (22) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(x)) -> TOP(reduce(x)) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (23) TransformationProof (EQUIVALENT) 197.56/71.52 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 197.56/71.52 197.56/71.52 (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)))) 197.56/71.52 (TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0))),TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0)))) 197.56/71.52 (TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))),TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0)))) 197.56/71.52 (TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))),TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0)))) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (24) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0))) 197.56/71.52 TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (25) TransformationProof (EQUIVALENT) 197.56/71.52 By rewriting [LPAR04] the rule TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0))) at position [0,0] we obtained the following new rules [LPAR04]: 197.56/71.52 197.56/71.52 (TOP(go_up(h(x0))) -> TOP(check_h(result_h(f(h(x0), c)))),TOP(go_up(h(x0))) -> TOP(check_h(result_h(f(h(x0), c))))) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (26) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 TOP(go_up(h(x0))) -> TOP(check_h(result_h(f(h(x0), c)))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (27) TransformationProof (EQUIVALENT) 197.56/71.52 By rewriting [LPAR04] the rule TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))) at position [0,0] we obtained the following new rules [LPAR04]: 197.56/71.52 197.56/71.52 (TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0)))),TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0))))) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (28) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 TOP(go_up(h(x0))) -> TOP(check_h(result_h(f(h(x0), c)))) 197.56/71.52 TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0)))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (29) TransformationProof (EQUIVALENT) 197.56/71.52 By rewriting [LPAR04] the rule TOP(go_up(h(x0))) -> TOP(check_h(result_h(f(h(x0), c)))) at position [0] we obtained the following new rules [LPAR04]: 197.56/71.52 197.56/71.52 (TOP(go_up(h(x0))) -> TOP(go_up(f(h(x0), c))),TOP(go_up(h(x0))) -> TOP(go_up(f(h(x0), c)))) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (30) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0)))) 197.56/71.52 TOP(go_up(h(x0))) -> TOP(go_up(f(h(x0), c))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (31) TransformationProof (EQUIVALENT) 197.56/71.52 By rewriting [LPAR04] the rule TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0)))) at position [0] we obtained the following new rules [LPAR04]: 197.56/71.52 197.56/71.52 (TOP(go_up(i(x0))) -> TOP(go_up(h(x0))),TOP(go_up(i(x0))) -> TOP(go_up(h(x0)))) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (32) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 TOP(go_up(h(x0))) -> TOP(go_up(f(h(x0), c))) 197.56/71.52 TOP(go_up(i(x0))) -> TOP(go_up(h(x0))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (33) QDPOrderProof (EQUIVALENT) 197.56/71.52 We use the reduction pair processor [LPAR04,JAR06]. 197.56/71.52 197.56/71.52 197.56/71.52 The following pairs can be oriented strictly and are deleted. 197.56/71.52 197.56/71.52 TOP(go_up(i(x0))) -> TOP(go_up(h(x0))) 197.56/71.52 The remaining pairs can at least be oriented weakly. 197.56/71.52 Used ordering: Matrix interpretation [MATRO]: 197.56/71.52 197.56/71.52 Non-tuple symbols: 197.56/71.52 <<< 197.56/71.52 M( result_f_1(x_1) ) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( reduce_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( result_h_1(x_1) ) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( c ) = [[0], [0]] 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( in_f_2_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( in_s_1_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( redex_f_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( check_f_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( redex_i_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( check_i_1(x_1) ) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( go_up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( in_f_1_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( result_i_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( check_h_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( f_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( redex_h_1(x_1) ) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( i_1(x_1) ) = [[1], [1]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( h_1(x_1) ) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 Tuple symbols: 197.56/71.52 <<< 197.56/71.52 M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 Matrix type: 197.56/71.52 197.56/71.52 We used a basic matrix type which is not further parametrizeable. 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 197.56/71.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 197.56/71.52 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (34) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 TOP(go_up(h(x0))) -> TOP(go_up(f(h(x0), c))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (35) QDPOrderProof (EQUIVALENT) 197.56/71.52 We use the reduction pair processor [LPAR04,JAR06]. 197.56/71.52 197.56/71.52 197.56/71.52 The following pairs can be oriented strictly and are deleted. 197.56/71.52 197.56/71.52 TOP(go_up(h(x0))) -> TOP(go_up(f(h(x0), c))) 197.56/71.52 The remaining pairs can at least be oriented weakly. 197.56/71.52 Used ordering: Matrix interpretation [MATRO]: 197.56/71.52 197.56/71.52 Non-tuple symbols: 197.56/71.52 <<< 197.56/71.52 M( result_f_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( reduce_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( result_h_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( c ) = [[0], [0]] 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( in_f_2_2(x_1, x_2) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( in_s_1_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( redex_f_2(x_1, x_2) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( check_f_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( redex_i_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( check_i_1(x_1) ) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( go_up_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( in_f_1_2(x_1, x_2) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( result_i_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( check_h_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( f_2(x_1, x_2) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( redex_h_1(x_1) ) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( i_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( h_1(x_1) ) = [[1], [0]] + [[1, 1], [1, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 Tuple symbols: 197.56/71.52 <<< 197.56/71.52 M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 Matrix type: 197.56/71.52 197.56/71.52 We used a basic matrix type which is not further parametrizeable. 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 197.56/71.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 197.56/71.52 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (36) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) 197.56/71.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (37) UsableRulesProof (EQUIVALENT) 197.56/71.52 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. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (38) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(x)) -> TOP(reduce(x)) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 top(go_up(x0)) 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_h_1(go_up(x0)) 197.56/71.52 in_i_1(go_up(x0)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (39) QReductionProof (EQUIVALENT) 197.56/71.52 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 197.56/71.52 197.56/71.52 top(go_up(x0)) 197.56/71.52 in_h_1(go_up(x0)) 197.56/71.52 in_i_1(go_up(x0)) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (40) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(go_up(x)) -> TOP(reduce(x)) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) 197.56/71.52 reduce(h(x_1)) -> check_h(redex_h(x_1)) 197.56/71.52 reduce(i(x_1)) -> check_i(redex_i(x_1)) 197.56/71.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 197.56/71.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 197.56/71.52 redex_i(x) -> result_i(h(x)) 197.56/71.52 check_i(result_i(x)) -> go_up(x) 197.56/71.52 redex_h(x) -> result_h(f(h(x), c)) 197.56/71.52 check_h(result_h(x)) -> go_up(x) 197.56/71.52 redex_f(h(x), c) -> result_f(f(i(x), s(x))) 197.56/71.52 redex_f(i(x), y) -> result_f(x) 197.56/71.52 check_f(result_f(x)) -> go_up(x) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) 197.56/71.52 check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) 197.56/71.52 in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) 197.56/71.52 in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 The set Q consists of the following terms: 197.56/71.52 197.56/71.52 reduce(f(x0, x1)) 197.56/71.52 reduce(h(x0)) 197.56/71.52 reduce(i(x0)) 197.56/71.52 redex_f(h(x0), c) 197.56/71.52 redex_h(x0) 197.56/71.52 redex_i(x0) 197.56/71.52 redex_f(i(x0), x1) 197.56/71.52 check_f(result_f(x0)) 197.56/71.52 check_h(result_h(x0)) 197.56/71.52 check_i(result_i(x0)) 197.56/71.52 check_f(redex_f(x0, x1)) 197.56/71.52 reduce(s(x0)) 197.56/71.52 in_f_1(go_up(x0), x1) 197.56/71.52 in_f_2(x0, go_up(x1)) 197.56/71.52 in_s_1(go_up(x0)) 197.56/71.52 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (41) Trivial-Transformation (SOUND) 197.56/71.52 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (42) 197.56/71.52 Obligation: 197.56/71.52 Q restricted rewrite system: 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 f(h(x), c) -> f(i(x), s(x)) 197.56/71.52 h(x) -> f(h(x), c) 197.56/71.52 i(x) -> h(x) 197.56/71.52 f(i(x), y) -> x 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (43) DependencyPairsProof (EQUIVALENT) 197.56/71.52 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (44) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 F(h(x), c) -> F(i(x), s(x)) 197.56/71.52 F(h(x), c) -> I(x) 197.56/71.52 H(x) -> F(h(x), c) 197.56/71.52 H(x) -> H(x) 197.56/71.52 I(x) -> H(x) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 f(h(x), c) -> f(i(x), s(x)) 197.56/71.52 h(x) -> f(h(x), c) 197.56/71.52 i(x) -> h(x) 197.56/71.52 f(i(x), y) -> x 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (45) DependencyGraphProof (EQUIVALENT) 197.56/71.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (46) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 F(h(x), c) -> I(x) 197.56/71.52 I(x) -> H(x) 197.56/71.52 H(x) -> F(h(x), c) 197.56/71.52 H(x) -> H(x) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 f(h(x), c) -> f(i(x), s(x)) 197.56/71.52 h(x) -> f(h(x), c) 197.56/71.52 i(x) -> h(x) 197.56/71.52 f(i(x), y) -> x 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (47) NonTerminationLoopProof (COMPLETE) 197.56/71.52 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 197.56/71.52 Found a loop by semiunifying a rule from P directly. 197.56/71.52 197.56/71.52 s = H(x) evaluates to t =H(x) 197.56/71.52 197.56/71.52 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 197.56/71.52 * Matcher: [ ] 197.56/71.52 * Semiunifier: [ ] 197.56/71.52 197.56/71.52 -------------------------------------------------------------------------------- 197.56/71.52 Rewriting sequence 197.56/71.52 197.56/71.52 The DP semiunifies directly so there is only one rewrite step from H(x) to H(x). 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (48) 197.56/71.52 NO 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (49) Raffelsieper-Zantema-Transformation (SOUND) 197.56/71.52 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (50) 197.56/71.52 Obligation: 197.56/71.52 Q restricted rewrite system: 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (51) DependencyPairsProof (EQUIVALENT) 197.56/71.52 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (52) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(x)) -> TOP(down(x)) 197.56/71.52 TOP(up(x)) -> DOWN(x) 197.56/71.52 DOWN(s(y4)) -> S_FLAT(down(y4)) 197.56/71.52 DOWN(s(y4)) -> DOWN(y4) 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> F_FLAT(down(f(y7, y8)), block(y9)) 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> DOWN(f(y7, y8)) 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> F_FLAT(block(f(y7, y8)), down(y9)) 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> DOWN(y9) 197.56/71.52 DOWN(f(c, y12)) -> F_FLAT(down(c), block(y12)) 197.56/71.52 DOWN(f(c, y12)) -> DOWN(c) 197.56/71.52 DOWN(f(c, y12)) -> F_FLAT(block(c), down(y12)) 197.56/71.52 DOWN(f(c, y12)) -> DOWN(y12) 197.56/71.52 DOWN(f(s(y15), y16)) -> F_FLAT(down(s(y15)), block(y16)) 197.56/71.52 DOWN(f(s(y15), y16)) -> DOWN(s(y15)) 197.56/71.52 DOWN(f(s(y15), y16)) -> F_FLAT(block(s(y15)), down(y16)) 197.56/71.52 DOWN(f(s(y15), y16)) -> DOWN(y16) 197.56/71.52 DOWN(f(fresh_constant, y17)) -> F_FLAT(down(fresh_constant), block(y17)) 197.56/71.52 DOWN(f(fresh_constant, y17)) -> DOWN(fresh_constant) 197.56/71.52 DOWN(f(fresh_constant, y17)) -> F_FLAT(block(fresh_constant), down(y17)) 197.56/71.52 DOWN(f(fresh_constant, y17)) -> DOWN(y17) 197.56/71.52 DOWN(f(h(y25), f(y26, y27))) -> F_FLAT(down(h(y25)), block(f(y26, y27))) 197.56/71.52 DOWN(f(h(y25), f(y26, y27))) -> DOWN(h(y25)) 197.56/71.52 DOWN(f(h(y25), f(y26, y27))) -> F_FLAT(block(h(y25)), down(f(y26, y27))) 197.56/71.52 DOWN(f(h(y25), f(y26, y27))) -> DOWN(f(y26, y27)) 197.56/71.52 DOWN(f(h(y43), h(y44))) -> F_FLAT(down(h(y43)), block(h(y44))) 197.56/71.52 DOWN(f(h(y43), h(y44))) -> DOWN(h(y43)) 197.56/71.52 DOWN(f(h(y43), h(y44))) -> F_FLAT(block(h(y43)), down(h(y44))) 197.56/71.52 DOWN(f(h(y43), h(y44))) -> DOWN(h(y44)) 197.56/71.52 DOWN(f(h(y62), i(y63))) -> F_FLAT(down(h(y62)), block(i(y63))) 197.56/71.52 DOWN(f(h(y62), i(y63))) -> DOWN(h(y62)) 197.56/71.52 DOWN(f(h(y62), i(y63))) -> F_FLAT(block(h(y62)), down(i(y63))) 197.56/71.52 DOWN(f(h(y62), i(y63))) -> DOWN(i(y63)) 197.56/71.52 DOWN(f(h(y75), s(y76))) -> F_FLAT(down(h(y75)), block(s(y76))) 197.56/71.52 DOWN(f(h(y75), s(y76))) -> DOWN(h(y75)) 197.56/71.52 DOWN(f(h(y75), s(y76))) -> F_FLAT(block(h(y75)), down(s(y76))) 197.56/71.52 DOWN(f(h(y75), s(y76))) -> DOWN(s(y76)) 197.56/71.52 DOWN(f(h(y86), fresh_constant)) -> F_FLAT(down(h(y86)), block(fresh_constant)) 197.56/71.52 DOWN(f(h(y86), fresh_constant)) -> DOWN(h(y86)) 197.56/71.52 DOWN(f(h(y86), fresh_constant)) -> F_FLAT(block(h(y86)), down(fresh_constant)) 197.56/71.52 DOWN(f(h(y86), fresh_constant)) -> DOWN(fresh_constant) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (53) DependencyGraphProof (EQUIVALENT) 197.56/71.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 30 less nodes. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (54) 197.56/71.52 Complex Obligation (AND) 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (55) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> DOWN(f(y7, y8)) 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> DOWN(y9) 197.56/71.52 DOWN(s(y4)) -> DOWN(y4) 197.56/71.52 DOWN(f(c, y12)) -> DOWN(y12) 197.56/71.52 DOWN(f(s(y15), y16)) -> DOWN(s(y15)) 197.56/71.52 DOWN(f(s(y15), y16)) -> DOWN(y16) 197.56/71.52 DOWN(f(fresh_constant, y17)) -> DOWN(y17) 197.56/71.52 DOWN(f(h(y25), f(y26, y27))) -> DOWN(f(y26, y27)) 197.56/71.52 DOWN(f(h(y75), s(y76))) -> DOWN(s(y76)) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (56) UsableRulesProof (EQUIVALENT) 197.56/71.52 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (57) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> DOWN(f(y7, y8)) 197.56/71.52 DOWN(f(f(y7, y8), y9)) -> DOWN(y9) 197.56/71.52 DOWN(s(y4)) -> DOWN(y4) 197.56/71.52 DOWN(f(c, y12)) -> DOWN(y12) 197.56/71.52 DOWN(f(s(y15), y16)) -> DOWN(s(y15)) 197.56/71.52 DOWN(f(s(y15), y16)) -> DOWN(y16) 197.56/71.52 DOWN(f(fresh_constant, y17)) -> DOWN(y17) 197.56/71.52 DOWN(f(h(y25), f(y26, y27))) -> DOWN(f(y26, y27)) 197.56/71.52 DOWN(f(h(y75), s(y76))) -> DOWN(s(y76)) 197.56/71.52 197.56/71.52 R is empty. 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (58) QDPSizeChangeProof (EQUIVALENT) 197.56/71.52 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 197.56/71.52 197.56/71.52 From the DPs we obtained the following set of size-change graphs: 197.56/71.52 *DOWN(s(y4)) -> DOWN(y4) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(f(y7, y8), y9)) -> DOWN(y9) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(c, y12)) -> DOWN(y12) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(s(y15), y16)) -> DOWN(y16) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(fresh_constant, y17)) -> DOWN(y17) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(f(y7, y8), y9)) -> DOWN(f(y7, y8)) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(h(y25), f(y26, y27))) -> DOWN(f(y26, y27)) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(s(y15), y16)) -> DOWN(s(y15)) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 *DOWN(f(h(y75), s(y76))) -> DOWN(s(y76)) 197.56/71.52 The graph contains the following edges 1 > 1 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (59) 197.56/71.52 YES 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (60) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(x)) -> TOP(down(x)) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (61) TransformationProof (EQUIVALENT) 197.56/71.52 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 197.56/71.52 197.56/71.52 (TOP(up(f(h(x0), c))) -> TOP(up(f(i(x0), s(x0)))),TOP(up(f(h(x0), c))) -> TOP(up(f(i(x0), s(x0))))) 197.56/71.52 (TOP(up(h(x0))) -> TOP(up(f(h(x0), c))),TOP(up(h(x0))) -> TOP(up(f(h(x0), c)))) 197.56/71.52 (TOP(up(i(x0))) -> TOP(up(h(x0))),TOP(up(i(x0))) -> TOP(up(h(x0)))) 197.56/71.52 (TOP(up(f(i(x0), x1))) -> TOP(up(x0)),TOP(up(f(i(x0), x1))) -> TOP(up(x0))) 197.56/71.52 (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) 197.56/71.52 (TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))),TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2)))) 197.56/71.52 (TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))),TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2)))) 197.56/71.52 (TOP(up(f(c, x0))) -> TOP(f_flat(down(c), block(x0))),TOP(up(f(c, x0))) -> TOP(f_flat(down(c), block(x0)))) 197.56/71.52 (TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0))),TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0)))) 197.56/71.52 (TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1))),TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1)))) 197.56/71.52 (TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1))),TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1)))) 197.56/71.52 (TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(down(fresh_constant), block(x0))),TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(down(fresh_constant), block(x0)))) 197.56/71.52 (TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))),TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0)))) 197.56/71.52 (TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2)))),TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2))))) 197.56/71.52 (TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2)))),TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2))))) 197.56/71.52 (TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1)))),TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1))))) 197.56/71.52 (TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1)))),TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1))))) 197.56/71.52 (TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1)))),TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1))))) 197.56/71.52 (TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1)))),TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1))))) 197.56/71.52 (TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1)))),TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1))))) 197.56/71.52 (TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1)))),TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1))))) 197.56/71.52 (TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant))),TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant)))) 197.56/71.52 (TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(block(h(x0)), down(fresh_constant))),TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(block(h(x0)), down(fresh_constant)))) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (62) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(f(h(x0), c))) -> TOP(up(f(i(x0), s(x0)))) 197.56/71.52 TOP(up(h(x0))) -> TOP(up(f(h(x0), c))) 197.56/71.52 TOP(up(i(x0))) -> TOP(up(h(x0))) 197.56/71.52 TOP(up(f(i(x0), x1))) -> TOP(up(x0)) 197.56/71.52 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) 197.56/71.52 TOP(up(f(c, x0))) -> TOP(f_flat(down(c), block(x0))) 197.56/71.52 TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1))) 197.56/71.52 TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(down(fresh_constant), block(x0))) 197.56/71.52 TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant))) 197.56/71.52 TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(block(h(x0)), down(fresh_constant))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (63) DependencyGraphProof (EQUIVALENT) 197.56/71.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (64) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(f(i(x0), x1))) -> TOP(up(x0)) 197.56/71.52 TOP(up(f(h(x0), c))) -> TOP(up(f(i(x0), s(x0)))) 197.56/71.52 TOP(up(h(x0))) -> TOP(up(f(h(x0), c))) 197.56/71.52 TOP(up(i(x0))) -> TOP(up(h(x0))) 197.56/71.52 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) 197.56/71.52 TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1))) 197.56/71.52 TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (65) QDPOrderProof (EQUIVALENT) 197.56/71.52 We use the reduction pair processor [LPAR04,JAR06]. 197.56/71.52 197.56/71.52 197.56/71.52 The following pairs can be oriented strictly and are deleted. 197.56/71.52 197.56/71.52 TOP(up(f(i(x0), x1))) -> TOP(up(x0)) 197.56/71.52 The remaining pairs can at least be oriented weakly. 197.56/71.52 Used ordering: Polynomial interpretation [POLO]: 197.56/71.52 197.56/71.52 POL(TOP(x_1)) = x_1 197.56/71.52 POL(block(x_1)) = x_1 197.56/71.52 POL(c) = 0 197.56/71.52 POL(down(x_1)) = x_1 197.56/71.52 POL(f(x_1, x_2)) = x_1 197.56/71.52 POL(f_flat(x_1, x_2)) = x_1 197.56/71.52 POL(fresh_constant) = 0 197.56/71.52 POL(h(x_1)) = 1 + x_1 197.56/71.52 POL(i(x_1)) = 1 + x_1 197.56/71.52 POL(s(x_1)) = 0 197.56/71.52 POL(s_flat(x_1)) = 0 197.56/71.52 POL(up(x_1)) = x_1 197.56/71.52 197.56/71.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (66) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(f(h(x0), c))) -> TOP(up(f(i(x0), s(x0)))) 197.56/71.52 TOP(up(h(x0))) -> TOP(up(f(h(x0), c))) 197.56/71.52 TOP(up(i(x0))) -> TOP(up(h(x0))) 197.56/71.52 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) 197.56/71.52 TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1))) 197.56/71.52 TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (67) DependencyGraphProof (EQUIVALENT) 197.56/71.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (68) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) 197.56/71.52 TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1))) 197.56/71.52 TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (69) QDPOrderProof (EQUIVALENT) 197.56/71.52 We use the reduction pair processor [LPAR04,JAR06]. 197.56/71.52 197.56/71.52 197.56/71.52 The following pairs can be oriented strictly and are deleted. 197.56/71.52 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(block(h(x0)), down(i(x1)))) 197.56/71.52 The remaining pairs can at least be oriented weakly. 197.56/71.52 Used ordering: Matrix interpretation [MATRO]: 197.56/71.52 197.56/71.52 Non-tuple symbols: 197.56/71.52 <<< 197.56/71.52 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( c ) = [[0], [0]] 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( block_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( f_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( i_1(x_1) ) = [[0], [1]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( fresh_constant ) = [[0], [0]] 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( h_1(x_1) ) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( up_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 <<< 197.56/71.52 M( f_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 197.56/71.52 >>> 197.56/71.52 197.56/71.52 Tuple symbols: 197.56/71.52 <<< 197.56/71.52 M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 197.56/71.52 >>> 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 Matrix type: 197.56/71.52 197.56/71.52 We used a basic matrix type which is not further parametrizeable. 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 197.56/71.52 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 197.56/71.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 197.56/71.52 197.56/71.52 ---------------------------------------- 197.56/71.52 197.56/71.52 (70) 197.56/71.52 Obligation: 197.56/71.52 Q DP problem: 197.56/71.52 The TRS P consists of the following rules: 197.56/71.52 197.56/71.52 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) 197.56/71.52 TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) 197.56/71.52 TOP(up(f(c, x0))) -> TOP(f_flat(block(c), down(x0))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(down(s(x0)), block(x1))) 197.56/71.52 TOP(up(f(s(x0), x1))) -> TOP(f_flat(block(s(x0)), down(x1))) 197.56/71.52 TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(down(h(x0)), block(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), f(x1, x2)))) -> TOP(f_flat(block(h(x0)), down(f(x1, x2)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(down(h(x0)), block(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), h(x1)))) -> TOP(f_flat(block(h(x0)), down(h(x1)))) 197.56/71.52 TOP(up(f(h(x0), i(x1)))) -> TOP(f_flat(down(h(x0)), block(i(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(down(h(x0)), block(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), s(x1)))) -> TOP(f_flat(block(h(x0)), down(s(x1)))) 197.56/71.52 TOP(up(f(h(x0), fresh_constant))) -> TOP(f_flat(down(h(x0)), block(fresh_constant))) 197.56/71.52 197.56/71.52 The TRS R consists of the following rules: 197.56/71.52 197.56/71.52 down(f(h(x), c)) -> up(f(i(x), s(x))) 197.56/71.52 down(h(x)) -> up(f(h(x), c)) 197.56/71.52 down(i(x)) -> up(h(x)) 197.56/71.52 down(f(i(x), y)) -> up(x) 197.56/71.52 top(up(x)) -> top(down(x)) 197.56/71.52 down(s(y4)) -> s_flat(down(y4)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(down(f(y7, y8)), block(y9)) 197.56/71.52 down(f(f(y7, y8), y9)) -> f_flat(block(f(y7, y8)), down(y9)) 197.56/71.52 down(f(c, y12)) -> f_flat(down(c), block(y12)) 197.56/71.52 down(f(c, y12)) -> f_flat(block(c), down(y12)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(down(s(y15)), block(y16)) 197.56/71.52 down(f(s(y15), y16)) -> f_flat(block(s(y15)), down(y16)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(down(fresh_constant), block(y17)) 197.56/71.52 down(f(fresh_constant, y17)) -> f_flat(block(fresh_constant), down(y17)) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(down(h(y25)), block(f(y26, y27))) 197.56/71.52 down(f(h(y25), f(y26, y27))) -> f_flat(block(h(y25)), down(f(y26, y27))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(down(h(y43)), block(h(y44))) 197.56/71.52 down(f(h(y43), h(y44))) -> f_flat(block(h(y43)), down(h(y44))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(down(h(y62)), block(i(y63))) 197.56/71.52 down(f(h(y62), i(y63))) -> f_flat(block(h(y62)), down(i(y63))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(down(h(y75)), block(s(y76))) 197.56/71.52 down(f(h(y75), s(y76))) -> f_flat(block(h(y75)), down(s(y76))) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(down(h(y86)), block(fresh_constant)) 197.56/71.52 down(f(h(y86), fresh_constant)) -> f_flat(block(h(y86)), down(fresh_constant)) 197.56/71.52 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 197.56/71.52 h_flat(up(x_1)) -> up(h(x_1)) 197.56/71.52 i_flat(up(x_1)) -> up(i(x_1)) 197.56/71.52 s_flat(up(x_1)) -> up(s(x_1)) 197.56/71.52 197.56/71.52 Q is empty. 197.56/71.52 We have to consider all minimal (P,Q,R)-chains. 197.56/71.57 EOF