/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could not be shown: (0) OTRS (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) MRRProof [EQUIVALENT, 17 ms] (13) QDP (14) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] (15) QDP (16) DependencyGraphProof [EQUIVALENT, 0 ms] (17) TRUE (18) QDP (19) UsableRulesProof [EQUIVALENT, 0 ms] (20) QDP (21) QReductionProof [EQUIVALENT, 0 ms] (22) QDP (23) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] (24) QDP (25) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) TRUE (29) QDP (30) UsableRulesProof [EQUIVALENT, 0 ms] (31) QDP (32) QReductionProof [EQUIVALENT, 0 ms] (33) QDP (34) TransformationProof [EQUIVALENT, 0 ms] (35) QDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) QDP (38) QReductionProof [EQUIVALENT, 0 ms] (39) QDP (40) Trivial-Transformation [SOUND, 0 ms] (41) QTRS (42) DependencyPairsProof [EQUIVALENT, 0 ms] (43) QDP (44) DependencyGraphProof [EQUIVALENT, 0 ms] (45) AND (46) QDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) QDP (49) QDPSizeChangeProof [EQUIVALENT, 0 ms] (50) YES (51) QDP (52) TransformationProof [EQUIVALENT, 0 ms] (53) QDP (54) DependencyGraphProof [EQUIVALENT, 0 ms] (55) QDP (56) QDPOrderProof [EQUIVALENT, 10 ms] (57) QDP (58) QDPOrderProof [EQUIVALENT, 0 ms] (59) QDP (60) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (61) QTRS (62) AAECC Innermost [EQUIVALENT, 5 ms] (63) QTRS (64) DependencyPairsProof [EQUIVALENT, 0 ms] (65) QDP (66) DependencyGraphProof [EQUIVALENT, 0 ms] (67) AND (68) QDP (69) UsableRulesProof [EQUIVALENT, 0 ms] (70) QDP (71) QReductionProof [EQUIVALENT, 0 ms] (72) QDP (73) QDPSizeChangeProof [EQUIVALENT, 0 ms] (74) YES (75) QDP (76) UsableRulesProof [EQUIVALENT, 0 ms] (77) QDP (78) QReductionProof [EQUIVALENT, 0 ms] (79) QDP (80) TransformationProof [EQUIVALENT, 0 ms] (81) QDP (82) DependencyGraphProof [EQUIVALENT, 0 ms] (83) QDP (84) TransformationProof [EQUIVALENT, 0 ms] (85) QDP (86) DependencyGraphProof [EQUIVALENT, 0 ms] (87) QDP (88) TransformationProof [EQUIVALENT, 0 ms] (89) QDP (90) TransformationProof [EQUIVALENT, 0 ms] (91) QDP (92) TransformationProof [EQUIVALENT, 0 ms] (93) QDP (94) TransformationProof [EQUIVALENT, 0 ms] (95) QDP (96) TransformationProof [EQUIVALENT, 0 ms] (97) QDP (98) DependencyGraphProof [EQUIVALENT, 0 ms] (99) QDP (100) TransformationProof [EQUIVALENT, 0 ms] (101) QDP (102) TransformationProof [EQUIVALENT, 0 ms] (103) QDP (104) TransformationProof [EQUIVALENT, 0 ms] (105) QDP (106) DependencyGraphProof [EQUIVALENT, 0 ms] (107) QDP (108) TransformationProof [EQUIVALENT, 0 ms] (109) QDP (110) QDPOrderProof [EQUIVALENT, 2 ms] (111) QDP (112) QDPOrderProof [EQUIVALENT, 17 ms] (113) QDP (114) MNOCProof [EQUIVALENT, 0 ms] (115) QDP (116) SplitQDPProof [EQUIVALENT, 0 ms] (117) AND (118) QDP (119) SemLabProof [SOUND, 0 ms] (120) QDP (121) DependencyGraphProof [EQUIVALENT, 0 ms] (122) QDP (123) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (124) QDP (125) MRRProof [EQUIVALENT, 0 ms] (126) QDP (127) DependencyGraphProof [EQUIVALENT, 0 ms] (128) QDP (129) MRRProof [EQUIVALENT, 6 ms] (130) QDP (131) MRRProof [EQUIVALENT, 0 ms] (132) QDP (133) PisEmptyProof [SOUND, 0 ms] (134) TRUE (135) QDP (136) SplitQDPProof [EQUIVALENT, 0 ms] (137) AND (138) QDP (139) SemLabProof [SOUND, 0 ms] (140) QDP (141) DependencyGraphProof [EQUIVALENT, 0 ms] (142) QDP (143) MRRProof [EQUIVALENT, 0 ms] (144) QDP (145) DependencyGraphProof [EQUIVALENT, 0 ms] (146) QDP (147) MRRProof [EQUIVALENT, 0 ms] (148) QDP (149) DependencyGraphProof [EQUIVALENT, 0 ms] (150) QDP (151) PisEmptyProof [SOUND, 0 ms] (152) TRUE (153) QDP (154) SplitQDPProof [EQUIVALENT, 0 ms] (155) AND (156) QDP (157) SemLabProof [SOUND, 0 ms] (158) QDP (159) MRRProof [EQUIVALENT, 0 ms] (160) QDP (161) DependencyGraphProof [EQUIVALENT, 0 ms] (162) QDP (163) MRRProof [EQUIVALENT, 0 ms] (164) QDP (165) MRRProof [EQUIVALENT, 4 ms] (166) QDP (167) DependencyGraphProof [EQUIVALENT, 0 ms] (168) QDP (169) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (170) QDP (171) PisEmptyProof [SOUND, 0 ms] (172) TRUE (173) QDP (174) QReductionProof [EQUIVALENT, 0 ms] (175) QDP ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Outermost Strategy. ---------------------------------------- (1) Thiemann-SpecialC-Transformation (EQUIVALENT) We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_b(u(x)) -> result_b(b(f(x))) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) TOP(go_up(x)) -> REDUCE(x) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(f(x_1)) -> REDEX_F(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) REDUCE(b(x_1)) -> REDEX_B(x_1) CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) CHECK_F(redex_f(x_1)) -> REDUCE(x_1) CHECK_B(redex_b(x_1)) -> IN_B_1(reduce(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> IN_U_1(reduce(x_1)) REDUCE(u(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> IN_G_1(reduce(x_1)) REDUCE(g(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_b(u(x)) -> result_b(b(f(x))) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_b(u(x)) -> result_b(b(f(x))) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) The TRS R consists of the following rules: redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_b(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) The TRS R consists of the following rules: redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) The set Q consists of the following terms: redex_f(f(f(x0))) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = 1 + x_1 POL(REDUCE(x_1)) = 2 + 2*x_1 POL(b(x_1)) = x_1 POL(c) = 0 POL(f(x_1)) = x_1 POL(g(x_1)) = 2*x_1 POL(redex_f(x_1)) = 1 + 2*x_1 POL(result_f(x_1)) = x_1 POL(u(x_1)) = x_1 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) R is empty. The set Q consists of the following terms: redex_f(f(f(x0))) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) UsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = 2*x_1 POL(REDUCE(x_1)) = 2*x_1 POL(f(x_1)) = 2*x_1 POL(redex_f(x_1)) = x_1 ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) R is empty. The set Q consists of the following terms: redex_f(f(f(x0))) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (17) TRUE ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_b(u(x)) -> result_b(b(f(x))) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_b(u(x)) -> result_b(b(f(x))) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_b(u(x)) -> result_b(b(f(x))) The set Q consists of the following terms: redex_b(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) UsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: REDUCE(g(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) The following rules are removed from R: redex_b(u(x)) -> result_b(b(f(x))) Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_B(x_1)) = x_1 POL(REDUCE(x_1)) = 2*x_1 POL(b(x_1)) = 2*x_1 POL(f(x_1)) = 2*x_1 POL(g(x_1)) = 2*x_1 POL(redex_b(x_1)) = 2*x_1 POL(result_b(x_1)) = x_1 POL(u(x_1)) = 2*x_1 ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) R is empty. The set Q consists of the following terms: redex_b(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) UsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_B(x_1)) = 2*x_1 POL(REDUCE(x_1)) = 2*x_1 POL(b(x_1)) = 2*x_1 POL(redex_b(x_1)) = x_1 ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_B(redex_b(x_1)) -> REDUCE(x_1) R is empty. The set Q consists of the following terms: redex_b(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (28) TRUE ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_b(u(x)) -> result_b(b(f(x))) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_b(u(x)) -> result_b(b(f(x))) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_b(u(x)) -> result_b(b(f(x))) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) (TOP(go_up(b(x0))) -> TOP(check_b(redex_b(x0))),TOP(go_up(b(x0))) -> TOP(check_b(redex_b(x0)))) (TOP(go_up(u(x0))) -> TOP(in_u_1(reduce(x0))),TOP(go_up(u(x0))) -> TOP(in_u_1(reduce(x0)))) (TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0))),TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0)))) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) TOP(go_up(b(x0))) -> TOP(check_b(redex_b(x0))) TOP(go_up(u(x0))) -> TOP(in_u_1(reduce(x0))) TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0))) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_b(u(x)) -> result_b(b(f(x))) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_b(u(x)) -> result_b(b(f(x))) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) reduce(g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_b(u(x)) -> result_b(b(f(x))) check_b(result_b(x)) -> go_up(x) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) in_b_1(go_up(x_1)) -> go_up(b(x_1)) redex_f(f(f(x))) -> result_f(c) redex_f(g(x)) -> result_f(f(f(x))) redex_f(b(x)) -> result_f(u(g(b(x)))) redex_f(u(x)) -> result_f(u(g(x))) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(b(x0)) redex_f(f(f(x0))) redex_b(u(x0)) redex_f(g(x0)) redex_f(b(x0)) redex_f(u(x0)) check_f(result_f(x0)) check_b(result_b(x0)) check_f(redex_f(x0)) check_b(redex_b(x0)) reduce(u(x0)) reduce(g(x0)) in_f_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) Trivial-Transformation (SOUND) We applied the Trivial transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (41) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. ---------------------------------------- (42) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(x)) -> B(f(x)) B(u(x)) -> F(x) F(g(x)) -> F(f(x)) F(g(x)) -> F(x) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. ---------------------------------------- (45) Complex Obligation (AND) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(x)) -> F(x) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(x)) -> F(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *F(g(x)) -> F(x) The graph contains the following edges 1 > 1 ---------------------------------------- (50) YES ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(x)) -> B(f(x)) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule B(u(x)) -> B(f(x)) at position [0] we obtained the following new rules [LPAR04]: (B(u(f(f(x0)))) -> B(c),B(u(f(f(x0)))) -> B(c)) (B(u(g(x0))) -> B(f(f(x0))),B(u(g(x0))) -> B(f(f(x0)))) (B(u(b(x0))) -> B(u(g(b(x0)))),B(u(b(x0))) -> B(u(g(b(x0))))) (B(u(u(x0))) -> B(u(g(x0))),B(u(u(x0))) -> B(u(g(x0)))) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(f(f(x0)))) -> B(c) B(u(g(x0))) -> B(f(f(x0))) B(u(b(x0))) -> B(u(g(b(x0)))) B(u(u(x0))) -> B(u(g(x0))) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(g(x0))) -> B(f(f(x0))) B(u(b(x0))) -> B(u(g(b(x0)))) B(u(u(x0))) -> B(u(g(x0))) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. B(u(b(x0))) -> B(u(g(b(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(B(x_1)) = x_1 POL(b(x_1)) = 1 + x_1 POL(c) = 0 POL(f(x_1)) = 0 POL(g(x_1)) = 0 POL(u(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f(f(f(x))) -> c f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) b(u(x)) -> b(f(x)) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(g(x0))) -> B(f(f(x0))) B(u(u(x0))) -> B(u(g(x0))) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. B(u(u(x0))) -> B(u(g(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(B(x_1)) = x_1 POL(b(x_1)) = x_1 POL(c) = 0 POL(f(x_1)) = 1 POL(g(x_1)) = 0 POL(u(x_1)) = 1 + x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f(f(f(x))) -> c f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) b(u(x)) -> b(f(x)) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(g(x0))) -> B(f(f(x0))) The TRS R consists of the following rules: f(f(f(x))) -> c b(u(x)) -> b(f(x)) f(g(x)) -> f(f(x)) f(b(x)) -> u(g(b(x))) f(u(x)) -> u(g(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (61) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) g_flat(up(x_1)) -> up(g(x_1)) Q is empty. ---------------------------------------- (62) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) g_flat(up(x_1)) -> up(g(x_1)) down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) The TRS R 2 is top(up(x)) -> top(down(x)) The signature Sigma is {top_1} ---------------------------------------- (63) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) ---------------------------------------- (64) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) TOP(up(x)) -> DOWN(x) DOWN(u(y2)) -> U_FLAT(down(y2)) DOWN(u(y2)) -> DOWN(y2) DOWN(g(y3)) -> G_FLAT(down(y3)) DOWN(g(y3)) -> DOWN(y3) DOWN(f(c)) -> F_FLAT(down(c)) DOWN(f(c)) -> DOWN(c) DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) DOWN(f(fresh_constant)) -> DOWN(fresh_constant) DOWN(b(f(y10))) -> B_FLAT(down(f(y10))) DOWN(b(f(y10))) -> DOWN(f(y10)) DOWN(b(c)) -> B_FLAT(down(c)) DOWN(b(c)) -> DOWN(c) DOWN(b(b(y11))) -> B_FLAT(down(b(y11))) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(g(y13))) -> B_FLAT(down(g(y13))) DOWN(b(g(y13))) -> DOWN(g(y13)) DOWN(b(fresh_constant)) -> B_FLAT(down(fresh_constant)) DOWN(b(fresh_constant)) -> DOWN(fresh_constant) DOWN(f(f(c))) -> F_FLAT(down(f(c))) DOWN(f(f(c))) -> DOWN(f(c)) DOWN(f(f(b(y16)))) -> F_FLAT(down(f(b(y16)))) DOWN(f(f(b(y16)))) -> DOWN(f(b(y16))) DOWN(f(f(u(y17)))) -> F_FLAT(down(f(u(y17)))) DOWN(f(f(u(y17)))) -> DOWN(f(u(y17))) DOWN(f(f(g(y18)))) -> F_FLAT(down(f(g(y18)))) DOWN(f(f(g(y18)))) -> DOWN(f(g(y18))) DOWN(f(f(fresh_constant))) -> F_FLAT(down(f(fresh_constant))) DOWN(f(f(fresh_constant))) -> DOWN(f(fresh_constant)) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 25 less nodes. ---------------------------------------- (67) Complex Obligation (AND) ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(g(y3)) -> DOWN(y3) DOWN(u(y2)) -> DOWN(y2) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(g(y13))) -> DOWN(g(y13)) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(g(y3)) -> DOWN(y3) DOWN(u(y2)) -> DOWN(y2) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(g(y13))) -> DOWN(g(y13)) R is empty. The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(g(y3)) -> DOWN(y3) DOWN(u(y2)) -> DOWN(y2) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(g(y13))) -> DOWN(g(y13)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *DOWN(b(b(y11))) -> DOWN(b(y11)) The graph contains the following edges 1 > 1 *DOWN(b(g(y13))) -> DOWN(g(y13)) The graph contains the following edges 1 > 1 *DOWN(g(y3)) -> DOWN(y3) The graph contains the following edges 1 > 1 *DOWN(u(y2)) -> DOWN(y2) The graph contains the following edges 1 > 1 ---------------------------------------- (74) YES ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) top(up(x0)) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(up(x0)) ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(x0))))) -> TOP(up(c)),TOP(up(f(f(f(x0))))) -> TOP(up(c))) (TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))),TOP(up(b(u(x0)))) -> TOP(up(b(f(x0))))) (TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))),TOP(up(f(g(x0)))) -> TOP(up(f(f(x0))))) (TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))),TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0)))))) (TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))),TOP(up(f(u(x0)))) -> TOP(up(u(g(x0))))) (TOP(up(u(x0))) -> TOP(u_flat(down(x0))),TOP(up(u(x0))) -> TOP(u_flat(down(x0)))) (TOP(up(g(x0))) -> TOP(g_flat(down(x0))),TOP(up(g(x0))) -> TOP(g_flat(down(x0)))) (TOP(up(f(c))) -> TOP(f_flat(down(c))),TOP(up(f(c))) -> TOP(f_flat(down(c)))) (TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))) (TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))),TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0))))) (TOP(up(b(c))) -> TOP(b_flat(down(c))),TOP(up(b(c))) -> TOP(b_flat(down(c)))) (TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))),TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0))))) (TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))),TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0))))) (TOP(up(b(fresh_constant))) -> TOP(b_flat(down(fresh_constant))),TOP(up(b(fresh_constant))) -> TOP(b_flat(down(fresh_constant)))) (TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))),TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))) (TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0))))),TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0)))))) (TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))),TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0)))))) (TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))),TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))) (TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))),TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))) ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(f(x0))))) -> TOP(up(c)) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(f(c))) -> TOP(f_flat(down(c))) TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(b(c))) -> TOP(b_flat(down(c))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) TOP(up(b(fresh_constant))) -> TOP(b_flat(down(fresh_constant))) TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0))))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))) TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(c)))) -> TOP(f_flat(f_flat(down(c)))),TOP(up(f(f(c)))) -> TOP(f_flat(f_flat(down(c))))) ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) TOP(up(f(f(c)))) -> TOP(f_flat(f_flat(down(c)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0))))) TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(b(x0))))) -> TOP(f_flat(down(f(b(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))),TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0))))))) ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(u(x0))))) -> TOP(f_flat(down(f(u(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))),TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0)))))) ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (92) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(b(g(x0)))) -> TOP(b_flat(down(g(x0)))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))),TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0))))) ---------------------------------------- (93) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (94) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))),TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0)))))) ---------------------------------------- (95) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (96) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(f_flat(down(fresh_constant)))),TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(f_flat(down(fresh_constant))))) ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))) TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(f_flat(down(fresh_constant)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (98) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(b(x0))))) -> TOP(f_flat(up(u(g(b(x0)))))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))),TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0))))))) ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))) TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(u(x0))))) -> TOP(f_flat(up(u(g(x0))))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))),TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0)))))) ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))) TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (104) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(f(g(x0))))) -> TOP(f_flat(up(f(f(x0))))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(g(x0))))) -> TOP(up(f(f(f(x0))))),TOP(up(f(f(g(x0))))) -> TOP(up(f(f(f(x0)))))) ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))) TOP(up(f(f(g(x0))))) -> TOP(up(f(f(f(x0))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (106) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (107) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (108) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(g(x0)))) -> TOP(up(f(f(x0)))) we obtained the following new rules [LPAR04]: (TOP(up(f(g(b(y_0))))) -> TOP(up(f(f(b(y_0))))),TOP(up(f(g(b(y_0))))) -> TOP(up(f(f(b(y_0)))))) (TOP(up(f(g(u(y_0))))) -> TOP(up(f(f(u(y_0))))),TOP(up(f(g(u(y_0))))) -> TOP(up(f(f(u(y_0)))))) ---------------------------------------- (109) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) TOP(up(f(g(b(y_0))))) -> TOP(up(f(f(b(y_0))))) TOP(up(f(g(u(y_0))))) -> TOP(up(f(f(u(y_0))))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (110) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(f(g(b(y_0))))) -> TOP(up(f(f(b(y_0))))) TOP(up(f(g(u(y_0))))) -> TOP(up(f(f(u(y_0))))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(b(x_1)) = 0 POL(b_flat(x_1)) = 0 POL(c) = 0 POL(down(x_1)) = 0 POL(f(x_1)) = x_1 POL(f_flat(x_1)) = 0 POL(fresh_constant) = 0 POL(g(x_1)) = 1 POL(g_flat(x_1)) = 1 POL(u(x_1)) = 0 POL(u_flat(x_1)) = 0 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: u_flat(up(x_1)) -> up(u(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) ---------------------------------------- (111) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (112) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(f(f(b(x0))))) -> TOP(up(f(u(g(b(x0)))))) TOP(up(f(u(x0)))) -> TOP(up(u(g(x0)))) TOP(up(f(f(u(x0))))) -> TOP(up(f(u(g(x0))))) TOP(up(f(b(x0)))) -> TOP(up(u(g(b(x0))))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(b(x_1)) = 0 POL(b_flat(x_1)) = 0 POL(c) = 0 POL(down(x_1)) = 0 POL(f(x_1)) = 1 + x_1 POL(f_flat(x_1)) = 0 POL(fresh_constant) = 0 POL(g(x_1)) = 0 POL(g_flat(x_1)) = 0 POL(u(x_1)) = 0 POL(u_flat(x_1)) = 0 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: u_flat(up(x_1)) -> up(u(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) ---------------------------------------- (113) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (114) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (115) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (116) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (117) Complex Obligation (AND) ---------------------------------------- (118) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) b_flat(up(x_1)) -> up(b(x_1)) g_flat(up(x_1)) -> up(g(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (119) SemLabProof (SOUND) We found the following model for the rules of the TRSs R and P. Interpretation over the domain with elements from 0 to 1. c: 0 TOP: 0 u: 0 g: 0 b: 0 down: 0 f: 0 fresh_constant: 1 up: 0 u_flat: 0 f_flat: 0 b_flat: 0 g_flat: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (120) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(u.1(x0))) -> TOP.0(u_flat.0(down.1(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(g.1(x0))) -> TOP.0(g_flat.0(down.1(x0))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) TOP.0(up.0(b.0(g.1(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.1(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(f.0(f.0(f.1(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (121) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (122) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(f.0(f.0(f.1(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (123) UsableRulesReductionPairsProof (EQUIVALENT) 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. No dependency pairs are removed. The following rules are removed from R: f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = 1 + x_1 POL(b.1(x_1)) = 1 + x_1 POL(b_flat.0(x_1)) = 1 + x_1 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = 1 + x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(f.0(f.0(f.1(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (125) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(f.0(f.0(f.1(x)))) -> up.0(c.) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = 1 + x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = 1 + x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = 1 + x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = 1 + x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 ---------------------------------------- (126) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (127) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (128) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (129) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = 1 + x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 ---------------------------------------- (130) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (131) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = 1 + x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 ---------------------------------------- (132) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(c.)) -> b_flat.0(down.0(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (133) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (134) TRUE ---------------------------------------- (135) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) b_flat(up(x_1)) -> up(b(x_1)) f_flat(up(x_1)) -> up(f(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (136) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (137) Complex Obligation (AND) ---------------------------------------- (138) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(f(c)) -> f_flat(down(c)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) b_flat(up(x_1)) -> up(b(x_1)) f_flat(up(x_1)) -> up(f(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (139) SemLabProof (SOUND) We found the following model for the rules of the TRSs R and P. Interpretation over the domain with elements from 0 to 1. c: 1 TOP: 0 u: 0 g: 0 b: 0 down: 0 f: 0 fresh_constant: 0 up: 0 u_flat: 0 f_flat: 0 b_flat: 0 g_flat: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (140) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(u.1(x0))) -> TOP.0(u_flat.0(down.1(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) TOP.0(up.0(b.0(g.1(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.1(x0)))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(g.1(x0))) -> TOP.0(g_flat.0(down.1(x0))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.1(c.) down.0(f.0(f.0(f.1(x)))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.1(c.)) -> f_flat.0(down.1(c.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.1(c.)) -> b_flat.0(down.1(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.1(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.0(fresh_constant.)) down.0(f.0(f.1(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.0(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (141) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (142) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.1(c.) down.0(f.0(f.0(f.1(x)))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.1(c.)) -> f_flat.0(down.1(c.)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.1(c.)) -> b_flat.0(down.1(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.1(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.0(fresh_constant.)) down.0(f.0(f.1(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.0(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (143) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(f.1(c.)) -> f_flat.0(down.1(c.)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = 1 + x_1 POL(b.1(x_1)) = x_1 POL(b_flat.0(x_1)) = 1 + x_1 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (144) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(f.1(x0)))) TOP.0(up.0(b.0(f.1(x0)))) -> TOP.0(b_flat.0(down.0(f.1(x0)))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.1(c.) down.0(f.0(f.0(f.1(x)))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.1(c.)) -> b_flat.0(down.1(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.1(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.0(fresh_constant.)) down.0(f.0(f.1(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.0(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (145) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (146) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.1(c.) down.0(f.0(f.0(f.1(x)))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.1(c.)) -> b_flat.0(down.1(c.)) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.1(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.0(fresh_constant.)) down.0(f.0(f.1(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.0(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (147) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(b.1(c.)) -> b_flat.0(down.1(c.)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (148) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.1(c.) down.0(f.0(f.0(f.1(x)))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.1(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.0(fresh_constant.)) down.0(f.0(f.1(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.0(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (149) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (150) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.1(c.) down.0(f.0(f.0(f.1(x)))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.0(f.0(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(f.1(y10))) -> b_flat.0(down.0(f.1(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.0(f.0(f.0(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.0(f.1(x0))) down.0(b.1(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.0(fresh_constant.)) down.0(f.0(f.1(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.0(f.0(f.0(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (151) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (152) TRUE ---------------------------------------- (153) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) b_flat(up(x_1)) -> up(b(x_1)) f_flat(up(x_1)) -> up(f(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (154) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (155) Complex Obligation (AND) ---------------------------------------- (156) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) b_flat(up(x_1)) -> up(b(x_1)) f_flat(up(x_1)) -> up(f(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (157) SemLabProof (SOUND) We found the following model for the rules of the TRSs R and P. Interpretation over the domain with elements from 0 to 1. c: 0 TOP: 0 u: 0 g: 0 b: 0 down: 0 f: x0 fresh_constant: 1 up: 0 u_flat: 0 b_flat: 0 f_flat: 0 g_flat: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (158) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.1(f.1(x0)))) -> TOP.0(b_flat.0(down.1(f.1(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.1(f.1(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(u.1(x0))) -> TOP.0(u_flat.0(down.1(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) TOP.0(up.0(b.0(g.1(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.1(x0)))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(g.1(x0))) -> TOP.0(g_flat.0(down.1(x0))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.1(f.1(f.1(f.1(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(b.0(u.1(x))) -> up.0(b.1(f.1(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.1(f.1(y10))) -> b_flat.0(down.1(f.1(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (159) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.1(f.1(x0)))) TOP.0(up.0(u.1(x0))) -> TOP.0(u_flat.0(down.1(x0))) TOP.0(up.0(b.0(g.1(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.1(x0)))) TOP.0(up.0(g.1(x0))) -> TOP.0(g_flat.0(down.1(x0))) Strictly oriented rules of the TRS R: down.0(b.0(u.1(x))) -> up.0(b.1(f.1(x))) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(g.1(y3)) -> g_flat.0(down.1(y3)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = 1 + x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = 1 + x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (160) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.1(f.1(x0)))) -> TOP.0(b_flat.0(down.1(f.1(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.1(f.1(f.1(f.1(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.1(f.1(y10))) -> b_flat.0(down.1(f.1(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (161) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (162) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.1(f.1(f.1(f.1(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.1(f.1(y10))) -> b_flat.0(down.1(f.1(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (163) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.1(f.1(f.1(f.1(x)))) -> up.0(c.) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = 1 + x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = 1 + x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (164) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.1(f.1(y10))) -> b_flat.0(down.1(f.1(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (165) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(b.1(f.1(y10))) -> b_flat.0(down.1(f.1(y10))) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = 1 + x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (166) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(b.1(x0)))) -> TOP.0(b_flat.0(down.0(b.1(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (167) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (168) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (169) UsableRulesReductionPairsProof (EQUIVALENT) 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. No dependency pairs are removed. The following rules are removed from R: down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.))) Used ordering: POLO with Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(b.0(x_1)) = x_1 POL(b.1(x_1)) = x_1 POL(b_flat.0(x_1)) = x_1 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(u.0(x_1)) = x_1 POL(u.1(x_1)) = x_1 POL(u_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (170) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(f.0(x0)))) TOP.0(up.0(b.0(f.0(x0)))) -> TOP.0(b_flat.0(down.0(f.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(g.0(x0))) -> TOP.0(g_flat.0(down.0(x0))) TOP.0(up.0(b.0(b.0(x0)))) -> TOP.0(b_flat.0(down.0(b.0(x0)))) TOP.0(up.0(b.0(g.0(x0)))) -> TOP.0(b_flat.0(g_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(f.0(f.0(f.0(x)))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(f.0(x))) down.0(f.0(g.0(x))) -> up.0(f.0(f.0(x))) down.0(f.0(g.1(x))) -> up.1(f.1(f.1(x))) down.0(f.0(b.0(x))) -> up.0(u.0(g.0(b.0(x)))) down.0(f.0(b.1(x))) -> up.0(u.0(g.0(b.1(x)))) down.0(f.0(u.0(x))) -> up.0(u.0(g.0(x))) down.0(f.0(u.1(x))) -> up.0(u.0(g.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(g.0(y3)) -> g_flat.0(down.0(y3)) down.0(b.0(f.0(y10))) -> b_flat.0(down.0(f.0(y10))) down.0(b.0(b.0(y11))) -> b_flat.0(down.0(b.0(y11))) down.0(b.0(b.1(y11))) -> b_flat.0(down.0(b.1(y11))) down.0(b.0(g.0(y13))) -> b_flat.0(down.0(g.0(y13))) down.0(b.0(g.1(y13))) -> b_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.))) down.0(f.0(f.0(b.0(y16)))) -> f_flat.0(down.0(f.0(b.0(y16)))) down.0(f.0(f.0(b.1(y16)))) -> f_flat.0(down.0(f.0(b.1(y16)))) down.0(f.0(f.0(u.0(y17)))) -> f_flat.0(down.0(f.0(u.0(y17)))) down.0(f.0(f.0(u.1(y17)))) -> f_flat.0(down.0(f.0(u.1(y17)))) down.0(f.0(f.0(g.0(y18)))) -> f_flat.0(down.0(f.0(g.0(y18)))) down.0(f.0(f.0(g.1(y18)))) -> f_flat.0(down.0(f.0(g.1(y18)))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.1(f.1(x_1)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) u_flat.0(up.1(x_1)) -> up.0(u.1(x_1)) The set Q consists of the following terms: down.0(f.0(f.0(f.0(x0)))) down.1(f.1(f.1(f.1(x0)))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(b.0(x0))) down.0(f.0(b.1(x0))) down.0(f.0(u.0(x0))) down.0(f.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(g.0(x0)) down.0(g.1(x0)) down.0(f.0(c.)) down.1(f.1(fresh_constant.)) down.0(b.0(f.0(x0))) down.0(b.1(f.1(x0))) down.0(b.0(c.)) down.0(b.0(b.0(x0))) down.0(b.0(b.1(x0))) down.0(b.0(g.0(x0))) down.0(b.0(g.1(x0))) down.0(b.1(fresh_constant.)) down.0(f.0(f.0(c.))) down.0(f.0(f.0(b.0(x0)))) down.0(f.0(f.0(b.1(x0)))) down.0(f.0(f.0(u.0(x0)))) down.0(f.0(f.0(u.1(x0)))) down.0(f.0(f.0(g.0(x0)))) down.0(f.0(f.0(g.1(x0)))) down.1(f.1(f.1(fresh_constant.))) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) b_flat.0(up.0(x0)) b_flat.0(up.1(x0)) u_flat.0(up.0(x0)) u_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (171) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (172) TRUE ---------------------------------------- (173) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) g_flat(up(x_1)) -> up(g(x_1)) b_flat(up(x_1)) -> up(b(x_1)) f_flat(up(x_1)) -> up(f(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(f(fresh_constant)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(b(fresh_constant)) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) down(f(f(fresh_constant))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (174) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. down(f(fresh_constant)) down(b(fresh_constant)) down(f(f(fresh_constant))) ---------------------------------------- (175) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(f(x0)))) TOP(up(b(f(x0)))) -> TOP(b_flat(down(f(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(g(x0))) -> TOP(g_flat(down(x0))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(g(x0)))) -> TOP(b_flat(g_flat(down(x0)))) The TRS R consists of the following rules: down(f(f(f(x)))) -> up(c) down(b(u(x))) -> up(b(f(x))) down(f(g(x))) -> up(f(f(x))) down(f(b(x))) -> up(u(g(b(x)))) down(f(u(x))) -> up(u(g(x))) down(u(y2)) -> u_flat(down(y2)) down(g(y3)) -> g_flat(down(y3)) down(b(f(y10))) -> b_flat(down(f(y10))) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(g(y13))) -> b_flat(down(g(y13))) down(f(f(c))) -> f_flat(down(f(c))) down(f(f(b(y16)))) -> f_flat(down(f(b(y16)))) down(f(f(u(y17)))) -> f_flat(down(f(u(y17)))) down(f(f(g(y18)))) -> f_flat(down(f(g(y18)))) g_flat(up(x_1)) -> up(g(x_1)) b_flat(up(x_1)) -> up(b(x_1)) f_flat(up(x_1)) -> up(f(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(f(f(f(x0)))) down(b(u(x0))) down(f(g(x0))) down(f(b(x0))) down(f(u(x0))) down(u(x0)) down(g(x0)) down(f(c)) down(b(f(x0))) down(b(c)) down(b(b(x0))) down(b(g(x0))) down(f(f(c))) down(f(f(b(x0)))) down(f(f(u(x0)))) down(f(f(g(x0)))) f_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) g_flat(up(x0)) We have to consider all (P,Q,R)-chains.