/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 Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 37 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) TransformationProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) TransformationProof [EQUIVALENT, 0 ms] (11) QDP (12) DependencyGraphProof [EQUIVALENT, 0 ms] (13) QDP (14) TransformationProof [EQUIVALENT, 0 ms] (15) QDP (16) DependencyGraphProof [EQUIVALENT, 0 ms] (17) QDP (18) TransformationProof [EQUIVALENT, 0 ms] (19) QDP (20) DependencyGraphProof [EQUIVALENT, 0 ms] (21) QDP (22) TransformationProof [EQUIVALENT, 0 ms] (23) QDP (24) DependencyGraphProof [EQUIVALENT, 0 ms] (25) QDP (26) TransformationProof [EQUIVALENT, 0 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) QDP (34) TransformationProof [EQUIVALENT, 0 ms] (35) QDP (36) DependencyGraphProof [EQUIVALENT, 0 ms] (37) QDP (38) TransformationProof [EQUIVALENT, 0 ms] (39) QDP (40) DependencyGraphProof [EQUIVALENT, 0 ms] (41) QDP (42) TransformationProof [EQUIVALENT, 0 ms] (43) QDP (44) DependencyGraphProof [EQUIVALENT, 0 ms] (45) QDP (46) TransformationProof [EQUIVALENT, 103 ms] (47) QDP (48) DependencyGraphProof [EQUIVALENT, 0 ms] (49) QDP (50) TransformationProof [EQUIVALENT, 14 ms] (51) QDP (52) DependencyGraphProof [EQUIVALENT, 0 ms] (53) QDP (54) QDPOrderProof [EQUIVALENT, 242 ms] (55) QDP (56) QDPOrderProof [EQUIVALENT, 154 ms] (57) QDP (58) QDPOrderProof [EQUIVALENT, 58 ms] (59) QDP (60) QDPOrderProof [EQUIVALENT, 3627 ms] (61) QDP (62) QDPOrderProof [EQUIVALENT, 3203 ms] (63) QDP (64) QDPOrderProof [EQUIVALENT, 2124 ms] (65) QDP (66) QDPOrderProof [EQUIVALENT, 3137 ms] (67) QDP (68) QDPOrderProof [EQUIVALENT, 167.0 s] (69) QDP (70) DependencyGraphProof [EQUIVALENT, 0 ms] (71) TRUE (72) QDP (73) QDPOrderProof [EQUIVALENT, 126 ms] (74) QDP (75) DependencyGraphProof [EQUIVALENT, 0 ms] (76) QDP (77) UsableRulesProof [EQUIVALENT, 0 ms] (78) QDP (79) QDPSizeChangeProof [EQUIVALENT, 0 ms] (80) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(0)) -> F(s(0)) G(x) -> H(x, x) S(x) -> H(x, 0) S(x) -> H(0, x) F(g(x)) -> G(g(f(x))) F(g(x)) -> G(f(x)) F(g(x)) -> F(x) G(s(x)) -> S(s(g(x))) G(s(x)) -> S(g(x)) G(s(x)) -> G(x) H(f(x), g(x)) -> F(s(x)) H(f(x), g(x)) -> S(x) S(s(s(0))) -> K(0) K(0) -> S(0) S(s(s(s(0)))) -> K(s(0)) K(s(0)) -> S(s(0)) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) H(k(x), g(x)) -> K(s(x)) H(k(x), g(x)) -> S(x) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(x)) -> G(g(f(x))) G(x) -> H(x, x) H(f(x), g(x)) -> F(s(x)) F(g(x)) -> G(f(x)) G(s(x)) -> S(s(g(x))) S(s(0)) -> F(s(0)) F(g(x)) -> F(x) S(s(s(s(0)))) -> K(s(0)) K(s(0)) -> S(s(0)) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) G(s(x)) -> S(g(x)) G(s(x)) -> G(x) H(f(x), g(x)) -> S(x) H(k(x), g(x)) -> K(s(x)) H(k(x), g(x)) -> S(x) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule S(s(0)) -> F(s(0)) at position [0] we obtained the following new rules [LPAR04]: (S(s(0)) -> F(h(0, 0)),S(s(0)) -> F(h(0, 0))) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(x)) -> G(g(f(x))) G(x) -> H(x, x) H(f(x), g(x)) -> F(s(x)) F(g(x)) -> G(f(x)) G(s(x)) -> S(s(g(x))) F(g(x)) -> F(x) S(s(s(s(0)))) -> K(s(0)) K(s(0)) -> S(s(0)) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) G(s(x)) -> S(g(x)) G(s(x)) -> G(x) H(f(x), g(x)) -> S(x) H(k(x), g(x)) -> K(s(x)) H(k(x), g(x)) -> S(x) S(s(0)) -> F(h(0, 0)) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) 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 2 SCCs with 6 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(0)) -> S(s(0)) S(s(s(s(0)))) -> K(s(0)) K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(0)) -> S(s(0)) at position [0] we obtained the following new rules [LPAR04]: (K(s(0)) -> S(h(0, 0)),K(s(0)) -> S(h(0, 0))) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(0)))) -> K(s(0)) K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(0)) -> S(h(0, 0)) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) S(s(s(s(0)))) -> K(s(0)) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule S(s(s(s(0)))) -> K(s(0)) at position [0] we obtained the following new rules [LPAR04]: (S(s(s(s(0)))) -> K(h(0, 0)),S(s(s(s(0)))) -> K(h(0, 0))) ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) S(s(s(s(0)))) -> K(h(0, 0)) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(s(s(s(s(s(s(0))))))))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(s(s(s(s(s(s(s(0))))))), 0)),K(s(s(0))) -> S(h(s(s(s(s(s(s(s(0))))))), 0))) (K(s(s(0))) -> S(h(0, s(s(s(s(s(s(s(0))))))))),K(s(s(0))) -> S(h(0, s(s(s(s(s(s(s(0)))))))))) (K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))),K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0)))) (K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))),K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0)))))))))) (K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))),K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0))))) (K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))),K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0)))))))))) (K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))),K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0)))))) (K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))),K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0)))))))))) (K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))),K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0))))))) (K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))),K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0)))))))))) (K(s(s(0))) -> S(s(s(s(s(k(s(0))))))),K(s(s(0))) -> S(s(s(s(s(k(s(0)))))))) (K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))),K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0)))))))) (K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))),K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0)))))))))) (K(s(s(0))) -> S(s(s(s(s(s(k(0))))))),K(s(s(0))) -> S(s(s(s(s(s(k(0)))))))) (K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))),K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0)))))))))) (K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))),K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0))))))))) (K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))),K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0)))))))))) (K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))),K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0)))))))))) ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(h(s(s(s(s(s(s(s(0))))))), 0)) K(s(s(0))) -> S(h(0, s(s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(s(s(s(s(s(0)))))))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(s(s(s(s(s(s(0)))))), 0)),K(s(s(0))) -> S(h(s(s(s(s(s(s(0)))))), 0))) (K(s(s(0))) -> S(h(0, s(s(s(s(s(s(0)))))))),K(s(s(0))) -> S(h(0, s(s(s(s(s(s(0))))))))) (K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))),K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0)))) (K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))),K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0))))))))) (K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))),K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0))))) (K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))),K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0))))))))) (K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))),K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0)))))) (K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))),K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0))))))))) (K(s(s(0))) -> S(s(s(s(k(s(0)))))),K(s(s(0))) -> S(s(s(s(k(s(0))))))) (K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))),K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0))))))) (K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))),K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0))))))))) (K(s(s(0))) -> S(s(s(s(s(k(0)))))),K(s(s(0))) -> S(s(s(s(s(k(0))))))) (K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))),K(s(s(0))) -> S(s(s(s(s(s(f(s(0))))))))) (K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))),K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0)))))))) (K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))),K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0))))))))) (K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))),K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0))))))))) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(h(s(s(s(s(s(s(0)))))), 0)) K(s(s(0))) -> S(h(0, s(s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(s(s(s(s(0))))))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(s(s(s(s(s(0))))), 0)),K(s(s(0))) -> S(h(s(s(s(s(s(0))))), 0))) (K(s(s(0))) -> S(h(0, s(s(s(s(s(0))))))),K(s(s(0))) -> S(h(0, s(s(s(s(s(0)))))))) (K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))),K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0)))) (K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))),K(s(s(0))) -> S(s(h(0, s(s(s(s(0)))))))) (K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))),K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0))))) (K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))),K(s(s(0))) -> S(s(s(h(0, s(s(s(0)))))))) (K(s(s(0))) -> S(s(s(k(s(0))))),K(s(s(0))) -> S(s(s(k(s(0)))))) (K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))),K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0)))))) (K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))),K(s(s(0))) -> S(s(s(s(h(0, s(s(0)))))))) (K(s(s(0))) -> S(s(s(s(k(0))))),K(s(s(0))) -> S(s(s(s(k(0)))))) (K(s(s(0))) -> S(s(s(s(s(f(s(0))))))),K(s(s(0))) -> S(s(s(s(s(f(s(0)))))))) (K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))),K(s(s(0))) -> S(s(s(s(s(h(s(0), 0))))))) (K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))),K(s(s(0))) -> S(s(s(s(s(h(0, s(0)))))))) (K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))),K(s(s(0))) -> S(s(s(s(s(s(h(0, 0)))))))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(0)))))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(h(s(s(s(s(s(0))))), 0)) K(s(s(0))) -> S(h(0, s(s(s(s(s(0))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(s(0)))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(s(s(s(0)))))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(s(s(s(s(0)))), 0)),K(s(s(0))) -> S(h(s(s(s(s(0)))), 0))) (K(s(s(0))) -> S(h(0, s(s(s(s(0)))))),K(s(s(0))) -> S(h(0, s(s(s(s(0))))))) (K(s(s(0))) -> S(s(h(s(s(s(0))), 0))),K(s(s(0))) -> S(s(h(s(s(s(0))), 0)))) (K(s(s(0))) -> S(s(h(0, s(s(s(0)))))),K(s(s(0))) -> S(s(h(0, s(s(s(0))))))) (K(s(s(0))) -> S(s(k(s(0)))),K(s(s(0))) -> S(s(k(s(0))))) (K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))),K(s(s(0))) -> S(s(s(h(s(s(0)), 0))))) (K(s(s(0))) -> S(s(s(h(0, s(s(0)))))),K(s(s(0))) -> S(s(s(h(0, s(s(0))))))) (K(s(s(0))) -> S(s(s(k(0)))),K(s(s(0))) -> S(s(s(k(0))))) (K(s(s(0))) -> S(s(s(s(f(s(0)))))),K(s(s(0))) -> S(s(s(s(f(s(0))))))) (K(s(s(0))) -> S(s(s(s(h(s(0), 0))))),K(s(s(0))) -> S(s(s(s(h(s(0), 0)))))) (K(s(s(0))) -> S(s(s(s(h(0, s(0)))))),K(s(s(0))) -> S(s(s(s(h(0, s(0))))))) (K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))),K(s(s(0))) -> S(s(s(s(s(h(0, 0))))))) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(0))))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(h(s(s(s(s(0)))), 0)) K(s(s(0))) -> S(h(0, s(s(s(s(0)))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(0))))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(s(s(0))))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(s(s(s(0))), 0)),K(s(s(0))) -> S(h(s(s(s(0))), 0))) (K(s(s(0))) -> S(h(0, s(s(s(0))))),K(s(s(0))) -> S(h(0, s(s(s(0)))))) (K(s(s(0))) -> S(k(s(0))),K(s(s(0))) -> S(k(s(0)))) (K(s(s(0))) -> S(s(h(s(s(0)), 0))),K(s(s(0))) -> S(s(h(s(s(0)), 0)))) (K(s(s(0))) -> S(s(h(0, s(s(0))))),K(s(s(0))) -> S(s(h(0, s(s(0)))))) (K(s(s(0))) -> S(s(k(0))),K(s(s(0))) -> S(s(k(0)))) (K(s(s(0))) -> S(s(s(f(s(0))))),K(s(s(0))) -> S(s(s(f(s(0)))))) (K(s(s(0))) -> S(s(s(h(s(0), 0)))),K(s(s(0))) -> S(s(s(h(s(0), 0))))) (K(s(s(0))) -> S(s(s(h(0, s(0))))),K(s(s(0))) -> S(s(s(h(0, s(0)))))) (K(s(s(0))) -> S(s(s(s(h(0, 0))))),K(s(s(0))) -> S(s(s(s(h(0, 0)))))) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(0)))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(h(s(s(s(0))), 0)) K(s(s(0))) -> S(h(0, s(s(s(0))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(0)))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(s(0)))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(s(s(0)), 0)),K(s(s(0))) -> S(h(s(s(0)), 0))) (K(s(s(0))) -> S(h(0, s(s(0)))),K(s(s(0))) -> S(h(0, s(s(0))))) (K(s(s(0))) -> S(k(0)),K(s(s(0))) -> S(k(0))) (K(s(s(0))) -> S(s(f(s(0)))),K(s(s(0))) -> S(s(f(s(0))))) (K(s(s(0))) -> S(s(h(s(0), 0))),K(s(s(0))) -> S(s(h(s(0), 0)))) (K(s(s(0))) -> S(s(h(0, s(0)))),K(s(s(0))) -> S(s(h(0, s(0))))) (K(s(s(0))) -> S(s(s(h(0, 0)))),K(s(s(0))) -> S(s(s(h(0, 0))))) ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(h(s(s(0)), 0)) K(s(s(0))) -> S(h(0, s(s(0)))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(0))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(s(0))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(f(s(0))),K(s(s(0))) -> S(f(s(0)))) (K(s(s(0))) -> S(h(s(0), 0)),K(s(s(0))) -> S(h(s(0), 0))) (K(s(s(0))) -> S(h(0, s(0))),K(s(s(0))) -> S(h(0, s(0)))) (K(s(s(0))) -> S(s(h(0, 0))),K(s(s(0))) -> S(s(h(0, 0)))) ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) K(s(s(0))) -> S(f(s(0))) K(s(s(0))) -> S(h(s(0), 0)) K(s(s(0))) -> S(h(0, s(0))) K(s(s(0))) -> S(s(h(0, 0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) K(s(s(0))) -> S(f(s(0))) K(s(s(0))) -> S(s(h(0, 0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(f(s(0))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(f(h(0, 0))),K(s(s(0))) -> S(f(h(0, 0)))) ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) K(s(s(0))) -> S(s(h(0, 0))) K(s(s(0))) -> S(f(h(0, 0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) K(s(s(0))) -> S(s(h(0, 0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule K(s(s(0))) -> S(s(h(0, 0))) at position [0] we obtained the following new rules [LPAR04]: (K(s(s(0))) -> S(h(h(0, 0), 0)),K(s(s(0))) -> S(h(h(0, 0), 0))) (K(s(s(0))) -> S(h(0, h(0, 0))),K(s(s(0))) -> S(h(0, h(0, 0)))) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) K(s(s(0))) -> S(h(h(0, 0), 0)) K(s(s(0))) -> S(h(0, h(0, 0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(s(0), 0))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(s(h(0, s(s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(f(s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, s(0))))))))) K(s(s(0))) -> S(s(s(s(s(s(s(s(h(0, 0))))))))) K(s(s(0))) -> S(s(h(0, s(s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(h(0, s(s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(f(s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, s(0)))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(0, 0)))))))) K(s(s(0))) -> S(s(h(0, s(s(s(s(0))))))) K(s(s(0))) -> S(s(s(h(0, s(s(s(0))))))) K(s(s(0))) -> S(s(s(s(h(0, s(s(0))))))) K(s(s(0))) -> S(s(s(s(s(f(s(0))))))) K(s(s(0))) -> S(s(s(s(s(h(0, s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(0, 0))))))) K(s(s(0))) -> S(s(h(0, s(s(s(0)))))) K(s(s(0))) -> S(s(s(h(0, s(s(0)))))) K(s(s(0))) -> S(s(s(s(f(s(0)))))) K(s(s(0))) -> S(s(s(s(h(0, s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(0, 0)))))) K(s(s(0))) -> S(s(h(0, s(s(0))))) K(s(s(0))) -> S(s(s(f(s(0))))) K(s(s(0))) -> S(s(s(h(0, s(0))))) K(s(s(0))) -> S(s(s(s(h(0, 0))))) K(s(s(0))) -> S(s(f(s(0)))) K(s(s(0))) -> S(s(h(0, s(0)))) K(s(s(0))) -> S(s(s(h(0, 0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(K(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< POL(0) = [[1], [0]] >>> <<< POL(S(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(k(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(f(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(g(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(k(0)) K(s(s(0))) -> S(s(h(s(0), 0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(s(h(s(s(s(s(s(s(0)))))), 0))) K(s(s(0))) -> S(s(s(h(s(s(s(s(s(0))))), 0)))) K(s(s(0))) -> S(s(s(s(h(s(s(s(s(0)))), 0))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(s(0))), 0)))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(s(0)), 0))))))) K(s(s(0))) -> S(s(s(s(s(s(s(h(s(0), 0)))))))) K(s(s(0))) -> S(s(h(s(s(s(s(s(0))))), 0))) K(s(s(0))) -> S(s(s(h(s(s(s(s(0)))), 0)))) K(s(s(0))) -> S(s(s(s(h(s(s(s(0))), 0))))) K(s(s(0))) -> S(s(s(s(s(h(s(s(0)), 0)))))) K(s(s(0))) -> S(s(s(s(s(s(h(s(0), 0))))))) K(s(s(0))) -> S(s(h(s(s(s(s(0)))), 0))) K(s(s(0))) -> S(s(s(h(s(s(s(0))), 0)))) K(s(s(0))) -> S(s(s(s(h(s(s(0)), 0))))) K(s(s(0))) -> S(s(s(s(s(h(s(0), 0)))))) K(s(s(0))) -> S(s(h(s(s(s(0))), 0))) K(s(s(0))) -> S(s(s(h(s(s(0)), 0)))) K(s(s(0))) -> S(s(s(s(h(s(0), 0))))) K(s(s(0))) -> S(s(h(s(s(0)), 0))) K(s(s(0))) -> S(s(s(h(s(0), 0)))) K(s(s(0))) -> S(s(h(s(0), 0))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(K(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [1]] >>> <<< POL(S(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(k(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(f(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(g(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(k(0))) K(s(s(0))) -> S(k(0)) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(k(0)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(S(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(s(x_1)) = [[1], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(K(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(k(x_1)) = [[1], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 0]] * x_2 >>> <<< POL(f(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(g(x_1)) = [[1], [0]] + [[0, 0], [1, 0]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(k(s(0))) K(s(s(0))) -> S(s(k(0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(k(s(0))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(S(x_1)) = [[0A]] + [[0A, -I, 0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A], [0A], [0A]] + [[-I, -I, -I], [-I, 0A, 0A], [0A, 0A, -I]] * x_1 >>> <<< POL(0) = [[1A], [0A], [0A]] >>> <<< POL(K(x_1)) = [[1A]] + [[-I, -I, -I]] * x_1 >>> <<< POL(k(x_1)) = [[0A], [1A], [0A]] + [[-I, -I, -I], [-I, -I, -I], [0A, 0A, -I]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0A], [-I], [-I]] + [[-I, -I, -I], [-I, 0A, 0A], [-I, 0A, -I]] * x_1 + [[-I, -I, -I], [-I, -I, 0A], [-I, 0A, -I]] * x_2 >>> <<< POL(f(x_1)) = [[0A], [-I], [-I]] + [[0A, -I, -I], [-I, -I, -I], [-I, -I, -I]] * x_1 >>> <<< POL(g(x_1)) = [[0A], [-I], [-I]] + [[0A, 0A, -I], [-I, 0A, 0A], [-I, 0A, 0A]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(k(0)))) K(s(s(0))) -> S(s(k(0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(s(s(s(k(s(0)))))) K(s(s(0))) -> S(s(s(s(s(k(0)))))) K(s(s(0))) -> S(s(k(s(0)))) K(s(s(0))) -> S(s(s(k(0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(S(x_1)) = [[0A]] + [[-I, 0A, -I]] * x_1 >>> <<< POL(s(x_1)) = [[0A], [0A], [0A]] + [[-I, 0A, 0A], [0A, -I, 0A], [-I, -I, 0A]] * x_1 >>> <<< POL(0) = [[0A], [1A], [0A]] >>> <<< POL(K(x_1)) = [[1A]] + [[-I, -I, -I]] * x_1 >>> <<< POL(k(x_1)) = [[0A], [0A], [0A]] + [[-I, 0A, -I], [0A, -I, 0A], [-I, -I, -I]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0A], [0A], [-I]] + [[-I, -I, 0A], [0A, -I, 0A], [-I, -I, 0A]] * x_1 + [[-I, -I, 0A], [0A, -I, -I], [-I, -I, 0A]] * x_2 >>> <<< POL(f(x_1)) = [[0A], [0A], [0A]] + [[-I, -I, 0A], [-I, -I, 0A], [-I, -I, 0A]] * x_1 >>> <<< POL(g(x_1)) = [[0A], [0A], [-I]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(k(0))))) K(s(s(0))) -> S(s(k(0))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(s(k(0))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(S(x_1)) = [[0A]] + [[-I, -I, 0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A], [0A], [0A]] + [[-I, 0A, -I], [0A, -I, 0A], [0A, -I, -I]] * x_1 >>> <<< POL(0) = [[0A], [-I], [1A]] >>> <<< POL(K(x_1)) = [[1A]] + [[-I, -I, -I]] * x_1 >>> <<< POL(k(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, -I], [0A, 0A, 0A], [0A, -I, 0A]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0A], [-I], [0A]] + [[-I, 0A, -I], [-I, -I, -I], [0A, -I, -I]] * x_1 + [[-I, 0A, -I], [0A, -I, -I], [-I, -I, -I]] * x_2 >>> <<< POL(f(x_1)) = [[-I], [0A], [-I]] + [[0A, 0A, -I], [0A, -I, 0A], [0A, -I, 0A]] * x_1 >>> <<< POL(g(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, -I]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(k(0))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. K(s(s(0))) -> S(s(s(k(s(0))))) K(s(s(0))) -> S(s(s(s(k(0))))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(S(x_1)) = [[0A]] + [[0A, -I, -I]] * x_1 >>> <<< POL(s(x_1)) = [[0A], [0A], [0A]] + [[-I, -I, 0A], [0A, -I, 0A], [-I, 0A, -I]] * x_1 >>> <<< POL(0) = [[1A], [-I], [-I]] >>> <<< POL(K(x_1)) = [[1A]] + [[-I, -I, -I]] * x_1 >>> <<< POL(k(x_1)) = [[0A], [0A], [0A]] + [[-I, -I, 0A], [0A, -I, 0A], [-I, 0A, 0A]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0A], [0A], [0A]] + [[-I, -I, 0A], [-I, -I, 0A], [-I, 0A, -I]] * x_1 + [[-I, -I, 0A], [-I, -I, 0A], [-I, 0A, -I]] * x_2 >>> <<< POL(f(x_1)) = [[0A], [0A], [-I]] + [[-I, -I, 0A], [0A, -I, 0A], [0A, 0A, 0A]] * x_1 >>> <<< POL(g(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. S(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> K(s(s(0))) K(s(s(0))) -> S(s(s(s(s(s(k(0))))))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^4, +, *, >=, >) : <<< POL(S(x_1)) = [[0]] + [[0, 2, 0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0], [0], [0]] + [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1], [1, 0, 0, 1]] * x_1 >>> <<< POL(0) = [[1], [0], [0], [0]] >>> <<< POL(K(x_1)) = [[3]] + [[0, 0, 0, 3]] * x_1 >>> <<< POL(k(x_1)) = [[0], [0], [0], [1]] + [[0, 0, 0, 0], [1, 0, 3, 1], [0, 2, 2, 2], [0, 0, 0, 0]] * x_1 >>> <<< POL(h(x_1, x_2)) = [[0], [0], [0], [0]] + [[0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 0, 1]] * x_1 + [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1], [0, 0, 0, 0]] * x_2 >>> <<< POL(f(x_1)) = [[0], [0], [0], [0]] + [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] * x_1 >>> <<< POL(g(x_1)) = [[0], [0], [0], [0]] + [[0, 0, 0, 0], [2, 2, 2, 3], [1, 2, 2, 2], [0, 0, 0, 1]] * x_1 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: K(s(s(0))) -> S(s(s(s(s(k(s(0))))))) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (71) TRUE ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: G(x) -> H(x, x) H(f(x), g(x)) -> F(s(x)) F(g(x)) -> G(g(f(x))) G(s(x)) -> G(x) F(g(x)) -> G(f(x)) F(g(x)) -> F(x) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. G(x) -> H(x, x) F(g(x)) -> G(g(f(x))) F(g(x)) -> G(f(x)) F(g(x)) -> F(x) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( F_1(x_1) ) = max{0, 2x_1 - 1} POL( G_1(x_1) ) = 2 POL( f_1(x_1) ) = 2x_1 POL( g_1(x_1) ) = x_1 + 2 POL( h_2(x_1, x_2) ) = max{0, -2} POL( s_1(x_1) ) = max{0, -2} POL( k_1(x_1) ) = max{0, -2} POL( 0 ) = 0 POL( H_2(x_1, x_2) ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f(g(x)) -> g(g(f(x))) g(x) -> h(x, x) h(f(x), g(x)) -> f(s(x)) h(k(x), g(x)) -> k(s(x)) k(s(0)) -> s(s(0)) s(s(0)) -> f(s(0)) s(s(s(s(0)))) -> k(s(0)) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) g(s(x)) -> s(s(g(x))) s(x) -> h(x, 0) s(x) -> h(0, x) s(s(s(0))) -> k(0) k(0) -> s(0) ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: H(f(x), g(x)) -> F(s(x)) G(s(x)) -> G(x) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: G(s(x)) -> G(x) The TRS R consists of the following rules: s(s(0)) -> f(s(0)) g(x) -> h(x, x) s(x) -> h(x, 0) s(x) -> h(0, x) f(g(x)) -> g(g(f(x))) g(s(x)) -> s(s(g(x))) h(f(x), g(x)) -> f(s(x)) s(s(s(0))) -> k(0) k(0) -> s(0) s(s(s(s(0)))) -> k(s(0)) k(s(0)) -> s(s(0)) s(s(s(s(s(s(s(s(s(s(s(0))))))))))) -> k(s(s(0))) k(s(s(0))) -> s(s(s(s(s(s(s(s(s(0))))))))) h(k(x), g(x)) -> k(s(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) 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. ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: G(s(x)) -> G(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *G(s(x)) -> G(x) The graph contains the following edges 1 > 1 ---------------------------------------- (80) YES