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