/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/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, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [EQUIVALENT, 3 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) AND (13) QDP (14) UsableRulesProof [EQUIVALENT, 0 ms] (15) QDP (16) TransformationProof [EQUIVALENT, 0 ms] (17) QDP (18) TransformationProof [EQUIVALENT, 0 ms] (19) QDP (20) TransformationProof [EQUIVALENT, 0 ms] (21) QDP (22) MRRProof [EQUIVALENT, 8 ms] (23) QDP (24) PisEmptyProof [EQUIVALENT, 0 ms] (25) YES (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) MNOCProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) QDP (45) QReductionProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 0 ms] (48) QDP (49) DependencyGraphProof [EQUIVALENT, 0 ms] (50) QDP (51) TransformationProof [EQUIVALENT, 0 ms] (52) QDP (53) DependencyGraphProof [EQUIVALENT, 0 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 0 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) QDP (59) TransformationProof [EQUIVALENT, 0 ms] (60) QDP (61) DependencyGraphProof [EQUIVALENT, 0 ms] (62) QDP (63) TransformationProof [EQUIVALENT, 0 ms] (64) QDP (65) DependencyGraphProof [EQUIVALENT, 0 ms] (66) QDP (67) UsableRulesProof [EQUIVALENT, 0 ms] (68) QDP (69) TransformationProof [EQUIVALENT, 0 ms] (70) QDP (71) DependencyGraphProof [EQUIVALENT, 0 ms] (72) TRUE ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(f(x, y), z) -> c 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(c) 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(c) 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(c) 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(c) 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(c)),TOP(up(f(f(x0, x1), x2))) -> TOP(up(c))) (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(c)) 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(c) 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 2 SCCs with 14 less nodes. ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) 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))) The TRS R consists of the following rules: down(f(f(x, y), z)) -> up(c) 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. ---------------------------------------- (14) 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. ---------------------------------------- (15) 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))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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(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)))) ---------------------------------------- (17) 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))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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)))) ---------------------------------------- (19) 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))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) 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))))) ---------------------------------------- (21) 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)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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)))) 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 ---------------------------------------- (23) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (25) YES ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 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(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(c) 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. ---------------------------------------- (27) 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. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 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(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. ---------------------------------------- (29) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 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(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. ---------------------------------------- (31) 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)))) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: 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(block(fresh_constant), down(a))) TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 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. ---------------------------------------- (33) 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))))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: 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(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 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. ---------------------------------------- (35) 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)))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: 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(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (37) 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))))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: 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(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (39) 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))))) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (41) 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)))) ---------------------------------------- (42) 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(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (43) 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. ---------------------------------------- (44) 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(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (45) 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) ---------------------------------------- (46) 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(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (47) 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)))) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (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: TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 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. ---------------------------------------- (51) 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))))) ---------------------------------------- (52) 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(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. ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (54) 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. ---------------------------------------- (55) 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)))) ---------------------------------------- (56) 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. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (58) 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. ---------------------------------------- (59) 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))))) ---------------------------------------- (60) 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. ---------------------------------------- (61) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (62) 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. ---------------------------------------- (63) 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))))) ---------------------------------------- (64) 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. ---------------------------------------- (65) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (66) 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. ---------------------------------------- (67) 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. ---------------------------------------- (68) 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. ---------------------------------------- (69) 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)))) ---------------------------------------- (70) 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. ---------------------------------------- (71) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (72) TRUE