RAIRO - Theoretical Informatics and Applications

Research Article

Classes of two-dimensional languages and recognizability conditions

Marcella Anselmoa1 and Maria Madoniaa2

a1 Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84084 Fisciano (SA), Italy; anselmo@dia.unisa.it

a2 Dipartimento di Matematica e Informatica, Università di Catania, Viale Andrea Doria 6/a, 95125 Catania, Italy; madonia@dmi.unict.it


The paper deals with some classes of two-dimensional recognizable languages of “high complexity”, in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by Matz, introducing a new complexity function. We solve an open question proposed by Matz, showing that all the known necessary conditions for recognizability of a language and its complement are not sufficient. The proof relies on a family of languages defined by functions.

(Received February 27 2010)

(Accepted November 4 2010)

(Online publication February 28 2011)

Key Words:

  • Two-dimensional languages;
  • unambiguity;
  • complement

Mathematics Subject Classification:

  • 68Q45;
  • 68Q70