Two-dimensional finite state recognizability

D. Giammarresi, A. Restivo

IBP-Litp 1994/24: Rapport de Recherche Litp / Litp research reports
27 pages - Décembre/December 1994 - Document en anglais.

Titre / Title: Two-dimensional finite state recognizability

Résumé : Le but de cet article est d'étudier une nouvelle notion de reconnaissabilité par états finis pour des langages bi-dimensionnels. Le point de départ est la caractérisation des langages de mots reconnaissables en terme de langages locaux et de projections. De telles notions peuvent être étendues de façon naturelle au cas bi-dimensionnel. Nous introduisons tout d'abord la notion de langage bi-dimensionnel local, puis nous définissons les langages bi-dimensionnels reconnaissables comme projections des langages locaux. On note REC cette famille de langages et on étudie ses propriétés combinatoires. On prouve en particulier des propriétés de fermetures relatives à différentes opérations. On déduit de ceci que des familles naturelles de langages bi-dimensionnels (comme les langages finis, les langages réguliers, ou les langages localement testables) sont reconnaissables. On donne de plus des conditions nécessaires de reconnaissabilité qui permettent de montrer que certains langages ne sont pas reconnaissables. Bien que REC ait plusieurs propriétés communes avec les langages de mots reconnaissables, on montre que, contrairement au cas des mots, REC n'est pas fermé par complémentation et que le problème du vide est indécidable. Enfin nous donnons une caractérisation de la famille REC qui utilise des modèles de machines et une autre qui utilise le formalisme logique.

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.

Publications internes Litp 1994 / Litp research reports 1994