Splitting a Context-Sensitive Set

摘要

We prove that if A is an infinite, coinfinite context-sensitive set, there exists adeterministic context-sensitive set B such that each of the four sets Download : Download full-size image, Download : Download full-size image is infinite. This result points up a major difference between the inclusion lattices of the context-sensitive and recursively enumerable sets.