7.30/2.60 YES 7.30/2.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.30/2.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.30/2.61 7.30/2.61 7.30/2.61 Outermost Termination of the given OTRS could be proven: 7.30/2.61 7.30/2.61 (0) OTRS 7.30/2.61 (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 7.30/2.61 (2) QTRS 7.30/2.61 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 7.30/2.61 (4) QDP 7.30/2.61 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (6) QDP 7.30/2.61 (7) UsableRulesProof [EQUIVALENT, 0 ms] 7.30/2.61 (8) QDP 7.30/2.61 (9) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (10) QDP 7.30/2.61 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (12) AND 7.30/2.61 (13) QDP 7.30/2.61 (14) UsableRulesProof [EQUIVALENT, 0 ms] 7.30/2.61 (15) QDP 7.30/2.61 (16) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (17) QDP 7.30/2.61 (18) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (19) QDP 7.30/2.61 (20) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (21) QDP 7.30/2.61 (22) MRRProof [EQUIVALENT, 5 ms] 7.30/2.61 (23) QDP 7.30/2.61 (24) PisEmptyProof [EQUIVALENT, 0 ms] 7.30/2.61 (25) YES 7.30/2.61 (26) QDP 7.30/2.61 (27) UsableRulesProof [EQUIVALENT, 0 ms] 7.30/2.61 (28) QDP 7.30/2.61 (29) MNOCProof [EQUIVALENT, 0 ms] 7.30/2.61 (30) QDP 7.30/2.61 (31) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (32) QDP 7.30/2.61 (33) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (34) QDP 7.30/2.61 (35) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (36) QDP 7.30/2.61 (37) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (38) QDP 7.30/2.61 (39) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (40) QDP 7.30/2.61 (41) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (42) QDP 7.30/2.61 (43) UsableRulesProof [EQUIVALENT, 0 ms] 7.30/2.61 (44) QDP 7.30/2.61 (45) QReductionProof [EQUIVALENT, 0 ms] 7.30/2.61 (46) QDP 7.30/2.61 (47) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (48) QDP 7.30/2.61 (49) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (50) QDP 7.30/2.61 (51) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (52) QDP 7.30/2.61 (53) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (54) QDP 7.30/2.61 (55) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (56) QDP 7.30/2.61 (57) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (58) QDP 7.30/2.61 (59) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (60) QDP 7.30/2.61 (61) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (62) QDP 7.30/2.61 (63) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (64) QDP 7.30/2.61 (65) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (66) QDP 7.30/2.61 (67) UsableRulesProof [EQUIVALENT, 0 ms] 7.30/2.61 (68) QDP 7.30/2.61 (69) TransformationProof [EQUIVALENT, 0 ms] 7.30/2.61 (70) QDP 7.30/2.61 (71) DependencyGraphProof [EQUIVALENT, 0 ms] 7.30/2.61 (72) TRUE 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (0) 7.30/2.61 Obligation: 7.30/2.61 Term rewrite system R: 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 f(f(x, y), z) -> c 7.30/2.61 f(x, f(y, z)) -> f(f(x, y), z) 7.30/2.61 a -> f(a, a) 7.30/2.61 7.30/2.61 7.30/2.61 7.30/2.61 Outermost Strategy. 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (1) Raffelsieper-Zantema-Transformation (SOUND) 7.30/2.61 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (2) 7.30/2.61 Obligation: 7.30/2.61 Q restricted rewrite system: 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 top(up(x)) -> top(down(x)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (3) DependencyPairsProof (EQUIVALENT) 7.30/2.61 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (4) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(x)) -> TOP(down(x)) 7.30/2.61 TOP(up(x)) -> DOWN(x) 7.30/2.61 DOWN(f(c, c)) -> F_FLAT(down(c), block(c)) 7.30/2.61 DOWN(f(c, c)) -> DOWN(c) 7.30/2.61 DOWN(f(c, c)) -> F_FLAT(block(c), down(c)) 7.30/2.61 DOWN(f(a, c)) -> F_FLAT(down(a), block(c)) 7.30/2.61 DOWN(f(a, c)) -> DOWN(a) 7.30/2.61 DOWN(f(a, c)) -> F_FLAT(block(a), down(c)) 7.30/2.61 DOWN(f(a, c)) -> DOWN(c) 7.30/2.61 DOWN(f(fresh_constant, c)) -> F_FLAT(down(fresh_constant), block(c)) 7.30/2.61 DOWN(f(fresh_constant, c)) -> DOWN(fresh_constant) 7.30/2.61 DOWN(f(fresh_constant, c)) -> F_FLAT(block(fresh_constant), down(c)) 7.30/2.61 DOWN(f(fresh_constant, c)) -> DOWN(c) 7.30/2.61 DOWN(f(c, a)) -> F_FLAT(down(c), block(a)) 7.30/2.61 DOWN(f(c, a)) -> DOWN(c) 7.30/2.61 DOWN(f(c, a)) -> F_FLAT(block(c), down(a)) 7.30/2.61 DOWN(f(c, a)) -> DOWN(a) 7.30/2.61 DOWN(f(a, a)) -> F_FLAT(down(a), block(a)) 7.30/2.61 DOWN(f(a, a)) -> DOWN(a) 7.30/2.61 DOWN(f(a, a)) -> F_FLAT(block(a), down(a)) 7.30/2.61 DOWN(f(fresh_constant, a)) -> F_FLAT(down(fresh_constant), block(a)) 7.30/2.61 DOWN(f(fresh_constant, a)) -> DOWN(fresh_constant) 7.30/2.61 DOWN(f(fresh_constant, a)) -> F_FLAT(block(fresh_constant), down(a)) 7.30/2.61 DOWN(f(fresh_constant, a)) -> DOWN(a) 7.30/2.61 DOWN(f(c, fresh_constant)) -> F_FLAT(down(c), block(fresh_constant)) 7.30/2.61 DOWN(f(c, fresh_constant)) -> DOWN(c) 7.30/2.61 DOWN(f(c, fresh_constant)) -> F_FLAT(block(c), down(fresh_constant)) 7.30/2.61 DOWN(f(c, fresh_constant)) -> DOWN(fresh_constant) 7.30/2.61 DOWN(f(a, fresh_constant)) -> F_FLAT(down(a), block(fresh_constant)) 7.30/2.61 DOWN(f(a, fresh_constant)) -> DOWN(a) 7.30/2.61 DOWN(f(a, fresh_constant)) -> F_FLAT(block(a), down(fresh_constant)) 7.30/2.61 DOWN(f(a, fresh_constant)) -> DOWN(fresh_constant) 7.30/2.61 DOWN(f(fresh_constant, fresh_constant)) -> F_FLAT(down(fresh_constant), block(fresh_constant)) 7.30/2.61 DOWN(f(fresh_constant, fresh_constant)) -> DOWN(fresh_constant) 7.30/2.61 DOWN(f(fresh_constant, fresh_constant)) -> F_FLAT(block(fresh_constant), down(fresh_constant)) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 top(up(x)) -> top(down(x)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (5) DependencyGraphProof (EQUIVALENT) 7.30/2.61 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 34 less nodes. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (6) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(x)) -> TOP(down(x)) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 top(up(x)) -> top(down(x)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (7) UsableRulesProof (EQUIVALENT) 7.30/2.61 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. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (8) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(x)) -> TOP(down(x)) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (9) TransformationProof (EQUIVALENT) 7.30/2.61 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 7.30/2.61 7.30/2.61 (TOP(up(f(f(x0, x1), x2))) -> TOP(up(c)),TOP(up(f(f(x0, x1), x2))) -> TOP(up(c))) 7.30/2.61 (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)))) 7.30/2.61 (TOP(up(a)) -> TOP(up(f(a, a))),TOP(up(a)) -> TOP(up(f(a, a)))) 7.30/2.61 (TOP(up(f(c, c))) -> TOP(f_flat(down(c), block(c))),TOP(up(f(c, c))) -> TOP(f_flat(down(c), block(c)))) 7.30/2.61 (TOP(up(f(c, c))) -> TOP(f_flat(block(c), down(c))),TOP(up(f(c, c))) -> TOP(f_flat(block(c), down(c)))) 7.30/2.61 (TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))),TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c)))) 7.30/2.61 (TOP(up(f(a, c))) -> TOP(f_flat(block(a), down(c))),TOP(up(f(a, c))) -> TOP(f_flat(block(a), down(c)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (TOP(up(f(c, a))) -> TOP(f_flat(down(c), block(a))),TOP(up(f(c, a))) -> TOP(f_flat(down(c), block(a)))) 7.30/2.61 (TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))),TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a)))) 7.30/2.61 (TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))),TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a)))) 7.30/2.61 (TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))),TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 (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)))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (10) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(f(x0, x1), x2))) -> TOP(up(c)) 7.30/2.61 TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) 7.30/2.61 TOP(up(a)) -> TOP(up(f(a, a))) 7.30/2.61 TOP(up(f(c, c))) -> TOP(f_flat(down(c), block(c))) 7.30/2.61 TOP(up(f(c, c))) -> TOP(f_flat(block(c), down(c))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(block(a), down(c))) 7.30/2.61 TOP(up(f(fresh_constant, c))) -> TOP(f_flat(down(fresh_constant), block(c))) 7.30/2.61 TOP(up(f(fresh_constant, c))) -> TOP(f_flat(block(fresh_constant), down(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(down(c), block(a))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(down(fresh_constant), block(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(c, fresh_constant))) -> TOP(f_flat(down(c), block(fresh_constant))) 7.30/2.61 TOP(up(f(c, fresh_constant))) -> TOP(f_flat(block(c), down(fresh_constant))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(block(a), down(fresh_constant))) 7.30/2.61 TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(down(fresh_constant), block(fresh_constant))) 7.30/2.61 TOP(up(f(fresh_constant, fresh_constant))) -> TOP(f_flat(block(fresh_constant), down(fresh_constant))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (11) DependencyGraphProof (EQUIVALENT) 7.30/2.61 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 14 less nodes. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (12) 7.30/2.61 Complex Obligation (AND) 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (13) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (14) UsableRulesProof (EQUIVALENT) 7.30/2.61 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. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (15) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(x0, f(x1, x2)))) -> TOP(up(f(f(x0, x1), x2))) 7.30/2.61 7.30/2.61 R is empty. 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (16) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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)))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (17) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(f(z0, z1), f(x1, x2)))) -> TOP(up(f(f(f(z0, z1), x1), x2))) 7.30/2.61 7.30/2.61 R is empty. 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (18) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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)))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (19) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(f(f(z0, z1), z2), f(x2, x3)))) -> TOP(up(f(f(f(f(z0, z1), z2), x2), x3))) 7.30/2.61 7.30/2.61 R is empty. 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (20) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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))))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (21) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 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)))) 7.30/2.61 7.30/2.61 R is empty. 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (22) MRRProof (EQUIVALENT) 7.30/2.61 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. 7.30/2.61 7.30/2.61 Strictly oriented dependency pairs: 7.30/2.61 7.30/2.61 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)))) 7.30/2.61 7.30/2.61 7.30/2.61 Used ordering: Polynomial interpretation [POLO]: 7.30/2.61 7.30/2.61 POL(TOP(x_1)) = 2*x_1 7.30/2.61 POL(f(x_1, x_2)) = 2 + x_1 + 2*x_2 7.30/2.61 POL(up(x_1)) = 2*x_1 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (23) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 P is empty. 7.30/2.61 R is empty. 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (24) PisEmptyProof (EQUIVALENT) 7.30/2.61 The TRS P is empty. Hence, there is no (P,Q,R) chain. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (25) 7.30/2.61 YES 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (26) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(f(f(x, y), z)) -> up(c) 7.30/2.61 down(f(x, f(y, z))) -> up(f(f(x, y), z)) 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 down(f(c, c)) -> f_flat(down(c), block(c)) 7.30/2.61 down(f(c, c)) -> f_flat(block(c), down(c)) 7.30/2.61 down(f(a, c)) -> f_flat(down(a), block(c)) 7.30/2.61 down(f(a, c)) -> f_flat(block(a), down(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(down(fresh_constant), block(c)) 7.30/2.61 down(f(fresh_constant, c)) -> f_flat(block(fresh_constant), down(c)) 7.30/2.61 down(f(c, a)) -> f_flat(down(c), block(a)) 7.30/2.61 down(f(c, a)) -> f_flat(block(c), down(a)) 7.30/2.61 down(f(a, a)) -> f_flat(down(a), block(a)) 7.30/2.61 down(f(a, a)) -> f_flat(block(a), down(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(down(fresh_constant), block(a)) 7.30/2.61 down(f(fresh_constant, a)) -> f_flat(block(fresh_constant), down(a)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(down(c), block(fresh_constant)) 7.30/2.61 down(f(c, fresh_constant)) -> f_flat(block(c), down(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(down(a), block(fresh_constant)) 7.30/2.61 down(f(a, fresh_constant)) -> f_flat(block(a), down(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(down(fresh_constant), block(fresh_constant)) 7.30/2.61 down(f(fresh_constant, fresh_constant)) -> f_flat(block(fresh_constant), down(fresh_constant)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (27) UsableRulesProof (EQUIVALENT) 7.30/2.61 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. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (28) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 Q is empty. 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (29) MNOCProof (EQUIVALENT) 7.30/2.61 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (30) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(down(a), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 The set Q consists of the following terms: 7.30/2.61 7.30/2.61 down(a) 7.30/2.61 f_flat(up(x0), block(x1)) 7.30/2.61 f_flat(block(x0), up(x1)) 7.30/2.61 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (31) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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)))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (32) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), down(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 The set Q consists of the following terms: 7.30/2.61 7.30/2.61 down(a) 7.30/2.61 f_flat(up(x0), block(x1)) 7.30/2.61 f_flat(block(x0), up(x1)) 7.30/2.61 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (33) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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))))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (34) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(down(a), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 The set Q consists of the following terms: 7.30/2.61 7.30/2.61 down(a) 7.30/2.61 f_flat(up(x0), block(x1)) 7.30/2.61 f_flat(block(x0), up(x1)) 7.30/2.61 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (35) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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)))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (36) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), down(a))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 The set Q consists of the following terms: 7.30/2.61 7.30/2.61 down(a) 7.30/2.61 f_flat(up(x0), block(x1)) 7.30/2.61 f_flat(block(x0), up(x1)) 7.30/2.61 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (37) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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))))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (38) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), down(a))) 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 The set Q consists of the following terms: 7.30/2.61 7.30/2.61 down(a) 7.30/2.61 f_flat(up(x0), block(x1)) 7.30/2.61 f_flat(block(x0), up(x1)) 7.30/2.61 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (39) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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))))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (40) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(down(a), block(fresh_constant))) 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.61 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.61 7.30/2.61 The TRS R consists of the following rules: 7.30/2.61 7.30/2.61 down(a) -> up(f(a, a)) 7.30/2.61 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.61 7.30/2.61 The set Q consists of the following terms: 7.30/2.61 7.30/2.61 down(a) 7.30/2.61 f_flat(up(x0), block(x1)) 7.30/2.61 f_flat(block(x0), up(x1)) 7.30/2.61 7.30/2.61 We have to consider all minimal (P,Q,R)-chains. 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (41) TransformationProof (EQUIVALENT) 7.30/2.61 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]: 7.30/2.61 7.30/2.61 (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)))) 7.30/2.61 7.30/2.61 7.30/2.61 ---------------------------------------- 7.30/2.61 7.30/2.61 (42) 7.30/2.61 Obligation: 7.30/2.61 Q DP problem: 7.30/2.61 The TRS P consists of the following rules: 7.30/2.61 7.30/2.61 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.61 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.61 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 down(a) -> up(f(a, a)) 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 down(a) 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (43) UsableRulesProof (EQUIVALENT) 7.30/2.62 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. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (44) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.62 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 down(a) 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (45) QReductionProof (EQUIVALENT) 7.30/2.62 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.30/2.62 7.30/2.62 down(a) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (46) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, c))) -> TOP(f_flat(up(f(a, a)), block(c))) 7.30/2.62 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (47) TransformationProof (EQUIVALENT) 7.30/2.62 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]: 7.30/2.62 7.30/2.62 (TOP(up(f(a, c))) -> TOP(up(f(f(a, a), c))),TOP(up(f(a, c))) -> TOP(up(f(f(a, a), c)))) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (48) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 TOP(up(f(a, c))) -> TOP(up(f(f(a, a), c))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (49) DependencyGraphProof (EQUIVALENT) 7.30/2.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (50) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(c, a))) -> TOP(f_flat(block(c), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (51) TransformationProof (EQUIVALENT) 7.30/2.62 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]: 7.30/2.62 7.30/2.62 (TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))),TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a))))) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (52) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 TOP(up(f(c, a))) -> TOP(up(f(c, f(a, a)))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (53) DependencyGraphProof (EQUIVALENT) 7.30/2.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (54) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(up(f(a, a)), block(a))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (55) TransformationProof (EQUIVALENT) 7.30/2.62 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]: 7.30/2.62 7.30/2.62 (TOP(up(f(a, a))) -> TOP(up(f(f(a, a), a))),TOP(up(f(a, a))) -> TOP(up(f(f(a, a), a)))) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (56) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(up(f(f(a, a), a))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (57) DependencyGraphProof (EQUIVALENT) 7.30/2.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (58) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, a))) -> TOP(f_flat(block(a), up(f(a, a)))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (59) TransformationProof (EQUIVALENT) 7.30/2.62 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]: 7.30/2.62 7.30/2.62 (TOP(up(f(a, a))) -> TOP(up(f(a, f(a, a)))),TOP(up(f(a, a))) -> TOP(up(f(a, f(a, a))))) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (60) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 TOP(up(f(a, a))) -> TOP(up(f(a, f(a, a)))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (61) DependencyGraphProof (EQUIVALENT) 7.30/2.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (62) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(f_flat(block(fresh_constant), up(f(a, a)))) 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (63) TransformationProof (EQUIVALENT) 7.30/2.62 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]: 7.30/2.62 7.30/2.62 (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))))) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (64) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 TOP(up(f(fresh_constant, a))) -> TOP(up(f(fresh_constant, f(a, a)))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (65) DependencyGraphProof (EQUIVALENT) 7.30/2.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (66) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (67) UsableRulesProof (EQUIVALENT) 7.30/2.62 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. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (68) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(f_flat(up(f(a, a)), block(fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (69) TransformationProof (EQUIVALENT) 7.30/2.62 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]: 7.30/2.62 7.30/2.62 (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)))) 7.30/2.62 7.30/2.62 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (70) 7.30/2.62 Obligation: 7.30/2.62 Q DP problem: 7.30/2.62 The TRS P consists of the following rules: 7.30/2.62 7.30/2.62 TOP(up(f(a, fresh_constant))) -> TOP(up(f(f(a, a), fresh_constant))) 7.30/2.62 7.30/2.62 The TRS R consists of the following rules: 7.30/2.62 7.30/2.62 f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2)) 7.30/2.62 7.30/2.62 The set Q consists of the following terms: 7.30/2.62 7.30/2.62 f_flat(up(x0), block(x1)) 7.30/2.62 f_flat(block(x0), up(x1)) 7.30/2.62 7.30/2.62 We have to consider all minimal (P,Q,R)-chains. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (71) DependencyGraphProof (EQUIVALENT) 7.30/2.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 7.30/2.62 ---------------------------------------- 7.30/2.62 7.30/2.62 (72) 7.30/2.62 TRUE 7.51/2.67 EOF