/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) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 81 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] (15) QDP (16) UsableRulesReductionPairsProof [EQUIVALENT, 1 ms] (17) QDP (18) DependencyGraphProof [EQUIVALENT, 0 ms] (19) TRUE (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QReductionProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [SOUND, 0 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) Trivial-Transformation [SOUND, 0 ms] (34) QTRS (35) QTRSRRRProof [EQUIVALENT, 48 ms] (36) QTRS (37) DependencyPairsProof [EQUIVALENT, 0 ms] (38) QDP (39) DependencyGraphProof [EQUIVALENT, 0 ms] (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) TransformationProof [EQUIVALENT, 0 ms] (44) QDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 0 ms] (48) QDP (49) DependencyGraphProof [EQUIVALENT, 0 ms] (50) QDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) QDP (53) ATransformationProof [EQUIVALENT, 0 ms] (54) QDP (55) NonTerminationLoopProof [COMPLETE, 0 ms] (56) NO (57) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (58) QTRS (59) QTRSRRRProof [EQUIVALENT, 85 ms] (60) QTRS (61) DependencyPairsProof [EQUIVALENT, 11 ms] (62) QDP (63) DependencyGraphProof [EQUIVALENT, 0 ms] (64) AND (65) QDP (66) UsableRulesProof [EQUIVALENT, 0 ms] (67) QDP (68) QDPSizeChangeProof [EQUIVALENT, 0 ms] (69) YES (70) QDP (71) UsableRulesProof [EQUIVALENT, 0 ms] (72) QDP (73) TransformationProof [EQUIVALENT, 0 ms] (74) QDP (75) DependencyGraphProof [EQUIVALENT, 0 ms] (76) QDP (77) SplitQDPProof [EQUIVALENT, 0 ms] (78) AND (79) QDP (80) SemLabProof [SOUND, 0 ms] (81) QDP (82) DependencyGraphProof [EQUIVALENT, 0 ms] (83) QDP (84) UsableRulesReductionPairsProof [EQUIVALENT, 13 ms] (85) QDP (86) DependencyGraphProof [EQUIVALENT, 0 ms] (87) QDP (88) MRRProof [EQUIVALENT, 19 ms] (89) QDP (90) PisEmptyProof [SOUND, 0 ms] (91) TRUE (92) QDP (93) SplitQDPProof [EQUIVALENT, 0 ms] (94) AND (95) QDP (96) SemLabProof [SOUND, 0 ms] (97) QDP (98) DependencyGraphProof [EQUIVALENT, 0 ms] (99) QDP (100) MRRProof [EQUIVALENT, 17 ms] (101) QDP (102) MRRProof [EQUIVALENT, 40 ms] (103) QDP (104) DependencyGraphProof [EQUIVALENT, 0 ms] (105) QDP (106) PisEmptyProof [SOUND, 0 ms] (107) TRUE (108) QDP (109) SplitQDPProof [EQUIVALENT, 0 ms] (110) AND (111) QDP (112) SemLabProof [SOUND, 0 ms] (113) QDP (114) DependencyGraphProof [EQUIVALENT, 0 ms] (115) QDP (116) MRRProof [EQUIVALENT, 45 ms] (117) QDP (118) MRRProof [EQUIVALENT, 0 ms] (119) QDP (120) DependencyGraphProof [EQUIVALENT, 0 ms] (121) QDP (122) PisEmptyProof [SOUND, 0 ms] (123) TRUE (124) QDP ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(0, 1) -> f(2, 2) 2 -> 0 2 -> 1 f(2, 1) -> 2 f(0, 2) -> 2 Outermost Strategy. ---------------------------------------- (1) Thiemann-SpecialC-Transformation (EQUIVALENT) We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) redex_f(0, 1) -> result_f(f(2, 2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(2, 1) -> result_f(2) redex_f(0, 2) -> result_f(2) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(1) = 0 POL(2) = 0 POL(check_f(x_1)) = x_1 POL(f(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(go_up(x_1)) = x_1 POL(in_f_1(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(in_f_2(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(redex_f(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(reduce(x_1)) = x_1 POL(result_f(x_1)) = x_1 POL(top(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: redex_f(2, 1) -> result_f(2) redex_f(0, 2) -> result_f(2) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) redex_f(0, 1) -> result_f(f(2, 2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) 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, x_2)) -> CHECK_F(redex_f(x_1, x_2)) REDUCE(f(x_1, x_2)) -> REDEX_F(x_1, x_2) CHECK_F(redex_f(x_1, x_2)) -> IN_F_1(reduce(x_1), x_2) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) CHECK_F(redex_f(x_1, x_2)) -> IN_F_2(x_1, reduce(x_2)) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) redex_f(0, 1) -> result_f(f(2, 2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) redex_f(0, 1) -> result_f(f(2, 2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_f(0, 1) -> result_f(f(2, 2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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, x1)) reduce(2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_f(0, 1) -> result_f(f(2, 2)) The set Q consists of the following terms: redex_f(0, 1) redex_f(2, 1) redex_f(0, 2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: redex_f(0, 1) -> result_f(f(2, 2)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 2 POL(1) = 2 POL(2) = 0 POL(CHECK_F(x_1)) = 2*x_1 POL(REDUCE(x_1)) = 2*x_1 POL(f(x_1, x_2)) = 2*x_1 + 2*x_2 POL(redex_f(x_1, x_2)) = 2*x_1 + x_2 POL(result_f(x_1)) = 2*x_1 ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1, x_2)) -> CHECK_F(redex_f(x_1, x_2)) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) R is empty. The set Q consists of the following terms: redex_f(0, 1) redex_f(2, 1) redex_f(0, 2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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, x_2)) -> CHECK_F(redex_f(x_1, x_2)) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = 2*x_1 POL(REDUCE(x_1)) = 2*x_1 POL(f(x_1, x_2)) = 2*x_1 + 2*x_2 POL(redex_f(x_1, x_2)) = 2*x_1 + x_2 ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_1) CHECK_F(redex_f(x_1, x_2)) -> REDUCE(x_2) R is empty. The set Q consists of the following terms: redex_f(0, 1) redex_f(2, 1) redex_f(0, 2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (19) TRUE ---------------------------------------- (20) 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, x_2)) -> check_f(redex_f(x_1, x_2)) redex_f(0, 1) -> result_f(f(2, 2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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. ---------------------------------------- (22) 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, x_2)) -> check_f(redex_f(x_1, x_2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(0, 1) -> result_f(f(2, 2)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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)) ---------------------------------------- (24) 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, x_2)) -> check_f(redex_f(x_1, x_2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(0, 1) -> result_f(f(2, 2)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (SOUND) 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, x1))) -> TOP(check_f(redex_f(x0, x1))),TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1)))) (TOP(go_up(2)) -> TOP(go_up(0)),TOP(go_up(2)) -> TOP(go_up(0))) (TOP(go_up(2)) -> TOP(go_up(1)),TOP(go_up(2)) -> TOP(go_up(1))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) TOP(go_up(2)) -> TOP(go_up(0)) TOP(go_up(2)) -> TOP(go_up(1)) The TRS R consists of the following rules: reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(0, 1) -> result_f(f(2, 2)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0, x1))) -> TOP(check_f(redex_f(x0, x1))) The TRS R consists of the following rules: reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(0, 1) -> result_f(f(2, 2)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(0, 1) -> result_f(f(2, 2)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1, x_2)) -> check_f(redex_f(x_1, x_2)) reduce(2) -> go_up(0) reduce(2) -> go_up(1) redex_f(0, 1) -> result_f(f(2, 2)) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1, x_2)) -> in_f_1(reduce(x_1), x_2) check_f(redex_f(x_1, x_2)) -> in_f_2(x_1, reduce(x_2)) in_f_2(x_1, go_up(x_2)) -> go_up(f(x_1, x_2)) in_f_1(go_up(x_1), x_2) -> go_up(f(x_1, x_2)) The set Q consists of the following terms: reduce(f(x0, x1)) redex_f(0, 1) reduce(2) redex_f(2, 1) redex_f(0, 2) check_f(result_f(x0)) check_f(redex_f(x0, x1)) in_f_1(go_up(x0), x1) in_f_2(x0, go_up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) Trivial-Transformation (SOUND) We applied the Trivial transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (34) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(0, 1) -> f(2, 2) 2 -> 0 2 -> 1 f(2, 1) -> 2 f(0, 2) -> 2 Q is empty. ---------------------------------------- (35) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(1) = 1 POL(2) = 1 POL(f(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f(2, 1) -> 2 f(0, 2) -> 2 ---------------------------------------- (36) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(0, 1) -> f(2, 2) 2 -> 0 2 -> 1 Q is empty. ---------------------------------------- (37) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(2, 2) F(0, 1) -> 2^1 The TRS R consists of the following rules: f(0, 1) -> f(2, 2) 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(2, 2) The TRS R consists of the following rules: f(0, 1) -> f(2, 2) 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) 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. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(2, 2) The TRS R consists of the following rules: 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule F(0, 1) -> F(2, 2) at position [0] we obtained the following new rules [LPAR04]: (F(0, 1) -> F(0, 2),F(0, 1) -> F(0, 2)) (F(0, 1) -> F(1, 2),F(0, 1) -> F(1, 2)) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(0, 2) F(0, 1) -> F(1, 2) The TRS R consists of the following rules: 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(0, 2) The TRS R consists of the following rules: 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule F(0, 1) -> F(0, 2) at position [1] we obtained the following new rules [LPAR04]: (F(0, 1) -> F(0, 0),F(0, 1) -> F(0, 0)) (F(0, 1) -> F(0, 1),F(0, 1) -> F(0, 1)) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(0, 0) F(0, 1) -> F(0, 1) The TRS R consists of the following rules: 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(0, 1) The TRS R consists of the following rules: 2 -> 0 2 -> 1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: F(0, 1) -> F(0, 1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: 0(1) -> 0(1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) 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 = 0(1) evaluates to t =0(1) 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 0(1) to 0(1). ---------------------------------------- (56) NO ---------------------------------------- (57) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (58) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(2, 1)) -> up(2) down(f(0, 2)) -> up(2) top(up(x)) -> top(down(x)) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. ---------------------------------------- (59) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(1) = 1 POL(2) = 1 POL(block(x_1)) = x_1 POL(down(x_1)) = x_1 POL(f(x_1, x_2)) = 2*x_1 + 2*x_2 POL(f_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(fresh_constant) = 0 POL(top(x_1)) = x_1 POL(up(x_1)) = x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(f(2, 1)) -> up(2) down(f(0, 2)) -> up(2) ---------------------------------------- (60) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) top(up(x)) -> top(down(x)) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. ---------------------------------------- (61) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (62) 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(f(y4, y5), y6)) -> F_FLAT(down(f(y4, y5)), block(y6)) DOWN(f(f(y4, y5), y6)) -> DOWN(f(y4, y5)) DOWN(f(f(y4, y5), y6)) -> F_FLAT(block(f(y4, y5)), down(y6)) DOWN(f(f(y4, y5), y6)) -> DOWN(y6) DOWN(f(1, y8)) -> F_FLAT(down(1), block(y8)) DOWN(f(1, y8)) -> DOWN(1) DOWN(f(1, y8)) -> F_FLAT(block(1), down(y8)) DOWN(f(1, y8)) -> DOWN(y8) DOWN(f(fresh_constant, y10)) -> F_FLAT(down(fresh_constant), block(y10)) DOWN(f(fresh_constant, y10)) -> DOWN(fresh_constant) DOWN(f(fresh_constant, y10)) -> F_FLAT(block(fresh_constant), down(y10)) DOWN(f(fresh_constant, y10)) -> DOWN(y10) DOWN(f(y11, f(y12, y13))) -> F_FLAT(down(y11), block(f(y12, y13))) DOWN(f(y11, f(y12, y13))) -> DOWN(y11) DOWN(f(y11, f(y12, y13))) -> F_FLAT(block(y11), down(f(y12, y13))) DOWN(f(y11, f(y12, y13))) -> DOWN(f(y12, y13)) DOWN(f(y26, 0)) -> F_FLAT(down(y26), block(0)) DOWN(f(y26, 0)) -> DOWN(y26) DOWN(f(y26, 0)) -> F_FLAT(block(y26), down(0)) DOWN(f(y26, 0)) -> DOWN(0) DOWN(f(2, 2)) -> F_FLAT(down(2), block(2)) DOWN(f(2, 2)) -> DOWN(2) DOWN(f(2, 2)) -> F_FLAT(block(2), down(2)) DOWN(f(y35, fresh_constant)) -> F_FLAT(down(y35), block(fresh_constant)) DOWN(f(y35, fresh_constant)) -> DOWN(y35) DOWN(f(y35, fresh_constant)) -> F_FLAT(block(y35), down(fresh_constant)) DOWN(f(y35, fresh_constant)) -> DOWN(fresh_constant) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) top(up(x)) -> top(down(x)) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 20 less nodes. ---------------------------------------- (64) Complex Obligation (AND) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(f(y4, y5), y6)) -> DOWN(y6) DOWN(f(f(y4, y5), y6)) -> DOWN(f(y4, y5)) DOWN(f(1, y8)) -> DOWN(y8) DOWN(f(fresh_constant, y10)) -> DOWN(y10) DOWN(f(y11, f(y12, y13))) -> DOWN(y11) DOWN(f(y11, f(y12, y13))) -> DOWN(f(y12, y13)) DOWN(f(y26, 0)) -> DOWN(y26) DOWN(f(y35, fresh_constant)) -> DOWN(y35) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) top(up(x)) -> top(down(x)) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) 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. ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(f(y4, y5), y6)) -> DOWN(y6) DOWN(f(f(y4, y5), y6)) -> DOWN(f(y4, y5)) DOWN(f(1, y8)) -> DOWN(y8) DOWN(f(fresh_constant, y10)) -> DOWN(y10) DOWN(f(y11, f(y12, y13))) -> DOWN(y11) DOWN(f(y11, f(y12, y13))) -> DOWN(f(y12, y13)) DOWN(f(y26, 0)) -> DOWN(y26) DOWN(f(y35, fresh_constant)) -> DOWN(y35) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) 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(f(f(y4, y5), y6)) -> DOWN(y6) The graph contains the following edges 1 > 1 *DOWN(f(f(y4, y5), y6)) -> DOWN(f(y4, y5)) The graph contains the following edges 1 > 1 *DOWN(f(1, y8)) -> DOWN(y8) The graph contains the following edges 1 > 1 *DOWN(f(fresh_constant, y10)) -> DOWN(y10) The graph contains the following edges 1 > 1 *DOWN(f(y11, f(y12, y13))) -> DOWN(y11) The graph contains the following edges 1 > 1 *DOWN(f(y11, f(y12, y13))) -> DOWN(f(y12, y13)) The graph contains the following edges 1 > 1 *DOWN(f(y26, 0)) -> DOWN(y26) The graph contains the following edges 1 > 1 *DOWN(f(y35, fresh_constant)) -> DOWN(y35) The graph contains the following edges 1 > 1 ---------------------------------------- (69) YES ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) top(up(x)) -> top(down(x)) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) 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. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(0, 1))) -> TOP(up(f(2, 2))),TOP(up(f(0, 1))) -> TOP(up(f(2, 2)))) (TOP(up(2)) -> TOP(up(0)),TOP(up(2)) -> TOP(up(0))) (TOP(up(2)) -> TOP(up(1)),TOP(up(2)) -> TOP(up(1))) (TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))),TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2)))) (TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))),TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2)))) (TOP(up(f(1, x0))) -> TOP(f_flat(down(1), block(x0))),TOP(up(f(1, x0))) -> TOP(f_flat(down(1), block(x0)))) (TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))),TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0)))) (TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(down(fresh_constant), block(x0))),TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(down(fresh_constant), block(x0)))) (TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))),TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0)))) (TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))),TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2))))) (TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))),TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2))))) (TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))),TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0)))) (TOP(up(f(x0, 0))) -> TOP(f_flat(block(x0), down(0))),TOP(up(f(x0, 0))) -> TOP(f_flat(block(x0), down(0)))) (TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))),TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2)))) (TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))),TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2)))) (TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))),TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant)))) (TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(block(x0), down(fresh_constant))),TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(block(x0), down(fresh_constant)))) ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(2)) -> TOP(up(0)) TOP(up(2)) -> TOP(up(1)) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(down(1), block(x0))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(down(fresh_constant), block(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, 0))) -> TOP(f_flat(block(x0), down(0))) TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(block(x0), down(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (78) Complex Obligation (AND) ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(down(fresh_constant), block(y10)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) down(f(y35, fresh_constant)) -> f_flat(block(y35), down(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) 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. block: 0 down: 0 f: 0 0: 0 fresh_constant: 1 up: 0 1: 0 2: 0 f_flat: 0 TOP: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.0-1(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.1(x0))) TOP.0(up.0(f.1-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.1(fresh_constant.), down.0(x0))) TOP.0(up.0(f.1-1(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.1(fresh_constant.), down.1(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.1-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-1(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(fresh_constant.))) TOP.0(up.0(f.1-1(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.1(x0), block.1(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(down.0(1.), block.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(down.0(1.), block.1(y8)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.0(y10)) down.0(f.1-1(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.1(y10)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.0(y10)) down.0(f.1-1(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.1(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.1(fresh_constant.)) down.0(f.1-1(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.1(fresh_constant.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(block.0(y35), down.1(fresh_constant.)) down.0(f.1-1(y35, fresh_constant.)) -> f_flat.0-0(block.1(y35), down.1(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 12 less nodes. ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.1-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.1(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-1(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(down.0(1.), block.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(down.0(1.), block.1(y8)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.0(y10)) down.0(f.1-1(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.1(y10)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.0(y10)) down.0(f.1-1(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.1(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.1(fresh_constant.)) down.0(f.1-1(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.1(fresh_constant.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(block.0(y35), down.1(fresh_constant.)) down.0(f.1-1(y35, fresh_constant.)) -> f_flat.0-0(block.1(y35), down.1(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: down.0(f.1-1(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.1(y10)) down.0(f.1-1(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.1(y10)) down.0(f.1-1(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.1(fresh_constant.)) down.0(f.1-1(y35, fresh_constant.)) -> f_flat.0-0(block.1(y35), down.1(fresh_constant.)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0.) = 1 POL(1.) = 1 POL(2.) = 1 POL(TOP.0(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0-0(x_1, x_2)) = x_1 + x_2 POL(f.0-1(x_1, x_2)) = x_1 + x_2 POL(f.1-0(x_1, x_2)) = x_1 + x_2 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(fresh_constant.) = 0 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.1-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.1(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-1(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(down.0(1.), block.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(down.0(1.), block.1(y8)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.0(y10)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.1(fresh_constant.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(block.0(y35), down.1(fresh_constant.)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.1-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.1(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-1(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(down.0(1.), block.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(down.0(1.), block.1(y8)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.0(y10)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.1(fresh_constant.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(block.0(y35), down.1(fresh_constant.)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) 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-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(down.1(fresh_constant.), block.0(y10)) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(block.0(y35), down.1(fresh_constant.)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(1.) = 0 POL(2.) = 0 POL(TOP.0(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = 1 + x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0-0(x_1, x_2)) = x_1 + x_2 POL(f.0-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f.1-0(x_1, x_2)) = 1 + x_1 + x_2 POL(f.1-1(x_1, x_2)) = x_1 + x_2 POL(f_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(fresh_constant.) = 0 POL(up.0(x_1)) = x_1 ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.1-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.1(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-1(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(down.0(1.), block.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(down.0(1.), block.1(y8)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.1-0(fresh_constant., y10)) -> f_flat.0-0(block.1(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-1(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.1(fresh_constant.)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (91) TRUE ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (94) Complex Obligation (AND) ---------------------------------------- (95) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(down(1), block(y8)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (96) 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. block: 0 down: 0 f: 0 0: 0 fresh_constant: 0 up: 0 1: 1 2: 0 f_flat: 0 TOP: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-1(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.1(x2))) TOP.0(up.0(f.1-0(1., x0))) -> TOP.0(f_flat.0-0(block.1(1.), down.0(x0))) TOP.0(up.0(f.1-1(1., x0))) -> TOP.0(f_flat.0-0(block.1(1.), down.1(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-1(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.1(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.1-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) TOP.0(up.0(f.1-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-1(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.1(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.1-0(1., y8)) -> f_flat.0-0(down.1(1.), block.0(y8)) down.0(f.1-1(1., y8)) -> f_flat.0-0(down.1(1.), block.1(y8)) down.0(f.1-0(1., y8)) -> f_flat.0-0(block.1(1.), down.0(y8)) down.0(f.1-1(1., y8)) -> f_flat.0-0(block.1(1.), down.1(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-1(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.1(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) down.0(f.1-0(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (98) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 12 less nodes. ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-1(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.1-0(1., x0))) -> TOP.0(f_flat.0-0(block.1(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-1(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.1(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.1-0(1., y8)) -> f_flat.0-0(down.1(1.), block.0(y8)) down.0(f.1-1(1., y8)) -> f_flat.0-0(down.1(1.), block.1(y8)) down.0(f.1-0(1., y8)) -> f_flat.0-0(block.1(1.), down.0(y8)) down.0(f.1-1(1., y8)) -> f_flat.0-0(block.1(1.), down.1(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-1(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.1(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) down.0(f.1-0(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) 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-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.1-0(1., y8)) -> f_flat.0-0(down.1(1.), block.0(y8)) down.0(f.0-1(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.1(y10)) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(down.1(y26), block.0(0.)) down.0(f.1-0(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.0(fresh_constant.)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 1 POL(1.) = 0 POL(2.) = 1 POL(TOP.0(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = 1 + x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0-0(x_1, x_2)) = x_1 + x_2 POL(f.0-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f.1-0(x_1, x_2)) = 1 + x_1 + x_2 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(fresh_constant.) = 0 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-1(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.1-0(1., x0))) -> TOP.0(f_flat.0-0(block.1(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-1(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.1(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.1-1(1., y8)) -> f_flat.0-0(down.1(1.), block.1(y8)) down.0(f.1-0(1., y8)) -> f_flat.0-0(block.1(1.), down.0(y8)) down.0(f.1-1(1., y8)) -> f_flat.0-0(block.1(1.), down.1(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) 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.1-1(1., y8)) -> f_flat.0-0(down.1(1.), block.1(y8)) down.0(f.1-1(1., y8)) -> f_flat.0-0(block.1(1.), down.1(y8)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(1.) = 0 POL(2.) = 0 POL(TOP.0(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0-0(x_1, x_2)) = x_1 + x_2 POL(f.0-1(x_1, x_2)) = x_1 + x_2 POL(f.1-0(x_1, x_2)) = x_1 + x_2 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(fresh_constant.) = 0 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-1(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.1-0(1., x0))) -> TOP.0(f_flat.0-0(block.1(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-1(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.1(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.1-0(1., y8)) -> f_flat.0-0(block.1(1.), down.0(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (104) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-1(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.1-0(1., x0))) -> TOP.0(f_flat.0-0(block.1(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(0.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.0-1(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.0(0.) down.0(2.) -> up.1(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.1-0(1., y8)) -> f_flat.0-0(block.1(1.), down.0(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(down.0(y26), block.0(0.)) down.0(f.0-0(y26, 0.)) -> f_flat.0-0(block.0(y26), down.0(0.)) down.0(f.1-0(y26, 0.)) -> f_flat.0-0(block.1(y26), down.0(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (106) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (107) TRUE ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (110) Complex Obligation (AND) ---------------------------------------- (111) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(y26, 0)) -> f_flat(block(y26), down(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (112) 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. block: 0 down: 0 f: 0 0: 1 fresh_constant: 0 up: 0 1: 0 2: 0 f_flat: 0 TOP: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (113) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.1-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.1(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.0-1(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.1(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-1(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.1(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-1(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(0.))) TOP.0(up.0(f.1-1(x0, 0.))) -> TOP.0(f_flat.0-0(down.1(x0), block.1(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) TOP.0(up.0(f.1-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.1(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.1-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.1(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-1(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.1(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(down.0(y26), block.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(down.1(y26), block.1(0.)) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(block.0(y26), down.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(block.1(y26), down.1(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) down.0(f.1-0(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (114) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 12 less nodes. ---------------------------------------- (115) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.1-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-1(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.1-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.1(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-1(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.1(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(down.0(y26), block.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(down.1(y26), block.1(0.)) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(block.0(y26), down.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(block.1(y26), down.1(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) down.0(f.1-0(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (116) 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-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.1(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.1(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.1(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.1(y6)) down.0(f.0-1(1., y8)) -> f_flat.0-0(block.0(1.), down.1(y8)) down.0(f.0-1(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.1(y10)) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.1(y11), block.0(f.1-1(y12, y13))) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(block.0(y26), down.1(0.)) down.0(f.1-0(y35, fresh_constant.)) -> f_flat.0-0(down.1(y35), block.0(fresh_constant.)) f_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(f.1-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(f.1-1(x_1, x_2)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(1.) = 1 POL(2.) = 1 POL(TOP.0(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = 1 + x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0-0(x_1, x_2)) = x_1 + x_2 POL(f.0-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f.1-0(x_1, x_2)) = 1 + x_1 + x_2 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(fresh_constant.) = 0 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (117) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.1-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-1(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.1-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.1(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(down.0(y26), block.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(down.1(y26), block.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(block.1(y26), down.1(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (118) 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.1-1(y26, 0.)) -> f_flat.0-0(down.1(y26), block.1(0.)) down.0(f.1-1(y26, 0.)) -> f_flat.0-0(block.1(y26), down.1(0.)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(1.) = 0 POL(2.) = 0 POL(TOP.0(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = x_1 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(f.0-0(x_1, x_2)) = x_1 + x_2 POL(f.0-1(x_1, x_2)) = x_1 + x_2 POL(f.1-0(x_1, x_2)) = x_1 + x_2 POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(f_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(fresh_constant.) = 0 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (119) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.1-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-1(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(0.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.1-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.1(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(down.0(y26), block.1(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (120) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (121) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(down.0(2.), block.0(2.))) TOP.0(up.0(f.1-0(0., 1.))) -> TOP.0(up.0(f.0-0(2., 2.))) TOP.0(up.0(f.0-0(2., 2.))) -> TOP.0(f_flat.0-0(block.0(2.), down.0(2.))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.0-1(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.0(x2))) TOP.0(up.0(f.0-1(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(down.0(f.1-0(x0, x1)), block.1(x2))) TOP.0(up.0(f.0-0(f.0-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.0-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.0-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-0(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-0(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(f.1-1(x0, x1), x2))) -> TOP.0(f_flat.0-0(block.0(f.1-1(x0, x1)), down.0(x2))) TOP.0(up.0(f.0-0(1., x0))) -> TOP.0(f_flat.0-0(block.0(1.), down.0(x0))) TOP.0(up.0(f.0-0(fresh_constant., x0))) -> TOP.0(f_flat.0-0(block.0(fresh_constant.), down.0(x0))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-1(x1, x2)))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(f.1-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.0-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.0(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-0(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.0-1(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.0-1(x1, x2)))) TOP.0(up.0(f.1-0(x0, f.1-0(x1, x2)))) -> TOP.0(f_flat.0-0(block.1(x0), down.0(f.1-0(x1, x2)))) TOP.0(up.0(f.0-1(x0, 0.))) -> TOP.0(f_flat.0-0(down.0(x0), block.1(0.))) TOP.0(up.0(f.0-0(x0, fresh_constant.))) -> TOP.0(f_flat.0-0(down.0(x0), block.0(fresh_constant.))) The TRS R consists of the following rules: down.0(f.1-0(0., 1.)) -> up.0(f.0-0(2., 2.)) down.0(2.) -> up.1(0.) down.0(2.) -> up.0(1.) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.0-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.0-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-0(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-0(y4, y5)), block.1(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.0(y6)) down.0(f.0-1(f.1-1(y4, y5), y6)) -> f_flat.0-0(down.0(f.1-1(y4, y5)), block.1(y6)) down.0(f.0-0(f.0-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.0-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.0-1(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-0(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-0(y4, y5)), down.0(y6)) down.0(f.0-0(f.1-1(y4, y5), y6)) -> f_flat.0-0(block.0(f.1-1(y4, y5)), down.0(y6)) down.0(f.0-0(1., y8)) -> f_flat.0-0(block.0(1.), down.0(y8)) down.0(f.0-0(fresh_constant., y10)) -> f_flat.0-0(block.0(fresh_constant.), down.0(y10)) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(down.0(y11), block.0(f.1-1(y12, y13))) down.0(f.0-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-0(y12, y13))) down.0(f.0-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.0-1(y12, y13))) down.0(f.0-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-0(y12, y13))) down.0(f.0-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.0(y11), down.0(f.1-1(y12, y13))) down.0(f.1-0(y11, f.0-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-0(y12, y13))) down.0(f.1-0(y11, f.0-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.0-1(y12, y13))) down.0(f.1-0(y11, f.1-0(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-0(y12, y13))) down.0(f.1-0(y11, f.1-1(y12, y13))) -> f_flat.0-0(block.1(y11), down.0(f.1-1(y12, y13))) down.0(f.0-1(y26, 0.)) -> f_flat.0-0(down.0(y26), block.1(0.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(down.0(2.), block.0(2.)) down.0(f.0-0(2., 2.)) -> f_flat.0-0(block.0(2.), down.0(2.)) down.0(f.0-0(y35, fresh_constant.)) -> f_flat.0-0(down.0(y35), block.0(fresh_constant.)) f_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(f.1-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(f.0-0(x_1, x_2)) f_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(f.0-1(x_1, x_2)) f_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(f.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (122) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (123) TRUE ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(2, 2))) -> TOP(f_flat(down(2), block(2))) TOP(up(f(0, 1))) -> TOP(up(f(2, 2))) TOP(up(f(2, 2))) -> TOP(f_flat(block(2), down(2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(down(f(x0, x1)), block(x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(f_flat(block(f(x0, x1)), down(x2))) TOP(up(f(1, x0))) -> TOP(f_flat(block(1), down(x0))) TOP(up(f(fresh_constant, x0))) -> TOP(f_flat(block(fresh_constant), down(x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(down(x0), block(f(x1, x2)))) TOP(up(f(x0, f(x1, x2)))) -> TOP(f_flat(block(x0), down(f(x1, x2)))) TOP(up(f(x0, 0))) -> TOP(f_flat(down(x0), block(0))) TOP(up(f(x0, fresh_constant))) -> TOP(f_flat(down(x0), block(fresh_constant))) The TRS R consists of the following rules: down(f(0, 1)) -> up(f(2, 2)) down(2) -> up(0) down(2) -> up(1) down(f(f(y4, y5), y6)) -> f_flat(down(f(y4, y5)), block(y6)) down(f(f(y4, y5), y6)) -> f_flat(block(f(y4, y5)), down(y6)) down(f(1, y8)) -> f_flat(block(1), down(y8)) down(f(fresh_constant, y10)) -> f_flat(block(fresh_constant), down(y10)) down(f(y11, f(y12, y13))) -> f_flat(down(y11), block(f(y12, y13))) down(f(y11, f(y12, y13))) -> f_flat(block(y11), down(f(y12, y13))) down(f(y26, 0)) -> f_flat(down(y26), block(0)) down(f(2, 2)) -> f_flat(down(2), block(2)) down(f(2, 2)) -> f_flat(block(2), down(2)) down(f(y35, fresh_constant)) -> f_flat(down(y35), block(fresh_constant)) f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains.