On splitting recursive sets

摘要

It is shown that for every infinite, coinfinite recursive set A there exists a set B which can be accepted in real time and log space such that B splits A (i.e., each of A ⋒ B, A ⋒ A, ⋒ B, A ⋒ B is infinite). This fact is generalized to other Blum measures. It is also shown that context-free languages can be split by regular sets. The analogy between the recursive versus the recursively enumerable sets and the deterministic versus the nondeterministic resource bounded sets is shown to fail when the respective inclusion lattices are considered.