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