TWO-DIMENSIONAL FINITE STATE RECOGNIZABILITY

Article type: Research Article

Authors: Giammarresi, Dora | Restivo, Antonio

Affiliations: Dipartimento di Matematica e Applicazioni, Università di Palermo, via Archirafi, 34 - 90123 Palermo, Italy

Abstract: The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with respect to different kinds of operations. From this, we derive that some natural families of two-dimensional languages (finite languages, regular languages, locally testable languages) are recognizable. Further we give some necessary conditions for recognizability which provides tools to show that certain languages are not recognizable. Although REC shares several properties of recognizable string languages, however, differently from the case of words, we prove here that REC is not closed under complementation and that the emptyness problem is undecidable for this family of languages. Finally, we report some characterizations of family REC by means of machine-based models and logic-based formalisms.

DOI: 10.3233/FI-1996-253411

Journal: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 399-422, 1996