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