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

摘要

This 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. (c) 2007 Elsevier B.V. All rights reserved.