On the separability of sparse context-free languages and of bounded rational relations

AbstractThis paper proves two results. (1) Given two bounded context-free languages, it is recursively decidable whether or not there exists a regular language which includes the first and is disjoint with the second and (2) given two rational k-ary bounded relations it is recursively decidable whether or not there exists a recognizable relation which includes the first and is disjoint with the second