/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could be proven: (0) OTRS (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 6 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [EQUIVALENT, 0 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) MNOCProof [EQUIVALENT, 3 ms] (16) QDP (17) TransformationProof [EQUIVALENT, 0 ms] (18) QDP (19) TransformationProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) TransformationProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) DependencyGraphProof [EQUIVALENT, 0 ms] (36) AND (37) QDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) QDP (40) QReductionProof [EQUIVALENT, 0 ms] (41) QDP (42) TransformationProof [EQUIVALENT, 0 ms] (43) QDP (44) TransformationProof [EQUIVALENT, 0 ms] (45) QDP (46) DependencyGraphProof [EQUIVALENT, 0 ms] (47) QDP (48) TransformationProof [EQUIVALENT, 0 ms] (49) QDP (50) TransformationProof [EQUIVALENT, 0 ms] (51) QDP (52) TransformationProof [EQUIVALENT, 0 ms] (53) QDP (54) TransformationProof [EQUIVALENT, 0 ms] (55) QDP (56) TransformationProof [EQUIVALENT, 0 ms] (57) QDP (58) TransformationProof [EQUIVALENT, 0 ms] (59) QDP (60) TransformationProof [EQUIVALENT, 0 ms] (61) QDP (62) TransformationProof [EQUIVALENT, 0 ms] (63) QDP (64) TransformationProof [EQUIVALENT, 0 ms] (65) QDP (66) MRRProof [EQUIVALENT, 17 ms] (67) QDP (68) DependencyGraphProof [EQUIVALENT, 0 ms] (69) QDP (70) MRRProof [EQUIVALENT, 0 ms] (71) QDP (72) PisEmptyProof [EQUIVALENT, 0 ms] (73) YES (74) QDP (75) TransformationProof [EQUIVALENT, 0 ms] (76) QDP (77) DependencyGraphProof [EQUIVALENT, 0 ms] (78) QDP (79) TransformationProof [EQUIVALENT, 0 ms] (80) QDP (81) DependencyGraphProof [EQUIVALENT, 0 ms] (82) QDP (83) TransformationProof [EQUIVALENT, 0 ms] (84) QDP (85) DependencyGraphProof [EQUIVALENT, 0 ms] (86) QDP (87) TransformationProof [EQUIVALENT, 0 ms] (88) QDP (89) DependencyGraphProof [EQUIVALENT, 0 ms] (90) QDP (91) UsableRulesProof [EQUIVALENT, 0 ms] (92) QDP (93) TransformationProof [EQUIVALENT, 0 ms] (94) QDP (95) DependencyGraphProof [EQUIVALENT, 0 ms] (96) TRUE ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(f(x, y), z) -> f(c, x) f(x, f(y, z)) -> f(f(x, y), z) a -> f(a, a) Outermost Strategy. ---------------------------------------- (1) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(f(c, x)) down(f(x, f(y, z))) -> up(f(f(x, y), z)) down(a) -> up(f(a, a)) top(up(x)) -> top(down(x)) down(f(c, c)) -> f_flat(down(c), block(c)) down(f(c, c)) -> f_flat(block(c), down(c)) down(f(a, c)) -> f_flat(down(a), block(c)) down(f(a, c)) -> f_flat(block(a), down(c)) down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) down(f(c, a)) -> f_flat(down(c), block(a)) down(f(c, a)) -> f_flat(block(c), down(a)) down(f(a, a)) -> f_flat(down(a), block(a)) down(f(a, a)) -> f_flat(block(a), down(a)) down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), 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. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) TOP(up(x)) -> DOWN(x) DOWN(f(c, c)) -> F_FLAT(down(c), block(c)) DOWN(f(c, c)) -> DOWN(c) DOWN(f(c, c)) -> F_FLAT(block(c), down(c)) DOWN(f(a, c)) -> F_FLAT(down(a), block(c)) DOWN(f(a, c)) -> DOWN(a) DOWN(f(a, c)) -> F_FLAT(block(a), down(c)) DOWN(f(a, c)) -> DOWN(c) DOWN(f(fresh_constant, c)) -> F_FLAT(down(fresh_constant), block(c)) DOWN(f(fresh_constant, c)) -> DOWN(fresh_constant) DOWN(f(fresh_constant, c)) -> F_FLAT(block(fresh_constant), down(c)) DOWN(f(fresh_constant, c)) -> DOWN(c) DOWN(f(c, a)) -> F_FLAT(down(c), block(a)) DOWN(f(c, a)) -> DOWN(c) DOWN(f(c, a)) -> F_FLAT(block(c), down(a)) DOWN(f(c, a)) -> DOWN(a) DOWN(f(a, a)) -> F_FLAT(down(a), block(a)) DOWN(f(a, a)) -> DOWN(a) DOWN(f(a, a)) -> F_FLAT(block(a), down(a)) DOWN(f(fresh_constant, a)) -> F_FLAT(down(fresh_constant), block(a)) DOWN(f(fresh_constant, a)) -> DOWN(fresh_constant) DOWN(f(fresh_constant, a)) -> F_FLAT(block(fresh_constant), down(a)) DOWN(f(fresh_constant, a)) -> DOWN(a) DOWN(f(c, fresh_constant)) -> F_FLAT(down(c), block(fresh_constant)) DOWN(f(c, fresh_constant)) -> DOWN(c) DOWN(f(c, fresh_constant)) -> F_FLAT(block(c), down(fresh_constant)) DOWN(f(c, fresh_constant)) -> DOWN(fresh_constant) DOWN(f(a, fresh_constant)) -> F_FLAT(down(a), block(fresh_constant)) DOWN(f(a, fresh_constant)) -> DOWN(a) DOWN(f(a, fresh_constant)) -> F_FLAT(block(a), down(fresh_constant)) DOWN(f(a, fresh_constant)) -> DOWN(fresh_constant) DOWN(f(fresh_constant, fresh_constant)) -> F_FLAT(down(fresh_constant), block(fresh_constant)) DOWN(f(fresh_constant, fresh_constant)) -> DOWN(fresh_constant) DOWN(f(fresh_constant, fresh_constant)) -> F_FLAT(block(fresh_constant), down(fresh_constant)) The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(f(c, x)) down(f(x, f(y, z))) -> up(f(f(x, y), z)) down(a) -> up(f(a, a)) top(up(x)) -> top(down(x)) down(f(c, c)) -> f_flat(down(c), block(c)) down(f(c, c)) -> f_flat(block(c), down(c)) down(f(a, c)) -> f_flat(down(a), block(c)) down(f(a, c)) -> f_flat(block(a), down(c)) down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) down(f(c, a)) -> f_flat(down(c), block(a)) down(f(c, a)) -> f_flat(block(c), down(a)) down(f(a, a)) -> f_flat(down(a), block(a)) down(f(a, a)) -> f_flat(block(a), down(a)) down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), 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. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 34 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(f(c, x)) down(f(x, f(y, z))) -> up(f(f(x, y), z)) down(a) -> up(f(a, a)) top(up(x)) -> top(down(x)) down(f(c, c)) -> f_flat(down(c), block(c)) down(f(c, c)) -> f_flat(block(c), down(c)) down(f(a, c)) -> f_flat(down(a), block(c)) down(f(a, c)) -> f_flat(block(a), down(c)) down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) down(f(c, a)) -> f_flat(down(c), block(a)) down(f(c, a)) -> f_flat(block(c), down(a)) down(f(a, a)) -> f_flat(down(a), block(a)) down(f(a, a)) -> f_flat(block(a), down(a)) down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), 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. ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(f(c, x)) down(f(x, f(y, z))) -> up(f(f(x, y), z)) down(a) -> up(f(a, a)) down(f(c, c)) -> f_flat(down(c), block(c)) down(f(c, c)) -> f_flat(block(c), down(c)) down(f(a, c)) -> f_flat(down(a), block(c)) down(f(a, c)) -> f_flat(block(a), down(c)) down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) down(f(c, a)) -> f_flat(down(c), block(a)) down(f(c, a)) -> f_flat(block(c), down(a)) down(f(a, a)) -> f_flat(down(a), block(a)) down(f(a, a)) -> f_flat(block(a), down(a)) down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), 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. ---------------------------------------- (9) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))),TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0)))) (TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))),TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2)))) (TOP(up(a)) -> TOP(up(f(a, a))),TOP(up(a)) -> TOP(up(f(a, a)))) (TOP(up(f(c, c))) -> TOP(f_flat(down(c), block(c))),TOP(up(f(c, c))) -> TOP(f_flat(down(c), block(c)))) (TOP(up(f(c, c))) -> TOP(f_flat(block(c), down(c))),TOP(up(f(c, c))) -> TOP(f_flat(block(c), down(c)))) (TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))),TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c)))) (TOP(up(f(a, c))) -> TOP(f_flat(block(a), down(c))),TOP(up(f(a, c))) -> TOP(f_flat(block(a), down(c)))) (TOP(up(f(fresh_constant, c))) -> TOP(f_flat(down(fresh_constant), block(c))),TOP(up(f(fresh_constant, c))) -> TOP(f_flat(down(fresh_constant), block(c)))) (TOP(up(f(fresh_constant, c))) -> TOP(f_flat(block(fresh_constant), down(c))),TOP(up(f(fresh_constant, c))) -> TOP(f_flat(block(fresh_constant), down(c)))) (TOP(up(f(c, a))) -> TOP(f_flat(down(c), block(a))),TOP(up(f(c, a))) -> TOP(f_flat(down(c), block(a)))) (TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))),TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a)))) (TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))),TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a)))) (TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))),TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a)))) (TOP(up(f(fresh_constant, a))) -> TOP(f_flat(down(fresh_constant), block(a))),TOP(up(f(fresh_constant, a))) -> TOP(f_flat(down(fresh_constant), block(a)))) (TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))),TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a)))) (TOP(up(f(c, fresh_constant))) -> TOP(f_flat(down(c), block(fresh_constant))),TOP(up(f(c, fresh_constant))) -> TOP(f_flat(down(c), block(fresh_constant)))) (TOP(up(f(c, fresh_constant))) -> TOP(f_flat(block(c), down(fresh_constant))),TOP(up(f(c, fresh_constant))) -> TOP(f_flat(block(c), down(fresh_constant)))) (TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))),TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant)))) (TOP(up(f(a, fresh_constant))) -> TOP(f_flat(block(a), down(fresh_constant))),TOP(up(f(a, fresh_constant))) -> TOP(f_flat(block(a), down(fresh_constant)))) (TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(down(fresh_constant), block(fresh_constant))),TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(down(fresh_constant), block(fresh_constant)))) (TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(block(fresh_constant), down(fresh_constant))),TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(block(fresh_constant), down(fresh_constant)))) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(a)) -> TOP(up(f(a, a))) TOP(up(f(c, c))) -> TOP(f_flat(down(c), block(c))) TOP(up(f(c, c))) -> TOP(f_flat(block(c), down(c))) TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) TOP(up(f(a, c))) -> TOP(f_flat(block(a), down(c))) TOP(up(f(fresh_constant, c))) -> TOP(f_flat(down(fresh_constant), block(c))) TOP(up(f(fresh_constant, c))) -> TOP(f_flat(block(fresh_constant), down(c))) TOP(up(f(c, a))) -> TOP(f_flat(down(c), block(a))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(down(fresh_constant), block(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(c, fresh_constant))) -> TOP(f_flat(down(c), block(fresh_constant))) TOP(up(f(c, fresh_constant))) -> TOP(f_flat(block(c), down(fresh_constant))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(block(a), down(fresh_constant))) TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(down(fresh_constant), block(fresh_constant))) TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(block(fresh_constant), down(fresh_constant))) The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(f(c, x)) down(f(x, f(y, z))) -> up(f(f(x, y), z)) down(a) -> up(f(a, a)) down(f(c, c)) -> f_flat(down(c), block(c)) down(f(c, c)) -> f_flat(block(c), down(c)) down(f(a, c)) -> f_flat(down(a), block(c)) down(f(a, c)) -> f_flat(block(a), down(c)) down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) down(f(c, a)) -> f_flat(down(c), block(a)) down(f(c, a)) -> f_flat(block(c), down(a)) down(f(a, a)) -> f_flat(down(a), block(a)) down(f(a, a)) -> f_flat(block(a), down(a)) down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), 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. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 13 less nodes. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(f(c, x)) down(f(x, f(y, z))) -> up(f(f(x, y), z)) down(a) -> up(f(a, a)) down(f(c, c)) -> f_flat(down(c), block(c)) down(f(c, c)) -> f_flat(block(c), down(c)) down(f(a, c)) -> f_flat(down(a), block(c)) down(f(a, c)) -> f_flat(block(a), down(c)) down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) down(f(c, a)) -> f_flat(down(c), block(a)) down(f(c, a)) -> f_flat(block(c), down(a)) down(f(a, a)) -> f_flat(down(a), block(a)) down(f(a, a)) -> f_flat(block(a), down(a)) down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), 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. ---------------------------------------- (13) 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. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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. ---------------------------------------- (15) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) at position [0,1] we obtained the following new rules [LPAR04]: (TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))),TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a))))) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))),TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c)))) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))),TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a)))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) at position [0,1] we obtained the following new rules [LPAR04]: (TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))),TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a))))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) at position [0,1] we obtained the following new rules [LPAR04]: (TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))),TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a))))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) at position [0,0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))),TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant)))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: down(a) -> up(f(a, a)) 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), 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(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: down(a) f_flat(up(x0), block(x1)) f_flat(block(x0), 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]. down(a) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))),TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a))))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (36) Complex Obligation (AND) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) 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. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) R is empty. The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) 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]. f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) we obtained the following new rules [LPAR04]: (TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))),TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2)))) (TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2))),TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2)))) (TOP(up(f(c, f(a, a)))) -> TOP(up(f(f(c, a), a))),TOP(up(f(c, f(a, a)))) -> TOP(up(f(f(c, a), a)))) ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))) TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2))) TOP(up(f(c, f(a, a)))) -> TOP(up(f(f(c, a), a))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule TOP(up(f(f(x0, x1), x2))) -> TOP(up(f(c, x0))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(c, z0), z1))) -> TOP(up(f(c, c))),TOP(up(f(f(c, z0), z1))) -> TOP(up(f(c, c)))) (TOP(up(f(f(f(z0, z1), z2), z3))) -> TOP(up(f(c, f(z0, z1)))),TOP(up(f(f(f(z0, z1), z2), z3))) -> TOP(up(f(c, f(z0, z1))))) (TOP(up(f(f(c, a), a))) -> TOP(up(f(c, c))),TOP(up(f(f(c, a), a))) -> TOP(up(f(c, c)))) ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))) TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2))) TOP(up(f(c, f(a, a)))) -> TOP(up(f(f(c, a), a))) TOP(up(f(f(c, z0), z1))) -> TOP(up(f(c, c))) TOP(up(f(f(f(z0, z1), z2), z3))) -> TOP(up(f(c, f(z0, z1)))) TOP(up(f(f(c, a), a))) -> TOP(up(f(c, c))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2))) TOP(up(f(f(f(z0, z1), z2), z3))) -> TOP(up(f(c, f(z0, z1)))) TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))),TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3)))) (TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))),TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3)))) ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(f(z0, z1), z2), z3))) -> TOP(up(f(c, f(z0, z1)))) TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))) TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule TOP(up(f(f(f(z0, z1), z2), z3))) -> TOP(up(f(c, f(z0, z1)))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(f(z0, z1), z2), z3), z4))) -> TOP(up(f(c, f(f(z0, z1), z2)))),TOP(up(f(f(f(f(z0, z1), z2), z3), z4))) -> TOP(up(f(c, f(f(z0, z1), z2))))) (TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))),TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0))))) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))) TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(f(f(f(z0, z1), z2), z3), z4))) -> TOP(up(f(c, f(f(z0, z1), z2)))) TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule TOP(up(f(c, f(x1, x2)))) -> TOP(up(f(f(c, x1), x2))) we obtained the following new rules [LPAR04]: (TOP(up(f(c, f(f(z0, z1), z2)))) -> TOP(up(f(f(c, f(z0, z1)), z2))),TOP(up(f(c, f(f(z0, z1), z2)))) -> TOP(up(f(f(c, f(z0, z1)), z2)))) (TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0))),TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0)))) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(f(f(f(z0, z1), z2), z3), z4))) -> TOP(up(f(c, f(f(z0, z1), z2)))) TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) TOP(up(f(c, f(f(z0, z1), z2)))) -> TOP(up(f(f(c, f(z0, z1)), z2))) TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(c, f(f(z0, z1), z2)))) -> TOP(up(f(f(c, f(z0, z1)), z2))) we obtained the following new rules [LPAR04]: (TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))),TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2))))) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(f(f(f(z0, z1), z2), z3), z4))) -> TOP(up(f(c, f(f(z0, z1), z2)))) TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0))) TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(f(f(f(z0, z1), z2), z3), z4))) -> TOP(up(f(c, f(f(z0, z1), z2)))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))),TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3)))))) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0))) TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))),TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4))))) (TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))),TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4)))) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0))) TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))) TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(c, f(c, z0)))) -> TOP(up(f(f(c, c), z0))) we obtained the following new rules [LPAR04]: (TOP(up(f(c, f(c, f(y_1, y_2))))) -> TOP(up(f(f(c, c), f(y_1, y_2)))),TOP(up(f(c, f(c, f(y_1, y_2))))) -> TOP(up(f(f(c, c), f(y_1, y_2))))) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))) TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) TOP(up(f(c, f(c, f(y_1, y_2))))) -> TOP(up(f(f(c, c), f(y_1, y_2)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(f(f(c, z0), z1), z2))) -> TOP(up(f(c, f(c, z0)))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) -> TOP(up(f(c, f(c, f(y_0, y_1))))),TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) -> TOP(up(f(c, f(c, f(y_0, y_1)))))) ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))) TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) TOP(up(f(c, f(c, f(y_1, y_2))))) -> TOP(up(f(f(c, c), f(y_1, y_2)))) TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) -> TOP(up(f(c, f(c, f(y_0, y_1))))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule TOP(up(f(f(c, z0), f(x2, x3)))) -> TOP(up(f(f(f(c, z0), x2), x3))) we obtained the following new rules [LPAR04]: (TOP(up(f(f(c, x0), f(x1, f(y_3, f(y_4, y_5)))))) -> TOP(up(f(f(f(c, x0), x1), f(y_3, f(y_4, y_5))))),TOP(up(f(f(c, x0), f(x1, f(y_3, f(y_4, y_5)))))) -> TOP(up(f(f(f(c, x0), x1), f(y_3, f(y_4, y_5)))))) (TOP(up(f(f(c, x0), f(f(y_2, y_3), f(y_4, y_5))))) -> TOP(up(f(f(f(c, x0), f(y_2, y_3)), f(y_4, y_5)))),TOP(up(f(f(c, x0), f(f(y_2, y_3), f(y_4, y_5))))) -> TOP(up(f(f(f(c, x0), f(y_2, y_3)), f(y_4, y_5))))) (TOP(up(f(f(c, f(y_0, y_1)), f(x1, x2)))) -> TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))),TOP(up(f(f(c, f(y_0, y_1)), f(x1, x2)))) -> TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2)))) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))) TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) TOP(up(f(c, f(c, f(y_1, y_2))))) -> TOP(up(f(f(c, c), f(y_1, y_2)))) TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) -> TOP(up(f(c, f(c, f(y_0, y_1))))) TOP(up(f(f(c, x0), f(x1, f(y_3, f(y_4, y_5)))))) -> TOP(up(f(f(f(c, x0), x1), f(y_3, f(y_4, y_5))))) TOP(up(f(f(c, x0), f(f(y_2, y_3), f(y_4, y_5))))) -> TOP(up(f(f(f(c, x0), f(y_2, y_3)), f(y_4, y_5)))) TOP(up(f(f(c, f(y_0, y_1)), f(x1, x2)))) -> TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) -> TOP(up(f(c, f(f(x0, x1), f(y_2, y_3))))) TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) -> TOP(up(f(c, f(c, f(y_0, y_1))))) Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = 2*x_1 POL(c) = 0 POL(f(x_1, x_2)) = 1 + x_1 + x_2 POL(up(x_1)) = 2*x_1 ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(c, f(f(x0, x1), f(y_1, y_2))))) -> TOP(up(f(f(c, f(x0, x1)), f(y_1, y_2)))) TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) TOP(up(f(c, f(c, f(y_1, y_2))))) -> TOP(up(f(f(c, c), f(y_1, y_2)))) TOP(up(f(f(c, x0), f(x1, f(y_3, f(y_4, y_5)))))) -> TOP(up(f(f(f(c, x0), x1), f(y_3, f(y_4, y_5))))) TOP(up(f(f(c, x0), f(f(y_2, y_3), f(y_4, y_5))))) -> TOP(up(f(f(f(c, x0), f(y_2, y_3)), f(y_4, y_5)))) TOP(up(f(f(c, f(y_0, y_1)), f(x1, x2)))) -> TOP(up(f(f(f(c, f(y_0, y_1)), x1), x2))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: TOP(up(f(f(f(x0, x1), x2), f(x3, f(y_3, y_4))))) -> TOP(up(f(f(f(f(x0, x1), x2), x3), f(y_3, y_4)))) TOP(up(f(f(f(x0, x1), f(y_2, y_3)), f(x3, x4)))) -> TOP(up(f(f(f(f(x0, x1), f(y_2, y_3)), x3), x4))) Used ordering: Polynomial interpretation [POLO]: POL(TOP(x_1)) = 2*x_1 POL(f(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(up(x_1)) = 2*x_1 ---------------------------------------- (71) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (73) YES ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, c))) -> TOP(up(f(f(a, a), c))),TOP(up(f(a, c))) -> TOP(up(f(f(a, a), c)))) ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) TOP(up(f(a, c))) -> TOP(up(f(f(a, a), c))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, a))) -> TOP(up(f(f(a, a), a))),TOP(up(f(a, a))) -> TOP(up(f(f(a, a), a)))) ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) TOP(up(f(a, a))) -> TOP(up(f(f(a, a), a))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, a))) -> TOP(up(f(a, f(a, a)))),TOP(up(f(a, a))) -> TOP(up(f(a, f(a, a))))) ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) TOP(up(f(a, a))) -> TOP(up(f(a, f(a, a)))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (87) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(fresh_constant, a))) -> TOP(up(f(fresh_constant, f(a, a)))),TOP(up(f(fresh_constant, a))) -> TOP(up(f(fresh_constant, f(a, a))))) ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) TOP(up(f(fresh_constant, a))) -> TOP(up(f(fresh_constant, f(a, a)))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (89) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: 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)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (91) 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. ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) The TRS R consists of the following rules: f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(f(a, fresh_constant))) -> TOP(up(f(f(a, a), fresh_constant))),TOP(up(f(a, fresh_constant))) -> TOP(up(f(f(a, a), fresh_constant)))) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, fresh_constant))) -> TOP(up(f(f(a, a), fresh_constant))) The TRS R consists of the following rules: f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) The set Q consists of the following terms: f_flat(up(x0), block(x1)) f_flat(block(x0), up(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (96) TRUE