Two-dimensional finite state recognizability D. Giammarresi, A. Restivo 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 lan­ gages de mots reconnaissables en terme de langages locaux et de projections. De telles notions peuvent être étendues de façon na­ turelle 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 recon­ naissables. Bien que REC ait plusieurs propriétés communes avec les langages de mots reconnaissables, on montre que, contraire­ ment 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 ma­ chines et une autre qui utilise le formalisme logique. The purpose of this paper is to investigate about a new notion of fi­ nite state recognizability for two-dimensional (picture) lan­ guages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local lan­ guages 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 rec­ ognizable. Although REC shares several properties of recogniz­ able 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 characteri­ zations of family REC by means of machine-based models and logic- based formalisms.