/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, 20 ms] (13) QDP (14) UsableRulesProof [EQUIVALENT, 0 ms] (15) QDP (16) QReductionProof [EQUIVALENT, 0 ms] (17) QDP (18) UsableRulesReductionPairsProof [EQUIVALENT, 7 ms] (19) QDP (20) DependencyGraphProof [EQUIVALENT, 0 ms] (21) QDP (22) QReductionProof [EQUIVALENT, 0 ms] (23) QDP (24) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (25) QDP (26) DependencyGraphProof [EQUIVALENT, 0 ms] (27) TRUE (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) QDP (37) QReductionProof [EQUIVALENT, 0 ms] (38) QDP (39) Trivial-Transformation [SOUND, 0 ms] (40) QTRS (41) DependencyPairsProof [EQUIVALENT, 0 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) AND (45) QDP (46) UsableRulesProof [EQUIVALENT, 0 ms] (47) QDP (48) QDPSizeChangeProof [EQUIVALENT, 0 ms] (49) YES (50) QDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) QDP (53) QDPSizeChangeProof [EQUIVALENT, 0 ms] (54) YES (55) QDP (56) TransformationProof [EQUIVALENT, 0 ms] (57) QDP (58) QDPOrderProof [EQUIVALENT, 5 ms] (59) QDP (60) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (61) QTRS (62) AAECC Innermost [EQUIVALENT, 25 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, 1 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) QDPOrderProof [EQUIVALENT, 11 ms] (87) QDP (88) QDPOrderProof [EQUIVALENT, 14 ms] (89) QDP (90) MNOCProof [EQUIVALENT, 0 ms] (91) QDP (92) SplitQDPProof [EQUIVALENT, 0 ms] (93) AND (94) QDP (95) SemLabProof [SOUND, 0 ms] (96) QDP (97) DependencyGraphProof [EQUIVALENT, 0 ms] (98) QDP (99) UsableRulesReductionPairsProof [EQUIVALENT, 11 ms] (100) QDP (101) MRRProof [EQUIVALENT, 0 ms] (102) QDP (103) DependencyGraphProof [EQUIVALENT, 0 ms] (104) QDP (105) MRRProof [EQUIVALENT, 6 ms] (106) QDP (107) MRRProof [EQUIVALENT, 0 ms] (108) QDP (109) PisEmptyProof [SOUND, 0 ms] (110) TRUE (111) QDP (112) QReductionProof [EQUIVALENT, 0 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) MRRProof [EQUIVALENT, 0 ms] (124) QDP (125) DependencyGraphProof [EQUIVALENT, 0 ms] (126) QDP (127) MRRProof [EQUIVALENT, 0 ms] (128) QDP (129) MRRProof [EQUIVALENT, 0 ms] (130) QDP (131) PisEmptyProof [SOUND, 0 ms] (132) TRUE (133) QDP (134) QReductionProof [EQUIVALENT, 0 ms] (135) QDP ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) redex_a(a(x)) -> result_a(c) redex_b(u(x)) -> result_b(b(d(x))) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_d(result_d(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(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_d_1(go_up(x_1)) -> go_up(d(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_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(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(a(x_1)) -> REDEX_A(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) REDUCE(b(x_1)) -> REDEX_B(x_1) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) REDUCE(d(x_1)) -> REDEX_D(x_1) CHECK_A(redex_a(x_1)) -> IN_A_1(reduce(x_1)) CHECK_A(redex_a(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) CHECK_D(redex_d(x_1)) -> IN_D_1(reduce(x_1)) CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> IN_U_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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) redex_a(a(x)) -> result_a(c) redex_b(u(x)) -> result_b(b(d(x))) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_d(result_d(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(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_d_1(go_up(x_1)) -> go_up(d(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_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 2 SCCs with 8 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) CHECK_D(redex_d(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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) redex_a(a(x)) -> result_a(c) redex_b(u(x)) -> result_b(b(d(x))) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_d(result_d(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(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_d_1(go_up(x_1)) -> go_up(d(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_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_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) redex_b(u(x)) -> result_b(b(d(x))) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_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(a(x0)) reduce(b(x0)) reduce(d(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) redex_b(u(x)) -> result_b(b(d(x))) The set Q consists of the following terms: redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(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 dependency pairs: REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(u(x_1)) -> REDUCE(x_1) Strictly oriented rules of the TRS R: redex_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_A(x_1)) = x_1 POL(CHECK_B(x_1)) = 1 + 2*x_1 POL(CHECK_D(x_1)) = x_1 POL(REDUCE(x_1)) = 1 + 2*x_1 POL(a(x_1)) = x_1 POL(b(x_1)) = x_1 POL(c) = 0 POL(d(x_1)) = 2 + x_1 POL(redex_a(x_1)) = 1 + 2*x_1 POL(redex_b(x_1)) = x_1 POL(redex_d(x_1)) = 2 + 2*x_1 POL(result_a(x_1)) = 2*x_1 POL(result_b(x_1)) = x_1 POL(result_d(x_1)) = x_1 POL(u(x_1)) = 2 + 2*x_1 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) The TRS R consists of the following rules: redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_b(u(x)) -> result_b(b(d(x))) The set Q consists of the following terms: redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) 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. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) The TRS R consists of the following rules: redex_b(u(x)) -> result_b(b(d(x))) The set Q consists of the following terms: redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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]. redex_d(a(x0)) redex_d(b(x0)) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) The TRS R consists of the following rules: redex_b(u(x)) -> result_b(b(d(x))) The set Q consists of the following terms: redex_a(a(x0)) redex_b(u(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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(a(x_1)) -> CHECK_A(redex_a(x_1)) The following rules are removed from R: redex_b(u(x)) -> result_b(b(d(x))) Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_A(x_1)) = 2*x_1 POL(CHECK_B(x_1)) = x_1 POL(REDUCE(x_1)) = 2*x_1 POL(a(x_1)) = 2*x_1 POL(b(x_1)) = 2*x_1 POL(d(x_1)) = 2*x_1 POL(redex_a(x_1)) = x_1 POL(redex_b(x_1)) = 2*x_1 POL(result_b(x_1)) = x_1 POL(u(x_1)) = 2*x_1 ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) 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_a(a(x0)) redex_b(u(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) R is empty. The set Q consists of the following terms: redex_a(a(x0)) redex_b(u(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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]. redex_a(a(x0)) redex_a(u(x0)) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(b(x_1)) -> CHECK_B(redex_b(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. ---------------------------------------- (24) 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 ---------------------------------------- (25) 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. ---------------------------------------- (26) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (27) TRUE ---------------------------------------- (28) 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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) redex_a(a(x)) -> result_a(c) redex_b(u(x)) -> result_b(b(d(x))) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_b(result_b(x)) -> go_up(x) check_d(result_d(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) check_b(redex_b(x_1)) -> in_b_1(reduce(x_1)) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(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_d_1(go_up(x_1)) -> go_up(d(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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. ---------------------------------------- (30) 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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) check_d(result_d(x)) -> go_up(x) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) in_d_1(go_up(x_1)) -> go_up(d(x_1)) redex_b(u(x)) -> result_b(b(d(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_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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)) ---------------------------------------- (32) 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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) check_d(result_d(x)) -> go_up(x) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) in_d_1(go_up(x_1)) -> go_up(d(x_1)) redex_b(u(x)) -> result_b(b(d(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_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(x_1)) The set Q consists of the following terms: reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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(a(x0))) -> TOP(check_a(redex_a(x0))),TOP(go_up(a(x0))) -> TOP(check_a(redex_a(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(d(x0))) -> TOP(check_d(redex_d(x0))),TOP(go_up(d(x0))) -> TOP(check_d(redex_d(x0)))) (TOP(go_up(u(x0))) -> TOP(in_u_1(reduce(x0))),TOP(go_up(u(x0))) -> TOP(in_u_1(reduce(x0)))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(a(x0))) -> TOP(check_a(redex_a(x0))) TOP(go_up(b(x0))) -> TOP(check_b(redex_b(x0))) TOP(go_up(d(x0))) -> TOP(check_d(redex_d(x0))) TOP(go_up(u(x0))) -> TOP(in_u_1(reduce(x0))) The TRS R consists of the following rules: reduce(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) check_d(result_d(x)) -> go_up(x) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) in_d_1(go_up(x_1)) -> go_up(d(x_1)) redex_b(u(x)) -> result_b(b(d(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_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(x_1)) The set Q consists of the following terms: reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) 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. ---------------------------------------- (36) 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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) check_d(result_d(x)) -> go_up(x) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) in_d_1(go_up(x_1)) -> go_up(d(x_1)) redex_b(u(x)) -> result_b(b(d(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_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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)) ---------------------------------------- (38) 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(a(x_1)) -> check_a(redex_a(x_1)) reduce(b(x_1)) -> check_b(redex_b(x_1)) reduce(d(x_1)) -> check_d(redex_d(x_1)) reduce(u(x_1)) -> in_u_1(reduce(x_1)) in_u_1(go_up(x_1)) -> go_up(u(x_1)) redex_d(a(x)) -> result_d(a(d(x))) redex_d(b(x)) -> result_d(u(a(b(x)))) check_d(result_d(x)) -> go_up(x) check_d(redex_d(x_1)) -> in_d_1(reduce(x_1)) in_d_1(go_up(x_1)) -> go_up(d(x_1)) redex_b(u(x)) -> result_b(b(d(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_a(a(x)) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) check_a(result_a(x)) -> go_up(x) check_a(redex_a(x_1)) -> in_a_1(reduce(x_1)) in_a_1(go_up(x_1)) -> go_up(a(x_1)) The set Q consists of the following terms: reduce(a(x0)) reduce(b(x0)) reduce(d(x0)) redex_a(a(x0)) redex_b(u(x0)) redex_d(a(x0)) redex_d(b(x0)) redex_a(u(x0)) check_a(result_a(x0)) check_b(result_b(x0)) check_d(result_d(x0)) check_a(redex_a(x0)) check_b(redex_b(x0)) check_d(redex_d(x0)) reduce(u(x0)) in_a_1(go_up(x0)) in_b_1(go_up(x0)) in_u_1(go_up(x0)) in_d_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) Trivial-Transformation (SOUND) We applied the Trivial transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (40) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(x)) Q is empty. ---------------------------------------- (41) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(x)) -> B(d(x)) B(u(x)) -> D(x) D(a(x)) -> A(d(x)) D(a(x)) -> D(x) D(b(x)) -> A(b(x)) A(u(x)) -> A(x) The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 3 less nodes. ---------------------------------------- (44) Complex Obligation (AND) ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: A(u(x)) -> A(x) The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) 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. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: A(u(x)) -> A(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) 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: *A(u(x)) -> A(x) The graph contains the following edges 1 > 1 ---------------------------------------- (49) YES ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: D(a(x)) -> D(x) The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) 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. ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: D(a(x)) -> D(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) 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: *D(a(x)) -> D(x) The graph contains the following edges 1 > 1 ---------------------------------------- (54) YES ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(x)) -> B(d(x)) The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule B(u(x)) -> B(d(x)) at position [0] we obtained the following new rules [LPAR04]: (B(u(a(x0))) -> B(a(d(x0))),B(u(a(x0))) -> B(a(d(x0)))) (B(u(b(x0))) -> B(u(a(b(x0)))),B(u(b(x0))) -> B(u(a(b(x0))))) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(a(x0))) -> B(a(d(x0))) B(u(b(x0))) -> B(u(a(b(x0)))) The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(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(b(x0))) -> B(u(a(b(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(B(x_1)) = x_1 POL(a(x_1)) = 0 POL(b(x_1)) = 1 + x_1 POL(c) = 0 POL(d(x_1)) = x_1 POL(u(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: a(a(x)) -> c a(u(x)) -> u(a(x)) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: B(u(a(x0))) -> B(a(d(x0))) The TRS R consists of the following rules: a(a(x)) -> c b(u(x)) -> b(d(x)) d(a(x)) -> a(d(x)) d(b(x)) -> u(a(b(x))) a(u(x)) -> u(a(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(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) a_flat(up(x_1)) -> up(a(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(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(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) a_flat(up(x_1)) -> up(a(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(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(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) a_flat(up(x_1)) -> up(a(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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(a(c)) -> A_FLAT(down(c)) DOWN(a(c)) -> DOWN(c) DOWN(a(b(y6))) -> A_FLAT(down(b(y6))) DOWN(a(b(y6))) -> DOWN(b(y6)) DOWN(a(d(y8))) -> A_FLAT(down(d(y8))) DOWN(a(d(y8))) -> DOWN(d(y8)) DOWN(a(fresh_constant)) -> A_FLAT(down(fresh_constant)) DOWN(a(fresh_constant)) -> DOWN(fresh_constant) DOWN(b(a(y10))) -> B_FLAT(down(a(y10))) DOWN(b(a(y10))) -> DOWN(a(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(d(y13))) -> B_FLAT(down(d(y13))) DOWN(b(d(y13))) -> DOWN(d(y13)) DOWN(b(fresh_constant)) -> B_FLAT(down(fresh_constant)) DOWN(b(fresh_constant)) -> DOWN(fresh_constant) DOWN(d(c)) -> D_FLAT(down(c)) DOWN(d(c)) -> DOWN(c) DOWN(d(u(y17))) -> D_FLAT(down(u(y17))) DOWN(d(u(y17))) -> DOWN(u(y17)) DOWN(d(d(y18))) -> D_FLAT(down(d(y18))) DOWN(d(d(y18))) -> DOWN(d(y18)) DOWN(d(fresh_constant)) -> D_FLAT(down(fresh_constant)) DOWN(d(fresh_constant)) -> DOWN(fresh_constant) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) a_flat(up(x_1)) -> up(a(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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 21 less nodes. ---------------------------------------- (67) Complex Obligation (AND) ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(a(b(y6))) -> DOWN(b(y6)) DOWN(b(a(y10))) -> DOWN(a(y10)) DOWN(a(d(y8))) -> DOWN(d(y8)) DOWN(d(u(y17))) -> DOWN(u(y17)) DOWN(u(y2)) -> DOWN(y2) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(d(y13))) -> DOWN(d(y13)) DOWN(d(d(y18))) -> DOWN(d(y18)) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) a_flat(up(x_1)) -> up(a(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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(a(b(y6))) -> DOWN(b(y6)) DOWN(b(a(y10))) -> DOWN(a(y10)) DOWN(a(d(y8))) -> DOWN(d(y8)) DOWN(d(u(y17))) -> DOWN(u(y17)) DOWN(u(y2)) -> DOWN(y2) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(d(y13))) -> DOWN(d(y13)) DOWN(d(d(y18))) -> DOWN(d(y18)) R is empty. The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(a(b(y6))) -> DOWN(b(y6)) DOWN(b(a(y10))) -> DOWN(a(y10)) DOWN(a(d(y8))) -> DOWN(d(y8)) DOWN(d(u(y17))) -> DOWN(u(y17)) DOWN(u(y2)) -> DOWN(y2) DOWN(b(b(y11))) -> DOWN(b(y11)) DOWN(b(d(y13))) -> DOWN(d(y13)) DOWN(d(d(y18))) -> DOWN(d(y18)) 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(a(y10))) -> DOWN(a(y10)) The graph contains the following edges 1 > 1 *DOWN(u(y2)) -> DOWN(y2) The graph contains the following edges 1 > 1 *DOWN(b(b(y11))) -> DOWN(b(y11)) The graph contains the following edges 1 > 1 *DOWN(b(d(y13))) -> DOWN(d(y13)) The graph contains the following edges 1 > 1 *DOWN(a(b(y6))) -> DOWN(b(y6)) The graph contains the following edges 1 > 1 *DOWN(a(d(y8))) -> DOWN(d(y8)) The graph contains the following edges 1 > 1 *DOWN(d(d(y18))) -> DOWN(d(y18)) The graph contains the following edges 1 > 1 *DOWN(d(u(y17))) -> DOWN(u(y17)) 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(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) top(up(x)) -> top(down(x)) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) a_flat(up(x_1)) -> up(a(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) top(up(x0)) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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(a(a(x0)))) -> TOP(up(c)),TOP(up(a(a(x0)))) -> TOP(up(c))) (TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))),TOP(up(b(u(x0)))) -> TOP(up(b(d(x0))))) (TOP(up(d(a(x0)))) -> TOP(up(a(d(x0)))),TOP(up(d(a(x0)))) -> TOP(up(a(d(x0))))) (TOP(up(d(b(x0)))) -> TOP(up(u(a(b(x0))))),TOP(up(d(b(x0)))) -> TOP(up(u(a(b(x0)))))) (TOP(up(a(u(x0)))) -> TOP(up(u(a(x0)))),TOP(up(a(u(x0)))) -> TOP(up(u(a(x0))))) (TOP(up(u(x0))) -> TOP(u_flat(down(x0))),TOP(up(u(x0))) -> TOP(u_flat(down(x0)))) (TOP(up(a(c))) -> TOP(a_flat(down(c))),TOP(up(a(c))) -> TOP(a_flat(down(c)))) (TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))),TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0))))) (TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))),TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0))))) (TOP(up(a(fresh_constant))) -> TOP(a_flat(down(fresh_constant))),TOP(up(a(fresh_constant))) -> TOP(a_flat(down(fresh_constant)))) (TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))),TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(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(d(x0)))) -> TOP(b_flat(down(d(x0)))),TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(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(d(c))) -> TOP(d_flat(down(c))),TOP(up(d(c))) -> TOP(d_flat(down(c)))) (TOP(up(d(u(x0)))) -> TOP(d_flat(down(u(x0)))),TOP(up(d(u(x0)))) -> TOP(d_flat(down(u(x0))))) (TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))),TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0))))) (TOP(up(d(fresh_constant))) -> TOP(d_flat(down(fresh_constant))),TOP(up(d(fresh_constant))) -> TOP(d_flat(down(fresh_constant)))) ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(a(a(x0)))) -> TOP(up(c)) TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(d(a(x0)))) -> TOP(up(a(d(x0)))) TOP(up(d(b(x0)))) -> TOP(up(u(a(b(x0))))) TOP(up(a(u(x0)))) -> TOP(up(u(a(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(c))) -> TOP(a_flat(down(c))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(a(fresh_constant))) -> TOP(a_flat(down(fresh_constant))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(c))) -> TOP(b_flat(down(c))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(fresh_constant))) -> TOP(b_flat(down(fresh_constant))) TOP(up(d(c))) -> TOP(d_flat(down(c))) TOP(up(d(u(x0)))) -> TOP(d_flat(down(u(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(fresh_constant))) -> TOP(d_flat(down(fresh_constant))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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 7 less nodes. ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(d(a(x0)))) -> TOP(up(a(d(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(d(b(x0)))) -> TOP(up(u(a(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(u(x0)))) -> TOP(up(u(a(x0)))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(down(u(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(d(u(x0)))) -> TOP(d_flat(down(u(x0)))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))),TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0))))) ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(d(a(x0)))) -> TOP(up(a(d(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(d(b(x0)))) -> TOP(up(u(a(b(x0))))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(u(x0)))) -> TOP(up(u(a(x0)))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(d(b(x0)))) -> TOP(up(u(a(b(x0))))) TOP(up(a(u(x0)))) -> TOP(up(u(a(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(a(x_1)) = 1 POL(a_flat(x_1)) = 1 POL(b(x_1)) = 0 POL(b_flat(x_1)) = 0 POL(c) = 0 POL(d(x_1)) = 1 POL(d_flat(x_1)) = 1 POL(down(x_1)) = 0 POL(fresh_constant) = 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: b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(d(a(x0)))) -> TOP(up(a(d(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(d(a(x0)))) -> TOP(up(a(d(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(a(x_1)) = 0 POL(a_flat(x_1)) = 0 POL(b(x_1)) = 0 POL(b_flat(x_1)) = 0 POL(c) = 0 POL(d(x_1)) = 1 POL(d_flat(x_1)) = 1 POL(down(x_1)) = 0 POL(fresh_constant) = 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: b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (92) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (93) Complex Obligation (AND) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(a(fresh_constant)) -> a_flat(down(fresh_constant)) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(b(fresh_constant)) -> b_flat(down(fresh_constant)) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) down(d(fresh_constant)) -> d_flat(down(fresh_constant)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) 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. a: 0 c: 0 TOP: 0 u: 0 b: 0 d: 0 down: 0 d_flat: 0 fresh_constant: 1 up: 0 u_flat: 0 b_flat: 0 a_flat: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (96) 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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.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(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) TOP.0(up.0(d.0(u.1(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.1(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(a.0(a.1(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.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(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(a.1(fresh_constant.)) -> a_flat.0(down.1(fresh_constant.)) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) down.0(d.1(fresh_constant.)) -> d_flat.0(down.1(fresh_constant.)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.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)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.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(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(d.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.1(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(a.0(a.1(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.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(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(a.1(fresh_constant.)) -> a_flat.0(down.1(fresh_constant.)) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) down.0(d.1(fresh_constant.)) -> d_flat.0(down.1(fresh_constant.)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.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)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.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(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (99) 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: d_flat.0(up.1(x_1)) -> up.0(d.1(x_1)) b_flat.0(up.1(x_1)) -> up.0(b.1(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.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(a.0(x_1)) = x_1 POL(a.1(x_1)) = x_1 POL(a_flat.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(d.0(x_1)) = 1 + x_1 POL(d.1(x_1)) = 1 + x_1 POL(d_flat.0(x_1)) = 1 + x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(fresh_constant.) = 0 POL(u.0(x_1)) = 1 + x_1 POL(u.1(x_1)) = 1 + x_1 POL(u_flat.0(x_1)) = 1 + x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(d.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.1(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(a.0(a.1(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.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(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(a.1(fresh_constant.)) -> a_flat.0(down.1(fresh_constant.)) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) down.0(d.1(fresh_constant.)) -> d_flat.0(down.1(fresh_constant.)) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (101) 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(a.1(fresh_constant.)) -> a_flat.0(down.1(fresh_constant.)) down.0(b.1(fresh_constant.)) -> b_flat.0(down.1(fresh_constant.)) down.0(d.1(fresh_constant.)) -> d_flat.0(down.1(fresh_constant.)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.0(x_1)) = x_1 POL(a.1(x_1)) = x_1 POL(a_flat.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(d.0(x_1)) = x_1 POL(d.1(x_1)) = x_1 POL(d_flat.0(x_1)) = x_1 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = x_1 POL(fresh_constant.) = 0 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 ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(d.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.1(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(a.0(a.1(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (103) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. ---------------------------------------- (104) 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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(a.0(a.1(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (105) 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(a.0(a.1(x))) -> up.0(c.) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.0(x_1)) = x_1 POL(a.1(x_1)) = 1 + x_1 POL(a_flat.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(d.0(x_1)) = x_1 POL(d.1(x_1)) = x_1 POL(d_flat.0(x_1)) = x_1 POL(down.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 ---------------------------------------- (106) 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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (107) 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(a.0(u.1(x))) -> up.0(u.0(a.1(x))) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.0(x_1)) = x_1 POL(a.1(x_1)) = x_1 POL(a_flat.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(d.0(x_1)) = x_1 POL(d.1(x_1)) = x_1 POL(d_flat.0(x_1)) = x_1 POL(down.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 ---------------------------------------- (108) 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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.0(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(c.)) -> a_flat.0(down.0(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(c.)) -> d_flat.0(down.0(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.0(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.1(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.1(fresh_constant.)) down.0(d.0(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.1(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (110) TRUE ---------------------------------------- (111) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (112) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. down(a(fresh_constant)) down(b(fresh_constant)) down(d(fresh_constant)) ---------------------------------------- (113) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(d(c)) down(d(u(x0))) down(d(d(x0))) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all (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(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(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(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(c)) -> a_flat(down(c)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(c)) -> b_flat(down(c)) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(d(c)) -> d_flat(down(c)) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_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. a: 0 c: 1 TOP: 0 u: 0 b: 0 d: 0 down: 0 fresh_constant: 0 d_flat: 0 up: 0 u_flat: 0 b_flat: 0 a_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(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.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(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) TOP.0(up.0(d.0(u.1(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.1(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.1(c.) down.0(a.0(a.1(x))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.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(a.1(c.)) -> a_flat.0(down.1(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.1(c.)) -> d_flat.0(down.1(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) 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)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.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)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.1(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.0(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.0(fresh_constant.)) down.0(d.1(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.0(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_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 2 less nodes. ---------------------------------------- (122) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(d.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.1(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.1(c.) down.0(a.0(a.1(x))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.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(a.1(c.)) -> a_flat.0(down.1(c.)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.1(c.)) -> d_flat.0(down.1(c.)) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) 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)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.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)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.1(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.0(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.0(fresh_constant.)) down.0(d.1(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.0(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (123) 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(a.1(c.)) -> a_flat.0(down.1(c.)) down.0(b.1(c.)) -> b_flat.0(down.1(c.)) down.0(d.1(c.)) -> d_flat.0(down.1(c.)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.0(x_1)) = x_1 POL(a.1(x_1)) = x_1 POL(a_flat.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(d.0(x_1)) = x_1 POL(d.1(x_1)) = x_1 POL(d_flat.0(x_1)) = x_1 POL(down.0(x_1)) = 1 + x_1 POL(down.1(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(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(d.0(x0)))) TOP.0(up.0(b.0(u.1(x0)))) -> TOP.0(up.0(b.0(d.1(x0)))) TOP.0(up.0(b.0(d.1(x0)))) -> TOP.0(b_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(b.1(x0)))) -> TOP.0(a_flat.0(down.0(b.1(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(a.0(d.1(x0)))) -> TOP.0(a_flat.0(down.0(d.1(x0)))) TOP.0(up.0(b.0(a.1(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(d.1(x0)))) -> TOP.0(d_flat.0(down.0(d.1(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.1(c.) down.0(a.0(a.1(x))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) 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)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.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)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.1(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.0(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.0(fresh_constant.)) down.0(d.1(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.0(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (125) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. ---------------------------------------- (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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.1(c.) down.0(a.0(a.1(x))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) 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)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.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)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.1(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.0(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.0(fresh_constant.)) down.0(d.1(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.0(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (127) 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: 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(a.0(x_1)) = x_1 POL(a.1(x_1)) = x_1 POL(a_flat.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(d.0(x_1)) = x_1 POL(d.1(x_1)) = x_1 POL(d_flat.0(x_1)) = x_1 POL(down.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 ---------------------------------------- (128) 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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.1(c.) down.0(a.0(a.1(x))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(b.0(u.1(x))) -> up.0(b.0(d.1(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) 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)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) d_flat.0(up.1(x_1)) -> up.0(d.1(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.1(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.0(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.0(fresh_constant.)) down.0(d.1(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.0(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_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(d.1(x))) down.0(d.0(a.1(x))) -> up.0(a.0(d.1(x))) d_flat.0(up.1(x_1)) -> up.0(d.1(x_1)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.0(x_1)) = x_1 POL(a.1(x_1)) = x_1 POL(a_flat.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(d.0(x_1)) = 1 + x_1 POL(d.1(x_1)) = x_1 POL(d_flat.0(x_1)) = 1 + x_1 POL(down.0(x_1)) = x_1 POL(u.0(x_1)) = 1 + x_1 POL(u.1(x_1)) = 1 + x_1 POL(u_flat.0(x_1)) = 1 + x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (130) 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(d.0(x0)))) TOP.0(up.0(b.0(d.0(x0)))) -> TOP.0(b_flat.0(down.0(d.0(x0)))) TOP.0(up.0(u.0(x0))) -> TOP.0(u_flat.0(down.0(x0))) TOP.0(up.0(a.0(b.0(x0)))) -> TOP.0(a_flat.0(down.0(b.0(x0)))) TOP.0(up.0(a.0(d.0(x0)))) -> TOP.0(a_flat.0(down.0(d.0(x0)))) TOP.0(up.0(b.0(a.0(x0)))) -> TOP.0(b_flat.0(down.0(a.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(d.0(d.0(x0)))) -> TOP.0(d_flat.0(down.0(d.0(x0)))) TOP.0(up.0(d.0(u.0(x0)))) -> TOP.0(d_flat.0(u_flat.0(down.0(x0)))) The TRS R consists of the following rules: down.0(a.0(a.0(x))) -> up.1(c.) down.0(a.0(a.1(x))) -> up.1(c.) down.0(b.0(u.0(x))) -> up.0(b.0(d.0(x))) down.0(d.0(a.0(x))) -> up.0(a.0(d.0(x))) down.0(d.0(b.0(x))) -> up.0(u.0(a.0(b.0(x)))) down.0(d.0(b.1(x))) -> up.0(u.0(a.0(b.1(x)))) down.0(a.0(u.0(x))) -> up.0(u.0(a.0(x))) down.0(a.0(u.1(x))) -> up.0(u.0(a.1(x))) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(b.0(y6))) -> a_flat.0(down.0(b.0(y6))) down.0(a.0(b.1(y6))) -> a_flat.0(down.0(b.1(y6))) down.0(a.0(d.0(y8))) -> a_flat.0(down.0(d.0(y8))) down.0(a.0(d.1(y8))) -> a_flat.0(down.0(d.1(y8))) down.0(b.0(a.0(y10))) -> b_flat.0(down.0(a.0(y10))) down.0(b.0(a.1(y10))) -> b_flat.0(down.0(a.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(d.0(y13))) -> b_flat.0(down.0(d.0(y13))) down.0(b.0(d.1(y13))) -> b_flat.0(down.0(d.1(y13))) down.0(d.0(u.0(y17))) -> d_flat.0(down.0(u.0(y17))) down.0(d.0(u.1(y17))) -> d_flat.0(down.0(u.1(y17))) down.0(d.0(d.0(y18))) -> d_flat.0(down.0(d.0(y18))) down.0(d.0(d.1(y18))) -> d_flat.0(down.0(d.1(y18))) 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)) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(x0))) down.0(a.0(a.1(x0))) down.0(b.0(u.0(x0))) down.0(b.0(u.1(x0))) down.0(d.0(a.0(x0))) down.0(d.0(a.1(x0))) down.0(d.0(b.0(x0))) down.0(d.0(b.1(x0))) down.0(a.0(u.0(x0))) down.0(a.0(u.1(x0))) down.0(u.0(x0)) down.0(u.1(x0)) down.0(a.1(c.)) down.0(a.0(b.0(x0))) down.0(a.0(b.1(x0))) down.0(a.0(d.0(x0))) down.0(a.0(d.1(x0))) down.0(a.0(fresh_constant.)) down.0(b.0(a.0(x0))) down.0(b.0(a.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(d.0(x0))) down.0(b.0(d.1(x0))) down.0(b.0(fresh_constant.)) down.0(d.1(c.)) down.0(d.0(u.0(x0))) down.0(d.0(u.1(x0))) down.0(d.0(d.0(x0))) down.0(d.0(d.1(x0))) down.0(d.0(fresh_constant.)) a_flat.0(up.0(x0)) a_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)) d_flat.0(up.0(x0)) d_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (131) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (132) TRUE ---------------------------------------- (133) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(a(fresh_constant)) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(b(fresh_constant)) down(d(c)) down(d(u(x0))) down(d(d(x0))) down(d(fresh_constant)) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (134) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. down(a(fresh_constant)) down(b(fresh_constant)) down(d(fresh_constant)) ---------------------------------------- (135) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(u(x0)))) -> TOP(up(b(d(x0)))) TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(u(x0))) -> TOP(u_flat(down(x0))) TOP(up(a(b(x0)))) -> TOP(a_flat(down(b(x0)))) TOP(up(a(d(x0)))) -> TOP(a_flat(down(d(x0)))) TOP(up(b(a(x0)))) -> TOP(b_flat(down(a(x0)))) TOP(up(b(b(x0)))) -> TOP(b_flat(down(b(x0)))) TOP(up(d(d(x0)))) -> TOP(d_flat(down(d(x0)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(a(x))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(a(u(x))) -> up(u(a(x))) down(u(y2)) -> u_flat(down(y2)) down(a(b(y6))) -> a_flat(down(b(y6))) down(a(d(y8))) -> a_flat(down(d(y8))) down(b(a(y10))) -> b_flat(down(a(y10))) down(b(b(y11))) -> b_flat(down(b(y11))) down(b(d(y13))) -> b_flat(down(d(y13))) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) u_flat(up(x_1)) -> up(u(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) a_flat(up(x_1)) -> up(a(x_1)) The set Q consists of the following terms: down(a(a(x0))) down(b(u(x0))) down(d(a(x0))) down(d(b(x0))) down(a(u(x0))) down(u(x0)) down(a(c)) down(a(b(x0))) down(a(d(x0))) down(b(a(x0))) down(b(c)) down(b(b(x0))) down(b(d(x0))) down(d(c)) down(d(u(x0))) down(d(d(x0))) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) We have to consider all (P,Q,R)-chains.