/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, 31 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) AND (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QReductionProof [EQUIVALENT, 0 ms] (20) QDP (21) UsableRulesReductionPairsProof [EQUIVALENT, 10 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) TRUE (25) QDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) QDP (28) QReductionProof [EQUIVALENT, 0 ms] (29) QDP (30) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) QDP (34) QReductionProof [EQUIVALENT, 0 ms] (35) QDP (36) MRRProof [EQUIVALENT, 7 ms] (37) QDP (38) PisEmptyProof [EQUIVALENT, 0 ms] (39) YES (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) QReductionProof [EQUIVALENT, 0 ms] (44) QDP (45) TransformationProof [EQUIVALENT, 0 ms] (46) QDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) QDP (49) QReductionProof [EQUIVALENT, 0 ms] (50) QDP (51) Trivial-Transformation [SOUND, 0 ms] (52) QTRS (53) DependencyPairsProof [EQUIVALENT, 0 ms] (54) QDP (55) DependencyGraphProof [EQUIVALENT, 0 ms] (56) AND (57) QDP (58) UsableRulesProof [EQUIVALENT, 0 ms] (59) QDP (60) QDPSizeChangeProof [EQUIVALENT, 0 ms] (61) YES (62) QDP (63) UsableRulesProof [EQUIVALENT, 0 ms] (64) QDP (65) QDPSizeChangeProof [EQUIVALENT, 0 ms] (66) YES (67) QDP (68) TransformationProof [EQUIVALENT, 0 ms] (69) QDP (70) QDPOrderProof [EQUIVALENT, 5 ms] (71) QDP (72) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (73) QTRS (74) AAECC Innermost [EQUIVALENT, 19 ms] (75) QTRS (76) DependencyPairsProof [EQUIVALENT, 0 ms] (77) QDP (78) DependencyGraphProof [EQUIVALENT, 0 ms] (79) AND (80) QDP (81) UsableRulesProof [EQUIVALENT, 0 ms] (82) QDP (83) QReductionProof [EQUIVALENT, 0 ms] (84) QDP (85) QDPSizeChangeProof [EQUIVALENT, 0 ms] (86) YES (87) QDP (88) UsableRulesProof [EQUIVALENT, 0 ms] (89) QDP (90) QReductionProof [EQUIVALENT, 5 ms] (91) QDP (92) TransformationProof [EQUIVALENT, 9 ms] (93) QDP (94) DependencyGraphProof [EQUIVALENT, 0 ms] (95) QDP (96) TransformationProof [EQUIVALENT, 0 ms] (97) QDP (98) TransformationProof [EQUIVALENT, 0 ms] (99) QDP (100) DependencyGraphProof [EQUIVALENT, 0 ms] (101) QDP (102) TransformationProof [EQUIVALENT, 0 ms] (103) QDP (104) TransformationProof [EQUIVALENT, 0 ms] (105) QDP (106) TransformationProof [EQUIVALENT, 0 ms] (107) QDP (108) TransformationProof [EQUIVALENT, 0 ms] (109) QDP (110) DependencyGraphProof [EQUIVALENT, 0 ms] (111) QDP (112) TransformationProof [EQUIVALENT, 0 ms] (113) QDP (114) QDPOrderProof [EQUIVALENT, 13 ms] (115) QDP (116) QDPOrderProof [EQUIVALENT, 22 ms] (117) QDP (118) DependencyGraphProof [EQUIVALENT, 0 ms] (119) QDP (120) MNOCProof [EQUIVALENT, 0 ms] (121) QDP (122) SplitQDPProof [EQUIVALENT, 0 ms] (123) AND (124) QDP (125) SemLabProof [SOUND, 0 ms] (126) QDP (127) DependencyGraphProof [EQUIVALENT, 0 ms] (128) QDP (129) UsableRulesReductionPairsProof [EQUIVALENT, 9 ms] (130) QDP (131) MRRProof [EQUIVALENT, 0 ms] (132) QDP (133) DependencyGraphProof [EQUIVALENT, 0 ms] (134) QDP (135) MRRProof [EQUIVALENT, 9 ms] (136) QDP (137) MRRProof [EQUIVALENT, 0 ms] (138) QDP (139) MRRProof [EQUIVALENT, 0 ms] (140) QDP (141) PisEmptyProof [SOUND, 0 ms] (142) TRUE (143) QDP (144) SplitQDPProof [EQUIVALENT, 0 ms] (145) AND (146) QDP (147) SemLabProof [SOUND, 0 ms] (148) QDP (149) DependencyGraphProof [EQUIVALENT, 0 ms] (150) QDP (151) MRRProof [EQUIVALENT, 6 ms] (152) QDP (153) DependencyGraphProof [EQUIVALENT, 0 ms] (154) QDP (155) MRRProof [EQUIVALENT, 0 ms] (156) QDP (157) MRRProof [EQUIVALENT, 18 ms] (158) QDP (159) PisEmptyProof [SOUND, 0 ms] (160) TRUE (161) QDP ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: a(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(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(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(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(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(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(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(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(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(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(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_b(u(x)) -> result_b(b(d(x))) redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(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(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(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(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_b(u(x)) -> result_b(b(d(x))) redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(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(u(x_1)) -> REDUCE(x_1) Strictly oriented rules of the TRS R: redex_d(a(x)) -> result_d(a(d(x))) redex_b(u(x)) -> result_b(b(d(x))) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_A(x_1)) = 1 + x_1 POL(CHECK_B(x_1)) = 1 + x_1 POL(CHECK_D(x_1)) = x_1 POL(REDUCE(x_1)) = 1 + 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)) = x_1 POL(redex_b(x_1)) = x_1 POL(redex_d(x_1)) = 1 + 2*x_1 POL(result_a(x_1)) = x_1 POL(result_b(x_1)) = x_1 POL(result_d(x_1)) = x_1 POL(u(x_1)) = 1 + 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(a(x_1)) -> CHECK_A(redex_a(x_1)) REDUCE(b(x_1)) -> CHECK_B(redex_b(x_1)) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) CHECK_D(redex_d(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(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) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (15) Complex Obligation (AND) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) The TRS R consists of the following rules: redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(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. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) The TRS R consists of the following rules: redex_d(b(x)) -> result_d(u(a(b(x)))) The set Q consists of the following terms: redex_a(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. ---------------------------------------- (19) 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(a(x0))) redex_b(u(x0)) redex_a(u(x0)) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_D(redex_d(x_1)) -> REDUCE(x_1) REDUCE(d(x_1)) -> CHECK_D(redex_d(x_1)) The TRS R consists of the following rules: redex_d(b(x)) -> result_d(u(a(b(x)))) The set Q consists of the following terms: redex_d(a(x0)) redex_d(b(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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(d(x_1)) -> CHECK_D(redex_d(x_1)) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_D(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_d(x_1)) = 2*x_1 POL(result_d(x_1)) = x_1 POL(u(x_1)) = x_1 ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_D(redex_d(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_d(b(x)) -> result_d(u(a(b(x)))) The set Q consists of the following terms: redex_d(a(x0)) redex_d(b(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (24) TRUE ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) 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) The TRS R consists of the following rules: redex_d(b(x)) -> result_d(u(a(b(x)))) redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(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. ---------------------------------------- (26) 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. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) 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) The TRS R consists of the following rules: redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(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. ---------------------------------------- (28) 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)) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) 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) The TRS R consists of the following rules: redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(a(a(x0))) redex_b(u(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) 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_A(x_1)) = x_1 POL(CHECK_B(x_1)) = 2*x_1 POL(REDUCE(x_1)) = 2*x_1 POL(a(x_1)) = 2*x_1 POL(b(x_1)) = 2*x_1 POL(c) = 0 POL(redex_a(x_1)) = 2*x_1 POL(redex_b(x_1)) = x_1 POL(result_a(x_1)) = x_1 POL(u(x_1)) = 2*x_1 ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) CHECK_A(redex_a(x_1)) -> REDUCE(x_1) CHECK_B(redex_b(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(a(a(x0))) redex_b(u(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) The TRS R consists of the following rules: redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(a(a(x0))) redex_b(u(x0)) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) 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_b(u(x0)) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) The TRS R consists of the following rules: redex_a(a(a(x))) -> result_a(c) redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(a(a(x0))) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) 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: CHECK_A(redex_a(x_1)) -> REDUCE(x_1) REDUCE(a(x_1)) -> CHECK_A(redex_a(x_1)) Strictly oriented rules of the TRS R: redex_a(a(a(x))) -> result_a(c) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_A(x_1)) = 1 + x_1 POL(REDUCE(x_1)) = 2*x_1 POL(a(x_1)) = 2 + 2*x_1 POL(c) = 0 POL(redex_a(x_1)) = 2 + 2*x_1 POL(result_a(x_1)) = x_1 POL(u(x_1)) = x_1 ---------------------------------------- (37) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: redex_a(u(x)) -> result_a(u(a(x))) The set Q consists of the following terms: redex_a(a(a(x0))) redex_a(u(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (39) YES ---------------------------------------- (40) 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(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(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. ---------------------------------------- (41) 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. ---------------------------------------- (42) 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(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(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. ---------------------------------------- (43) 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)) ---------------------------------------- (44) 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(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(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. ---------------------------------------- (45) 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)))) ---------------------------------------- (46) 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(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(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. ---------------------------------------- (47) 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. ---------------------------------------- (48) 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(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(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. ---------------------------------------- (49) 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)) ---------------------------------------- (50) 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(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(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. ---------------------------------------- (51) Trivial-Transformation (SOUND) We applied the Trivial transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(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. ---------------------------------------- (53) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (54) 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(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. ---------------------------------------- (55) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 3 less nodes. ---------------------------------------- (56) Complex Obligation (AND) ---------------------------------------- (57) 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(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) 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. ---------------------------------------- (59) 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. ---------------------------------------- (60) 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 ---------------------------------------- (61) YES ---------------------------------------- (62) 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(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. ---------------------------------------- (63) 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. ---------------------------------------- (64) 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. ---------------------------------------- (65) 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 ---------------------------------------- (66) YES ---------------------------------------- (67) 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(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. ---------------------------------------- (68) 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))))) ---------------------------------------- (69) 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(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. ---------------------------------------- (70) 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(a(x))) -> c a(u(x)) -> u(a(x)) ---------------------------------------- (71) 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(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. ---------------------------------------- (72) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (73) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(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. ---------------------------------------- (74) 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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(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(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} ---------------------------------------- (75) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(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(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(fresh_constant))) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) ---------------------------------------- (76) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (77) 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) DOWN(a(a(c))) -> A_FLAT(down(a(c))) DOWN(a(a(c))) -> DOWN(a(c)) DOWN(a(a(b(y21)))) -> A_FLAT(down(a(b(y21)))) DOWN(a(a(b(y21)))) -> DOWN(a(b(y21))) DOWN(a(a(u(y22)))) -> A_FLAT(down(a(u(y22)))) DOWN(a(a(u(y22)))) -> DOWN(a(u(y22))) DOWN(a(a(d(y23)))) -> A_FLAT(down(a(d(y23)))) DOWN(a(a(d(y23)))) -> DOWN(a(d(y23))) DOWN(a(a(fresh_constant))) -> A_FLAT(down(a(fresh_constant))) DOWN(a(a(fresh_constant))) -> DOWN(a(fresh_constant)) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(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(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 29 less nodes. ---------------------------------------- (79) Complex Obligation (AND) ---------------------------------------- (80) 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)) DOWN(a(a(b(y21)))) -> DOWN(a(b(y21))) DOWN(a(a(d(y23)))) -> DOWN(a(d(y23))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(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(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (81) 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. ---------------------------------------- (82) 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)) DOWN(a(a(b(y21)))) -> DOWN(a(b(y21))) DOWN(a(a(d(y23)))) -> DOWN(a(d(y23))) R is empty. The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (83) 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(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(fresh_constant))) a_flat(up(x0)) b_flat(up(x0)) u_flat(up(x0)) d_flat(up(x0)) ---------------------------------------- (84) 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)) DOWN(a(a(b(y21)))) -> DOWN(a(b(y21))) DOWN(a(a(d(y23)))) -> DOWN(a(d(y23))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) 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(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(a(b(y21)))) -> DOWN(a(b(y21))) The graph contains the following edges 1 > 1 *DOWN(u(y2)) -> DOWN(y2) 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(a(d(y23)))) -> DOWN(a(d(y23))) 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 ---------------------------------------- (86) YES ---------------------------------------- (87) 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(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(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(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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) 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. ---------------------------------------- (89) 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(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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) 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)) ---------------------------------------- (91) 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(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (92) 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(a(x0))))) -> TOP(up(c)),TOP(up(a(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)))) (TOP(up(a(a(c)))) -> TOP(a_flat(down(a(c)))),TOP(up(a(a(c)))) -> TOP(a_flat(down(a(c))))) (TOP(up(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))),TOP(up(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0)))))) (TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))),TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0)))))) (TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))),TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0)))))) (TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))),TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant))))) ---------------------------------------- (93) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(a(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))) TOP(up(a(a(c)))) -> TOP(a_flat(down(a(c)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (94) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. ---------------------------------------- (95) 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)))) TOP(up(a(a(c)))) -> TOP(a_flat(down(a(c)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (96) 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))))) ---------------------------------------- (97) 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(a(a(c)))) -> TOP(a_flat(down(a(c)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (98) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(a(a(c)))) -> TOP(a_flat(down(a(c)))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(a(a(c)))) -> TOP(a_flat(a_flat(down(c)))),TOP(up(a(a(c)))) -> TOP(a_flat(a_flat(down(c))))) ---------------------------------------- (99) 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(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) TOP(up(a(a(c)))) -> TOP(a_flat(a_flat(down(c)))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (100) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (102) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(a(a(b(x0))))) -> TOP(a_flat(down(a(b(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))),TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0)))))) ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (104) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(a(a(u(x0))))) -> TOP(a_flat(down(a(u(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0))))),TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0)))))) ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (106) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(a(a(d(x0))))) -> TOP(a_flat(down(a(d(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))),TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0)))))) ---------------------------------------- (107) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) TOP(up(d(u(x0)))) -> TOP(d_flat(u_flat(down(x0)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (108) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(down(a(fresh_constant)))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(a_flat(down(fresh_constant)))),TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(a_flat(down(fresh_constant))))) ---------------------------------------- (109) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) TOP(up(a(a(fresh_constant)))) -> TOP(a_flat(a_flat(down(fresh_constant)))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (110) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (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(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(a(a(u(x0))))) -> TOP(a_flat(up(u(a(x0))))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(a(a(u(x0))))) -> TOP(up(a(u(a(x0))))),TOP(up(a(a(u(x0))))) -> TOP(up(a(u(a(x0)))))) ---------------------------------------- (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(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) TOP(up(a(a(u(x0))))) -> TOP(up(a(u(a(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (114) 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)))) TOP(up(d(b(x0)))) -> TOP(up(u(a(b(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)) = 1 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)) ---------------------------------------- (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(a(d(x0)))) -> TOP(a_flat(down(d(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) TOP(up(a(a(u(x0))))) -> TOP(up(a(u(a(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (116) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. 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)) = 0 POL(d_flat(x_1)) = 0 POL(down(x_1)) = 1 + x_1 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)) ---------------------------------------- (117) 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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) TOP(up(a(a(u(x0))))) -> TOP(up(a(u(a(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (118) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (119) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (120) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (121) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (122) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (123) Complex Obligation (AND) ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: down(a(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)) down(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) a_flat(up(x_1)) -> up(a(x_1)) d_flat(up(x_1)) -> up(d(x_1)) b_flat(up(x_1)) -> up(b(x_1)) u_flat(up(x_1)) -> up(u(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (125) 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. ---------------------------------------- (126) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: down.0(a.0(a.0(a.0(x)))) -> up.0(c.) down.0(a.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.)) down.0(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) 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)) 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)) 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(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (127) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (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(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(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.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(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: down.0(a.0(a.0(a.0(x)))) -> up.0(c.) down.0(a.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.)) down.0(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) 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)) 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)) 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(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (129) 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: a_flat.0(up.1(x_1)) -> up.0(a.1(x_1)) 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)) 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)) = 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)) = 1 + x_1 POL(d_flat.0(x_1)) = 1 + x_1 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = 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)) = 1 + x_1 POL(up.1(x_1)) = 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(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(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.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(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: down.0(d.1(fresh_constant.)) -> d_flat.0(down.1(fresh_constant.)) a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.1(y2)) -> u_flat.0(down.1(y2)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.0(c.) down.0(a.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(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(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(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (131) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(d.1(fresh_constant.)) -> d_flat.0(down.1(fresh_constant.)) 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.)) 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 ---------------------------------------- (132) 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(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(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.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(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.0(c.) down.0(a.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(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(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(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (133) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 9 less nodes. ---------------------------------------- (134) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.0(c.) down.0(a.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(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(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(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (135) 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.0(a.1(x)))) -> up.0(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)) = 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)) = 1 + x_1 POL(d_flat.0(x_1)) = x_1 POL(down.0(x_1)) = x_1 POL(fresh_constant.) = 0 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 ---------------------------------------- (136) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.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(b.0(u.1(x))) -> up.0(b.0(d.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(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(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (137) 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(d.0(a.1(x))) -> up.0(a.0(d.1(x))) down.0(b.0(u.1(x))) -> up.0(b.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(fresh_constant.) = 0 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 ---------------------------------------- (138) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.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(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(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(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (139) 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(fresh_constant.) = 0 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 ---------------------------------------- (140) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: a_flat.0(up.0(x_1)) -> up.0(a.0(x_1)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.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(a.0(u.0(x))) -> up.0(u.0(a.0(x))) 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(a.0(a.0(c.))) -> a_flat.0(down.0(a.0(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.1(fresh_constant.))) -> a_flat.0(down.0(a.1(fresh_constant.))) u_flat.0(up.0(x_1)) -> up.0(u.0(x_1)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.0(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (141) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (142) TRUE ---------------------------------------- (143) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: a_flat(up(x_1)) -> up(a(x_1)) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) 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))) d_flat(up(x_1)) -> up(d(x_1)) down(u(y2)) -> u_flat(down(y2)) down(a(a(a(x)))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(a(u(x))) -> up(u(a(x))) 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(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) u_flat(up(x_1)) -> up(u(x_1)) b_flat(up(x_1)) -> up(b(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (144) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (145) Complex Obligation (AND) ---------------------------------------- (146) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: a_flat(up(x_1)) -> up(a(x_1)) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) 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))) d_flat(up(x_1)) -> up(d(x_1)) down(u(y2)) -> u_flat(down(y2)) down(a(a(a(x)))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(a(u(x))) -> up(u(a(x))) 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(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) u_flat(up(x_1)) -> up(u(x_1)) b_flat(up(x_1)) -> up(b(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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. ---------------------------------------- (147) 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 d_flat: 0 fresh_constant: 0 up: 0 u_flat: 0 b_flat: 0 a_flat: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (148) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: 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)) 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(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))) 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)) 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(a.0(a.0(x)))) -> up.1(c.) down.0(a.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(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(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(a.0(a.1(c.))) -> a_flat.0(down.0(a.1(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.0(fresh_constant.))) -> a_flat.0(down.0(a.0(fresh_constant.))) 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)) 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)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.1(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (149) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (150) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(b.0(u.0(x0)))) -> TOP.0(up.0(b.0(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(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(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.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(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: 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)) 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(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))) 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)) 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(a.0(a.0(x)))) -> up.1(c.) down.0(a.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(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(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(a.0(a.1(c.))) -> a_flat.0(down.0(a.1(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.0(fresh_constant.))) -> a_flat.0(down.0(a.0(fresh_constant.))) 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)) 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)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.1(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (151) 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(d.1(c.)) -> d_flat.0(down.1(c.)) 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.)) 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(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 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (152) 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(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(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.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(a.0(a.0(b.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.1(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) TOP.0(up.0(a.0(a.0(d.1(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.1(x0))))) The TRS R consists of the following rules: 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)) 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(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))) 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)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.1(c.) down.0(a.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(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(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(a.0(a.1(c.))) -> a_flat.0(down.0(a.1(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.0(fresh_constant.))) -> a_flat.0(down.0(a.0(fresh_constant.))) 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)) 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)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.1(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (153) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 9 less nodes. ---------------------------------------- (154) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: 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)) 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(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))) 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)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.1(c.) down.0(a.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(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(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(a.0(a.1(c.))) -> a_flat.0(down.0(a.1(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.0(fresh_constant.))) -> a_flat.0(down.0(a.0(fresh_constant.))) 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)) 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)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.1(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (155) 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(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)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (156) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: 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)) 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(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))) 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)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.1(c.) down.0(a.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(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(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(a.0(a.1(c.))) -> a_flat.0(down.0(a.1(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.0(fresh_constant.))) -> a_flat.0(down.0(a.0(fresh_constant.))) 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)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.1(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (157) 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(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)) down.0(b.0(u.1(x))) -> up.0(b.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)) = 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(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)) = x_1 ---------------------------------------- (158) 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(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)))) TOP.0(up.0(a.0(a.0(b.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(b.0(x0))))) TOP.0(up.0(a.0(a.0(d.0(x0))))) -> TOP.0(a_flat.0(a_flat.0(down.0(d.0(x0))))) The TRS R consists of the following rules: 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)) 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(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))) d_flat.0(up.0(x_1)) -> up.0(d.0(x_1)) down.0(u.0(y2)) -> u_flat.0(down.0(y2)) down.0(a.0(a.0(a.0(x)))) -> up.1(c.) down.0(a.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(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(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(a.0(a.1(c.))) -> a_flat.0(down.0(a.1(c.))) down.0(a.0(a.0(b.0(y21)))) -> a_flat.0(down.0(a.0(b.0(y21)))) down.0(a.0(a.0(b.1(y21)))) -> a_flat.0(down.0(a.0(b.1(y21)))) down.0(a.0(a.0(u.0(y22)))) -> a_flat.0(down.0(a.0(u.0(y22)))) down.0(a.0(a.0(u.1(y22)))) -> a_flat.0(down.0(a.0(u.1(y22)))) down.0(a.0(a.0(d.0(y23)))) -> a_flat.0(down.0(a.0(d.0(y23)))) down.0(a.0(a.0(d.1(y23)))) -> a_flat.0(down.0(a.0(d.1(y23)))) down.0(a.0(a.0(fresh_constant.))) -> a_flat.0(down.0(a.0(fresh_constant.))) 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)) b_flat.0(up.0(x_1)) -> up.0(b.0(x_1)) The set Q consists of the following terms: down.0(a.0(a.0(a.0(x0)))) down.0(a.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.)) down.0(a.0(a.1(c.))) down.0(a.0(a.0(b.0(x0)))) down.0(a.0(a.0(b.1(x0)))) down.0(a.0(a.0(u.0(x0)))) down.0(a.0(a.0(u.1(x0)))) down.0(a.0(a.0(d.0(x0)))) down.0(a.0(a.0(d.1(x0)))) down.0(a.0(a.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. ---------------------------------------- (159) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (160) TRUE ---------------------------------------- (161) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(b(d(x0)))) -> TOP(b_flat(down(d(x0)))) TOP(up(b(u(x0)))) -> TOP(up(b(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)))) TOP(up(a(a(b(x0))))) -> TOP(a_flat(a_flat(down(b(x0))))) TOP(up(a(a(d(x0))))) -> TOP(a_flat(a_flat(down(d(x0))))) The TRS R consists of the following rules: a_flat(up(x_1)) -> up(a(x_1)) down(d(a(x))) -> up(a(d(x))) down(d(b(x))) -> up(u(a(b(x)))) down(d(u(y17))) -> d_flat(down(u(y17))) down(d(d(y18))) -> d_flat(down(d(y18))) d_flat(up(x_1)) -> up(d(x_1)) down(u(y2)) -> u_flat(down(y2)) down(a(a(a(x)))) -> up(c) down(b(u(x))) -> up(b(d(x))) down(a(u(x))) -> up(u(a(x))) 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(a(a(c))) -> a_flat(down(a(c))) down(a(a(b(y21)))) -> a_flat(down(a(b(y21)))) down(a(a(u(y22)))) -> a_flat(down(a(u(y22)))) down(a(a(d(y23)))) -> a_flat(down(a(d(y23)))) down(a(a(fresh_constant))) -> a_flat(down(a(fresh_constant))) u_flat(up(x_1)) -> up(u(x_1)) b_flat(up(x_1)) -> up(b(x_1)) The set Q consists of the following terms: down(a(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)) down(a(a(c))) down(a(a(b(x0)))) down(a(a(u(x0)))) down(a(a(d(x0)))) down(a(a(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.