/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could not be shown: (0) OTRS (1) Trivial-Transformation [SOUND, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) NonTerminationLoopProof [COMPLETE, 0 ms] (10) NO (11) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (12) QTRS (13) DependencyPairsProof [EQUIVALENT, 7 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) AND (17) QDP (18) UsableRulesProof [EQUIVALENT, 0 ms] (19) QDP (20) QReductionProof [EQUIVALENT, 0 ms] (21) QDP (22) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (23) QDP (24) DependencyGraphProof [EQUIVALENT, 0 ms] (25) QDP (26) QReductionProof [EQUIVALENT, 0 ms] (27) QDP (28) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (29) QDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) TRUE (32) QDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) QDP (35) QReductionProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 22 ms] (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) QReductionProof [EQUIVALENT, 0 ms] (44) QDP (45) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (46) QTRS (47) AAECC Innermost [EQUIVALENT, 7 ms] (48) QTRS (49) DependencyPairsProof [EQUIVALENT, 0 ms] (50) QDP (51) DependencyGraphProof [EQUIVALENT, 1 ms] (52) AND (53) QDP (54) UsableRulesProof [EQUIVALENT, 0 ms] (55) QDP (56) QReductionProof [EQUIVALENT, 0 ms] (57) QDP (58) QDPSizeChangeProof [EQUIVALENT, 0 ms] (59) YES (60) QDP (61) UsableRulesProof [EQUIVALENT, 0 ms] (62) QDP (63) QReductionProof [EQUIVALENT, 0 ms] (64) QDP (65) TransformationProof [EQUIVALENT, 0 ms] (66) QDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) QDP (69) TransformationProof [EQUIVALENT, 0 ms] (70) QDP (71) TransformationProof [EQUIVALENT, 0 ms] (72) QDP (73) TransformationProof [EQUIVALENT, 0 ms] (74) QDP (75) TransformationProof [EQUIVALENT, 0 ms] (76) QDP (77) TransformationProof [EQUIVALENT, 0 ms] (78) QDP (79) TransformationProof [EQUIVALENT, 0 ms] (80) QDP (81) TransformationProof [EQUIVALENT, 0 ms] (82) QDP (83) TransformationProof [EQUIVALENT, 0 ms] (84) QDP (85) QDPOrderProof [EQUIVALENT, 26 ms] (86) QDP (87) DependencyGraphProof [EQUIVALENT, 0 ms] (88) QDP (89) QDPOrderProof [EQUIVALENT, 9 ms] (90) QDP (91) QDPOrderProof [EQUIVALENT, 688 ms] (92) QDP (93) QDPOrderProof [EQUIVALENT, 959 ms] (94) QDP (95) MNOCProof [EQUIVALENT, 0 ms] (96) QDP (97) SplitQDPProof [EQUIVALENT, 0 ms] (98) AND (99) QDP (100) SemLabProof [SOUND, 0 ms] (101) QDP (102) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (103) QDP (104) MRRProof [EQUIVALENT, 27 ms] (105) QDP (106) DependencyGraphProof [EQUIVALENT, 0 ms] (107) QDP (108) MRRProof [EQUIVALENT, 0 ms] (109) QDP (110) MRRProof [EQUIVALENT, 0 ms] (111) QDP (112) PisEmptyProof [SOUND, 0 ms] (113) TRUE (114) QDP (115) QReductionProof [EQUIVALENT, 0 ms] (116) QDP (117) MNOCProof [EQUIVALENT, 0 ms] (118) QDP (119) SplitQDPProof [EQUIVALENT, 0 ms] (120) AND (121) QDP (122) SemLabProof [SOUND, 0 ms] (123) QDP (124) MRRProof [EQUIVALENT, 0 ms] (125) QDP (126) DependencyGraphProof [EQUIVALENT, 0 ms] (127) QDP (128) PisEmptyProof [SOUND, 0 ms] (129) TRUE (130) QDP (131) QReductionProof [EQUIVALENT, 0 ms] (132) QDP ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: a -> f(a) f(f(x)) -> g(x) g(g(x)) -> h(x) h(h(x)) -> c Outermost Strategy. ---------------------------------------- (1) Trivial-Transformation (SOUND) We applied the Trivial transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a -> f(a) f(f(x)) -> g(x) g(g(x)) -> h(x) h(h(x)) -> c Q is empty. ---------------------------------------- (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: A -> F(a) A -> A F(f(x)) -> G(x) G(g(x)) -> H(x) The TRS R consists of the following rules: a -> f(a) f(f(x)) -> g(x) g(g(x)) -> h(x) h(h(x)) -> c Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: A -> A The TRS R consists of the following rules: a -> f(a) f(f(x)) -> g(x) g(g(x)) -> h(x) h(h(x)) -> c Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) 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. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: A -> A R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = A evaluates to t =A Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from A to A. ---------------------------------------- (10) NO ---------------------------------------- (11) Thiemann-SpecialC-Transformation (EQUIVALENT) We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. ---------------------------------------- (12) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_f(f(x)) -> result_f(g(x)) redex_g(g(x)) -> result_g(h(x)) redex_h(h(x)) -> result_h(c) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_h(result_h(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) ---------------------------------------- (13) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) TOP(go_up(x)) -> REDUCE(x) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(f(x_1)) -> REDEX_F(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) REDUCE(g(x_1)) -> REDEX_G(x_1) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) REDUCE(h(x_1)) -> REDEX_H(x_1) CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) CHECK_F(redex_f(x_1)) -> REDUCE(x_1) CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1)) CHECK_G(redex_g(x_1)) -> REDUCE(x_1) CHECK_H(redex_h(x_1)) -> IN_H_1(reduce(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_f(f(x)) -> result_f(g(x)) redex_g(g(x)) -> result_g(h(x)) redex_h(h(x)) -> result_h(c) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_h(result_h(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 7 less nodes. ---------------------------------------- (16) Complex Obligation (AND) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_f(f(x)) -> result_f(g(x)) redex_g(g(x)) -> result_g(h(x)) redex_h(h(x)) -> result_h(c) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_h(result_h(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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. ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_h(h(x)) -> result_h(c) redex_f(f(x)) -> result_f(g(x)) redex_g(g(x)) -> result_g(h(x)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_h(h(x)) -> result_h(c) redex_f(f(x)) -> result_f(g(x)) redex_g(g(x)) -> result_g(h(x)) The set Q consists of the following terms: redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) The following rules are removed from R: redex_f(f(x)) -> result_f(g(x)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = x_1 POL(CHECK_G(x_1)) = x_1 POL(CHECK_H(x_1)) = x_1 POL(REDUCE(x_1)) = 2*x_1 POL(c) = 0 POL(f(x_1)) = 2*x_1 POL(g(x_1)) = 2*x_1 POL(h(x_1)) = 2*x_1 POL(redex_f(x_1)) = 2*x_1 POL(redex_g(x_1)) = 2*x_1 POL(redex_h(x_1)) = 2*x_1 POL(result_f(x_1)) = x_1 POL(result_g(x_1)) = x_1 POL(result_h(x_1)) = x_1 ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_h(h(x)) -> result_h(c) redex_g(g(x)) -> result_g(h(x)) The set Q consists of the following terms: redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) The TRS R consists of the following rules: redex_h(h(x)) -> result_h(c) redex_g(g(x)) -> result_g(h(x)) The set Q consists of the following terms: redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) 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_f(f(x0)) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) The TRS R consists of the following rules: redex_h(h(x)) -> result_h(c) redex_g(g(x)) -> result_g(h(x)) The set Q consists of the following terms: redex_g(g(x0)) redex_h(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) The following rules are removed from R: redex_g(g(x)) -> result_g(h(x)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_G(x_1)) = x_1 POL(CHECK_H(x_1)) = x_1 POL(REDUCE(x_1)) = 2*x_1 POL(c) = 0 POL(g(x_1)) = 2*x_1 POL(h(x_1)) = 2*x_1 POL(redex_g(x_1)) = 2*x_1 POL(redex_h(x_1)) = 2*x_1 POL(result_g(x_1)) = x_1 POL(result_h(x_1)) = x_1 ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_G(redex_g(x_1)) -> REDUCE(x_1) REDUCE(h(x_1)) -> CHECK_H(redex_h(x_1)) CHECK_H(redex_h(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_h(h(x)) -> result_h(c) The set Q consists of the following terms: redex_g(g(x0)) redex_h(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (31) TRUE ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_f(f(x)) -> result_f(g(x)) redex_g(g(x)) -> result_g(h(x)) redex_h(h(x)) -> result_h(c) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_h(result_h(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) 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)) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) (TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))) (TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0))),TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0)))) (TOP(go_up(a)) -> TOP(go_up(f(a))),TOP(go_up(a)) -> TOP(go_up(f(a)))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0))) TOP(go_up(a)) -> TOP(go_up(f(a))) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(go_up(a)) -> TOP(go_up(f(a))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(a) = 1 POL(c) = 0 POL(check_f(x_1)) = x_1 POL(check_g(x_1)) = x_1 POL(check_h(x_1)) = x_1 POL(f(x_1)) = 0 POL(g(x_1)) = 0 POL(go_up(x_1)) = x_1 POL(h(x_1)) = 0 POL(in_f_1(x_1)) = 0 POL(in_g_1(x_1)) = 0 POL(in_h_1(x_1)) = 0 POL(redex_f(x_1)) = 0 POL(redex_g(x_1)) = 0 POL(redex_h(x_1)) = 0 POL(reduce(x_1)) = 0 POL(result_f(x_1)) = x_1 POL(result_g(x_1)) = x_1 POL(result_h(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) TOP(go_up(h(x0))) -> TOP(check_h(redex_h(x0))) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_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(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_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(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) reduce(h(x_1)) -> check_h(redex_h(x_1)) reduce(a) -> go_up(f(a)) redex_h(h(x)) -> result_h(c) check_h(result_h(x)) -> go_up(x) check_h(redex_h(x_1)) -> in_h_1(reduce(x_1)) in_h_1(go_up(x_1)) -> go_up(h(x_1)) redex_g(g(x)) -> result_g(h(x)) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) redex_f(f(x)) -> result_f(g(x)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0)) reduce(h(x0)) reduce(a) redex_f(f(x0)) redex_g(g(x0)) redex_h(h(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_h(result_h(x0)) check_f(redex_f(x0)) check_g(redex_g(x0)) check_h(redex_h(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) in_h_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (46) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) top(up(x)) -> top(down(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) Q is empty. ---------------------------------------- (47) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) The TRS R 2 is top(up(x)) -> top(down(x)) The signature Sigma is {top_1} ---------------------------------------- (48) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) top(up(x)) -> top(down(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) ---------------------------------------- (49) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) TOP(up(x)) -> DOWN(x) DOWN(f(a)) -> F_FLAT(down(a)) DOWN(f(a)) -> DOWN(a) DOWN(f(g(y5))) -> F_FLAT(down(g(y5))) DOWN(f(g(y5))) -> DOWN(g(y5)) DOWN(f(h(y6))) -> F_FLAT(down(h(y6))) DOWN(f(h(y6))) -> DOWN(h(y6)) DOWN(f(c)) -> F_FLAT(down(c)) DOWN(f(c)) -> DOWN(c) DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) DOWN(f(fresh_constant)) -> DOWN(fresh_constant) DOWN(g(a)) -> G_FLAT(down(a)) DOWN(g(a)) -> DOWN(a) DOWN(g(f(y8))) -> G_FLAT(down(f(y8))) DOWN(g(f(y8))) -> DOWN(f(y8)) DOWN(g(h(y10))) -> G_FLAT(down(h(y10))) DOWN(g(h(y10))) -> DOWN(h(y10)) DOWN(g(c)) -> G_FLAT(down(c)) DOWN(g(c)) -> DOWN(c) DOWN(g(fresh_constant)) -> G_FLAT(down(fresh_constant)) DOWN(g(fresh_constant)) -> DOWN(fresh_constant) DOWN(h(a)) -> H_FLAT(down(a)) DOWN(h(a)) -> DOWN(a) DOWN(h(f(y12))) -> H_FLAT(down(f(y12))) DOWN(h(f(y12))) -> DOWN(f(y12)) DOWN(h(g(y13))) -> H_FLAT(down(g(y13))) DOWN(h(g(y13))) -> DOWN(g(y13)) DOWN(h(c)) -> H_FLAT(down(c)) DOWN(h(c)) -> DOWN(c) DOWN(h(fresh_constant)) -> H_FLAT(down(fresh_constant)) DOWN(h(fresh_constant)) -> DOWN(fresh_constant) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) top(up(x)) -> top(down(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 25 less nodes. ---------------------------------------- (52) Complex Obligation (AND) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(g(y5))) -> DOWN(g(y5)) DOWN(g(f(y8))) -> DOWN(f(y8)) DOWN(f(h(y6))) -> DOWN(h(y6)) DOWN(h(f(y12))) -> DOWN(f(y12)) DOWN(h(g(y13))) -> DOWN(g(y13)) DOWN(g(h(y10))) -> DOWN(h(y10)) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) top(up(x)) -> top(down(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) 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. ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(g(y5))) -> DOWN(g(y5)) DOWN(g(f(y8))) -> DOWN(f(y8)) DOWN(f(h(y6))) -> DOWN(h(y6)) DOWN(h(f(y12))) -> DOWN(f(y12)) DOWN(h(g(y13))) -> DOWN(g(y13)) DOWN(g(h(y10))) -> DOWN(h(y10)) R is empty. The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) 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) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(g(y5))) -> DOWN(g(y5)) DOWN(g(f(y8))) -> DOWN(f(y8)) DOWN(f(h(y6))) -> DOWN(h(y6)) DOWN(h(f(y12))) -> DOWN(f(y12)) DOWN(h(g(y13))) -> DOWN(g(y13)) DOWN(g(h(y10))) -> DOWN(h(y10)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) 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(g(f(y8))) -> DOWN(f(y8)) The graph contains the following edges 1 > 1 *DOWN(g(h(y10))) -> DOWN(h(y10)) The graph contains the following edges 1 > 1 *DOWN(h(f(y12))) -> DOWN(f(y12)) The graph contains the following edges 1 > 1 *DOWN(f(g(y5))) -> DOWN(g(y5)) The graph contains the following edges 1 > 1 *DOWN(f(h(y6))) -> DOWN(h(y6)) The graph contains the following edges 1 > 1 *DOWN(h(g(y13))) -> DOWN(g(y13)) The graph contains the following edges 1 > 1 ---------------------------------------- (59) YES ---------------------------------------- (60) 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) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) top(up(x)) -> top(down(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) 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. ---------------------------------------- (62) 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) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) top(up(x0)) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) 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)) ---------------------------------------- (64) 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) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) 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)) -> TOP(up(f(a))),TOP(up(a)) -> TOP(up(f(a)))) (TOP(up(f(f(x0)))) -> TOP(up(g(x0))),TOP(up(f(f(x0)))) -> TOP(up(g(x0)))) (TOP(up(g(g(x0)))) -> TOP(up(h(x0))),TOP(up(g(g(x0)))) -> TOP(up(h(x0)))) (TOP(up(h(h(x0)))) -> TOP(up(c)),TOP(up(h(h(x0)))) -> TOP(up(c))) (TOP(up(f(a))) -> TOP(f_flat(down(a))),TOP(up(f(a))) -> TOP(f_flat(down(a)))) (TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))),TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))) (TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))),TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0))))) (TOP(up(f(c))) -> TOP(f_flat(down(c))),TOP(up(f(c))) -> TOP(f_flat(down(c)))) (TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))) (TOP(up(g(a))) -> TOP(g_flat(down(a))),TOP(up(g(a))) -> TOP(g_flat(down(a)))) (TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))),TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0))))) (TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))),TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0))))) (TOP(up(g(c))) -> TOP(g_flat(down(c))),TOP(up(g(c))) -> TOP(g_flat(down(c)))) (TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))),TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant)))) (TOP(up(h(a))) -> TOP(h_flat(down(a))),TOP(up(h(a))) -> TOP(h_flat(down(a)))) (TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))),TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0))))) (TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))),TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0))))) (TOP(up(h(c))) -> TOP(h_flat(down(c))),TOP(up(h(c))) -> TOP(h_flat(down(c)))) (TOP(up(h(fresh_constant))) -> TOP(h_flat(down(fresh_constant))),TOP(up(h(fresh_constant))) -> TOP(h_flat(down(fresh_constant)))) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(a)) -> TOP(up(f(a))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(h(h(x0)))) -> TOP(up(c)) TOP(up(f(a))) -> TOP(f_flat(down(a))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(f(c))) -> TOP(f_flat(down(c))) TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))) TOP(up(g(a))) -> TOP(g_flat(down(a))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(g(c))) -> TOP(g_flat(down(c))) TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))) TOP(up(h(a))) -> TOP(h_flat(down(a))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(c))) -> TOP(h_flat(down(c))) TOP(up(h(fresh_constant))) -> TOP(h_flat(down(fresh_constant))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 8 less nodes. ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(h(a))) -> TOP(h_flat(down(a))) TOP(up(f(a))) -> TOP(f_flat(down(a))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(a))) -> TOP(g_flat(down(a))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(h(a))) -> TOP(h_flat(down(a))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(h(a))) -> TOP(h_flat(up(f(a)))),TOP(up(h(a))) -> TOP(h_flat(up(f(a))))) ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(f(a))) -> TOP(f_flat(down(a))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(a))) -> TOP(g_flat(down(a))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(h_flat(up(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a))) -> TOP(f_flat(down(a))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(a))) -> TOP(f_flat(up(f(a)))),TOP(up(f(a))) -> TOP(f_flat(up(f(a))))) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(a))) -> TOP(g_flat(down(a))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(h_flat(up(f(a)))) TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(g(a))) -> TOP(g_flat(down(a))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(g(a))) -> TOP(g_flat(up(f(a)))),TOP(up(g(a))) -> TOP(g_flat(up(f(a))))) ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(h_flat(up(f(a)))) TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(h(a))) -> TOP(h_flat(up(f(a)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(h(a))) -> TOP(up(h(f(a)))),TOP(up(h(a))) -> TOP(up(h(f(a))))) ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(a))) -> TOP(up(f(f(a)))),TOP(up(f(a))) -> TOP(up(f(f(a))))) ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(f(a))) -> TOP(up(f(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(g(a))) -> TOP(up(g(f(a)))),TOP(up(g(a))) -> TOP(up(g(f(a))))) ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(g(x0)))) -> TOP(up(h(x0))) TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(f(a))) -> TOP(up(f(f(a)))) TOP(up(g(a))) -> TOP(up(g(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(g(g(x0)))) -> TOP(up(h(x0))) we obtained the following new rules [LPAR04]: (TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0)))),TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0))))) (TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0)))),TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0))))) (TOP(up(g(g(a)))) -> TOP(up(h(a))),TOP(up(g(g(a)))) -> TOP(up(h(a)))) ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(x0)))) -> TOP(up(g(x0))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(f(a))) -> TOP(up(f(f(a)))) TOP(up(g(a))) -> TOP(up(g(f(a)))) TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0)))) TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0)))) TOP(up(g(g(a)))) -> TOP(up(h(a))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(f(x0)))) -> TOP(up(g(x0))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))),TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0))))) (TOP(up(f(f(h(y_0))))) -> TOP(up(g(h(y_0)))),TOP(up(f(f(h(y_0))))) -> TOP(up(g(h(y_0))))) (TOP(up(f(f(a)))) -> TOP(up(g(a))),TOP(up(f(f(a)))) -> TOP(up(g(a)))) (TOP(up(f(f(g(f(y_0)))))) -> TOP(up(g(g(f(y_0))))),TOP(up(f(f(g(f(y_0)))))) -> TOP(up(g(g(f(y_0)))))) (TOP(up(f(f(g(g(y_0)))))) -> TOP(up(g(g(g(y_0))))),TOP(up(f(f(g(g(y_0)))))) -> TOP(up(g(g(g(y_0)))))) (TOP(up(f(f(g(a))))) -> TOP(up(g(g(a)))),TOP(up(f(f(g(a))))) -> TOP(up(g(g(a))))) ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(f(a))) -> TOP(up(f(f(a)))) TOP(up(g(a))) -> TOP(up(g(f(a)))) TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0)))) TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0)))) TOP(up(g(g(a)))) -> TOP(up(h(a))) TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))) TOP(up(f(f(h(y_0))))) -> TOP(up(g(h(y_0)))) TOP(up(f(f(a)))) -> TOP(up(g(a))) TOP(up(f(f(g(f(y_0)))))) -> TOP(up(g(g(f(y_0))))) TOP(up(f(f(g(g(y_0)))))) -> TOP(up(g(g(g(y_0))))) TOP(up(f(f(g(a))))) -> TOP(up(g(g(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))) TOP(up(f(f(h(y_0))))) -> TOP(up(g(h(y_0)))) TOP(up(f(f(a)))) -> TOP(up(g(a))) TOP(up(f(f(g(f(y_0)))))) -> TOP(up(g(g(f(y_0))))) TOP(up(f(f(g(g(y_0)))))) -> TOP(up(g(g(g(y_0))))) TOP(up(f(f(g(a))))) -> TOP(up(g(g(a)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(a) = 0 POL(c) = 0 POL(down(x_1)) = 0 POL(f(x_1)) = 1 POL(f_flat(x_1)) = 1 POL(fresh_constant) = 0 POL(g(x_1)) = 0 POL(g_flat(x_1)) = 0 POL(h(x_1)) = 0 POL(h_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: g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) h_flat(up(x_1)) -> up(h(x_1)) ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(f(a))) -> TOP(up(f(f(a)))) TOP(up(g(a))) -> TOP(up(g(f(a)))) TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0)))) TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0)))) TOP(up(g(g(a)))) -> TOP(up(h(a))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (87) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(g(a))) -> TOP(up(g(f(a)))) TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0)))) TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0)))) TOP(up(g(g(a)))) -> TOP(up(h(a))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (89) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(g(g(f(y_0))))) -> TOP(up(h(f(y_0)))) TOP(up(g(g(g(y_0))))) -> TOP(up(h(g(y_0)))) TOP(up(g(g(a)))) -> TOP(up(h(a))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = x_1 POL(a) = 0 POL(c) = 0 POL(down(x_1)) = 0 POL(f(x_1)) = 0 POL(f_flat(x_1)) = 0 POL(fresh_constant) = 0 POL(g(x_1)) = 1 POL(g_flat(x_1)) = 1 POL(h(x_1)) = 0 POL(h_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: f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) TOP(up(g(a))) -> TOP(up(g(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (91) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(g(a))) -> TOP(up(g(f(a)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( a ) = [[1], [0]] >>> <<< M( h_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( c ) = [[0], [0]] >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( f_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< M( h_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( f_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( g_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( g_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) down(a) -> up(f(a)) ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) TOP(up(h(a))) -> TOP(up(h(f(a)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(h(a))) -> TOP(up(h(f(a)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( a ) = [[0], [1]] >>> <<< M( h_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( c ) = [[0], [0]] >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( f_1(x_1) ) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 >>> <<< M( h_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< M( f_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( g_1(x_1) ) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< M( g_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) g_flat(up(x_1)) -> up(g(x_1)) h_flat(up(x_1)) -> up(h(x_1)) down(a) -> up(f(a)) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (97) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (98) Complex Obligation (AND) ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: down(a) -> up(f(a)) down(f(f(x))) -> up(g(x)) down(g(g(x))) -> up(h(x)) down(h(h(x))) -> up(c) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(h(fresh_constant)) -> h_flat(down(fresh_constant)) h_flat(up(x_1)) -> up(h(x_1)) g_flat(up(x_1)) -> up(g(x_1)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) 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. h_flat: 0 a: 0 c: 0 down: 0 f: 0 fresh_constant: 1 up: 0 h: 0 f_flat: 0 TOP: 0 g_flat: 0 g: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(f.0(h.1(x0)))) -> TOP.0(f_flat.0(down.0(h.1(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(h.1(x0)))) -> TOP.0(g_flat.0(down.0(h.1(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(f.1(x0)))) -> TOP.0(h_flat.0(down.0(f.1(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) TOP.0(up.0(h.0(g.1(x0)))) -> TOP.0(h_flat.0(down.0(g.1(x0)))) The TRS R consists of the following rules: down.0(a.) -> up.0(f.0(a.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(h.0(h.0(x))) -> up.0(c.) down.0(h.0(h.1(x))) -> up.0(c.) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.0(c.)) -> g_flat.0(down.0(c.)) down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.)) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.0(c.)) -> h_flat.0(down.0(c.)) down.0(h.1(fresh_constant.)) -> h_flat.0(down.1(fresh_constant.)) h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) h_flat.0(up.1(x_1)) -> up.0(h.1(x_1)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.0(c.)) down.0(g.1(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.0(c.)) down.0(h.1(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) 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: h_flat.0(up.1(x_1)) -> up.0(h.1(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.) = 0 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = 1 + x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(h.0(x_1)) = x_1 POL(h.1(x_1)) = x_1 POL(h_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(f.0(h.1(x0)))) -> TOP.0(f_flat.0(down.0(h.1(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(h.1(x0)))) -> TOP.0(g_flat.0(down.0(h.1(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(f.1(x0)))) -> TOP.0(h_flat.0(down.0(f.1(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) TOP.0(up.0(h.0(g.1(x0)))) -> TOP.0(h_flat.0(down.0(g.1(x0)))) The TRS R consists of the following rules: down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.)) h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.0(c.)) -> g_flat.0(down.0(c.)) down.0(h.1(fresh_constant.)) -> h_flat.0(down.1(fresh_constant.)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) down.0(h.0(h.0(x))) -> up.0(c.) down.0(h.0(h.1(x))) -> up.0(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.0(c.)) -> h_flat.0(down.0(c.)) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.0(c.)) down.0(g.1(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.0(c.)) down.0(h.1(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (104) 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(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.)) down.0(h.1(fresh_constant.)) -> h_flat.0(down.1(fresh_constant.)) down.0(h.0(h.1(x))) -> up.0(c.) down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.) = 0 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = 1 + x_1 POL(f_flat.0(x_1)) = x_1 POL(fresh_constant.) = 0 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = 1 + x_1 POL(g_flat.0(x_1)) = x_1 POL(h.0(x_1)) = x_1 POL(h.1(x_1)) = 1 + x_1 POL(h_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(f.0(h.1(x0)))) -> TOP.0(f_flat.0(down.0(h.1(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(h.1(x0)))) -> TOP.0(g_flat.0(down.0(h.1(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(f.1(x0)))) -> TOP.0(h_flat.0(down.0(f.1(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) TOP.0(up.0(h.0(g.1(x0)))) -> TOP.0(h_flat.0(down.0(g.1(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.0(c.)) -> g_flat.0(down.0(c.)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) down.0(h.0(h.0(x))) -> up.0(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.0(c.)) -> h_flat.0(down.0(c.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.0(c.)) down.0(g.1(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.0(c.)) down.0(h.1(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (106) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. ---------------------------------------- (107) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.0(c.)) -> g_flat.0(down.0(c.)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) down.0(h.0(h.0(x))) -> up.0(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.0(c.)) -> h_flat.0(down.0(c.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.0(c.)) down.0(g.1(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.0(c.)) down.0(h.1(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (108) 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(g.0(g.1(x))) -> up.0(h.1(x)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.) = 0 POL(c.) = 0 POL(down.0(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = 1 + x_1 POL(f_flat.0(x_1)) = x_1 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = 1 + x_1 POL(g_flat.0(x_1)) = x_1 POL(h.0(x_1)) = x_1 POL(h.1(x_1)) = x_1 POL(h_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 ---------------------------------------- (109) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.0(c.)) -> g_flat.0(down.0(c.)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) down.0(h.0(h.0(x))) -> up.0(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.0(c.)) -> h_flat.0(down.0(c.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.0(c.)) down.0(g.1(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.0(c.)) down.0(h.1(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (110) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(f.0(f.1(x))) -> up.0(g.1(x)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.) = 0 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = 1 + x_1 POL(f_flat.0(x_1)) = x_1 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(h.0(x_1)) = x_1 POL(h.1(x_1)) = x_1 POL(h_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 ---------------------------------------- (111) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.0(c.)) -> g_flat.0(down.0(c.)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) down.0(h.0(h.0(x))) -> up.0(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.0(c.)) -> h_flat.0(down.0(c.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.0(c.)) -> f_flat.0(down.0(c.)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.0(c.)) down.0(f.1(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.0(c.)) down.0(g.1(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.0(c.)) down.0(h.1(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (112) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (113) TRUE ---------------------------------------- (114) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: h_flat(up(x_1)) -> up(h(x_1)) down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) g_flat(up(x_1)) -> up(g(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) f_flat(up(x_1)) -> up(f(x_1)) down(a) -> up(f(a)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (115) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. down(f(fresh_constant)) down(g(fresh_constant)) down(h(fresh_constant)) ---------------------------------------- (116) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: h_flat(up(x_1)) -> up(h(x_1)) down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) g_flat(up(x_1)) -> up(g(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) f_flat(up(x_1)) -> up(f(x_1)) down(a) -> up(f(a)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all (P,Q,R)-chains. ---------------------------------------- (117) MNOCProof (EQUIVALENT) We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. ---------------------------------------- (118) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: h_flat(up(x_1)) -> up(h(x_1)) down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) g_flat(up(x_1)) -> up(g(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) f_flat(up(x_1)) -> up(f(x_1)) down(a) -> up(f(a)) Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (119) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (120) Complex Obligation (AND) ---------------------------------------- (121) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: h_flat(up(x_1)) -> up(h(x_1)) down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) down(g(c)) -> g_flat(down(c)) g_flat(up(x_1)) -> up(g(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(h(c)) -> h_flat(down(c)) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) down(f(c)) -> f_flat(down(c)) f_flat(up(x_1)) -> up(f(x_1)) down(a) -> up(f(a)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (122) 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. h_flat: 0 a: 0 c: 1 down: 0 f: 0 fresh_constant: 0 up: 0 h: 0 f_flat: 0 TOP: 0 g_flat: 0 g: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (123) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(f.0(h.1(x0)))) -> TOP.0(f_flat.0(down.0(h.1(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(h.1(x0)))) -> TOP.0(g_flat.0(down.0(h.1(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(f.1(x0)))) -> TOP.0(h_flat.0(down.0(f.1(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) TOP.0(up.0(h.0(g.1(x0)))) -> TOP.0(h_flat.0(down.0(g.1(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) h_flat.0(up.1(x_1)) -> up.0(h.1(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) down.0(g.1(c.)) -> g_flat.0(down.1(c.)) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) down.0(h.0(h.0(x))) -> up.1(c.) down.0(h.0(h.1(x))) -> up.1(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(h.1(c.)) -> h_flat.0(down.1(c.)) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) down.0(f.1(c.)) -> f_flat.0(down.1(c.)) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.1(c.)) down.0(g.0(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.1(c.)) down.0(h.0(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (124) 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(g.1(c.)) -> g_flat.0(down.1(c.)) down.0(h.1(c.)) -> h_flat.0(down.1(c.)) down.0(f.1(c.)) -> f_flat.0(down.1(c.)) Used ordering: Polynomial interpretation [POLO]: POL(TOP.0(x_1)) = x_1 POL(a.) = 0 POL(c.) = 0 POL(down.0(x_1)) = 1 + x_1 POL(down.1(x_1)) = x_1 POL(f.0(x_1)) = x_1 POL(f.1(x_1)) = x_1 POL(f_flat.0(x_1)) = x_1 POL(g.0(x_1)) = x_1 POL(g.1(x_1)) = x_1 POL(g_flat.0(x_1)) = x_1 POL(h.0(x_1)) = x_1 POL(h.1(x_1)) = x_1 POL(h_flat.0(x_1)) = x_1 POL(up.0(x_1)) = 1 + x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (125) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(f.0(h.1(x0)))) -> TOP.0(f_flat.0(down.0(h.1(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(h.1(x0)))) -> TOP.0(g_flat.0(down.0(h.1(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(f.1(x0)))) -> TOP.0(h_flat.0(down.0(f.1(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) TOP.0(up.0(h.0(g.1(x0)))) -> TOP.0(h_flat.0(down.0(g.1(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) h_flat.0(up.1(x_1)) -> up.0(h.1(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) down.0(h.0(h.0(x))) -> up.1(c.) down.0(h.0(h.1(x))) -> up.1(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.1(c.)) down.0(g.0(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.1(c.)) down.0(h.0(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (126) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. ---------------------------------------- (127) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) TOP.0(up.0(f.0(h.0(x0)))) -> TOP.0(f_flat.0(down.0(h.0(x0)))) TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) TOP.0(up.0(g.0(h.0(x0)))) -> TOP.0(g_flat.0(down.0(h.0(x0)))) TOP.0(up.0(h.0(f.0(x0)))) -> TOP.0(h_flat.0(down.0(f.0(x0)))) TOP.0(up.0(h.0(g.0(x0)))) -> TOP.0(h_flat.0(down.0(g.0(x0)))) The TRS R consists of the following rules: h_flat.0(up.0(x_1)) -> up.0(h.0(x_1)) h_flat.0(up.1(x_1)) -> up.0(h.1(x_1)) down.0(g.0(g.0(x))) -> up.0(h.0(x)) down.0(g.0(g.1(x))) -> up.0(h.1(x)) down.0(g.0(a.)) -> g_flat.0(down.0(a.)) down.0(g.0(f.0(y8))) -> g_flat.0(down.0(f.0(y8))) down.0(g.0(f.1(y8))) -> g_flat.0(down.0(f.1(y8))) down.0(g.0(h.0(y10))) -> g_flat.0(down.0(h.0(y10))) down.0(g.0(h.1(y10))) -> g_flat.0(down.0(h.1(y10))) g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) down.0(h.0(h.0(x))) -> up.1(c.) down.0(h.0(h.1(x))) -> up.1(c.) down.0(h.0(a.)) -> h_flat.0(down.0(a.)) down.0(h.0(f.0(y12))) -> h_flat.0(down.0(f.0(y12))) down.0(h.0(f.1(y12))) -> h_flat.0(down.0(f.1(y12))) down.0(h.0(g.0(y13))) -> h_flat.0(down.0(g.0(y13))) down.0(h.0(g.1(y13))) -> h_flat.0(down.0(g.1(y13))) down.0(f.0(f.0(x))) -> up.0(g.0(x)) down.0(f.0(f.1(x))) -> up.0(g.1(x)) down.0(f.0(a.)) -> f_flat.0(down.0(a.)) down.0(f.0(g.0(y5))) -> f_flat.0(down.0(g.0(y5))) down.0(f.0(g.1(y5))) -> f_flat.0(down.0(g.1(y5))) down.0(f.0(h.0(y6))) -> f_flat.0(down.0(h.0(y6))) down.0(f.0(h.1(y6))) -> f_flat.0(down.0(h.1(y6))) f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) down.0(a.) -> up.0(f.0(a.)) The set Q consists of the following terms: down.0(a.) down.0(f.0(f.0(x0))) down.0(f.0(f.1(x0))) down.0(g.0(g.0(x0))) down.0(g.0(g.1(x0))) down.0(h.0(h.0(x0))) down.0(h.0(h.1(x0))) down.0(f.0(a.)) down.0(f.0(g.0(x0))) down.0(f.0(g.1(x0))) down.0(f.0(h.0(x0))) down.0(f.0(h.1(x0))) down.0(f.1(c.)) down.0(f.0(fresh_constant.)) down.0(g.0(a.)) down.0(g.0(f.0(x0))) down.0(g.0(f.1(x0))) down.0(g.0(h.0(x0))) down.0(g.0(h.1(x0))) down.0(g.1(c.)) down.0(g.0(fresh_constant.)) down.0(h.0(a.)) down.0(h.0(f.0(x0))) down.0(h.0(f.1(x0))) down.0(h.0(g.0(x0))) down.0(h.0(g.1(x0))) down.0(h.1(c.)) down.0(h.0(fresh_constant.)) f_flat.0(up.0(x0)) f_flat.0(up.1(x0)) g_flat.0(up.0(x0)) g_flat.0(up.1(x0)) h_flat.0(up.0(x0)) h_flat.0(up.1(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (128) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (129) TRUE ---------------------------------------- (130) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: h_flat(up(x_1)) -> up(h(x_1)) down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) g_flat(up(x_1)) -> up(g(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) f_flat(up(x_1)) -> up(f(x_1)) down(a) -> up(f(a)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(f(fresh_constant)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(g(fresh_constant)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) down(h(fresh_constant)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (131) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. down(f(fresh_constant)) down(g(fresh_constant)) down(h(fresh_constant)) ---------------------------------------- (132) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) TOP(up(f(h(x0)))) -> TOP(f_flat(down(h(x0)))) TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) TOP(up(g(h(x0)))) -> TOP(g_flat(down(h(x0)))) TOP(up(h(f(x0)))) -> TOP(h_flat(down(f(x0)))) TOP(up(h(g(x0)))) -> TOP(h_flat(down(g(x0)))) The TRS R consists of the following rules: h_flat(up(x_1)) -> up(h(x_1)) down(g(g(x))) -> up(h(x)) down(g(a)) -> g_flat(down(a)) down(g(f(y8))) -> g_flat(down(f(y8))) down(g(h(y10))) -> g_flat(down(h(y10))) g_flat(up(x_1)) -> up(g(x_1)) down(h(h(x))) -> up(c) down(h(a)) -> h_flat(down(a)) down(h(f(y12))) -> h_flat(down(f(y12))) down(h(g(y13))) -> h_flat(down(g(y13))) down(f(f(x))) -> up(g(x)) down(f(a)) -> f_flat(down(a)) down(f(g(y5))) -> f_flat(down(g(y5))) down(f(h(y6))) -> f_flat(down(h(y6))) f_flat(up(x_1)) -> up(f(x_1)) down(a) -> up(f(a)) The set Q consists of the following terms: down(a) down(f(f(x0))) down(g(g(x0))) down(h(h(x0))) down(f(a)) down(f(g(x0))) down(f(h(x0))) down(f(c)) down(g(a)) down(g(f(x0))) down(g(h(x0))) down(g(c)) down(h(a)) down(h(f(x0))) down(h(g(x0))) down(h(c)) f_flat(up(x0)) g_flat(up(x0)) h_flat(up(x0)) We have to consider all (P,Q,R)-chains.