Context-Sensitive String Languages and Recognizable Picture Languages

AbstractThe theorem stating that the family of frontiers of recognizable tree languages is exactly the family of context-free languages (see J. Mezei and J. B. Wright, 1967,Inform. and Comput.11, 3–29), is a basic result in the theory of formal languages. In this article, we prove a similar result: the family of frontiers of recognizable picture languages is exactly the family of context-sensitive language