Tilingrecognizable twodimensional languages: from nondeterminism
to determinism through unambiguity
Dora Giammarresi
Dipartimento di Matematica
Università di Roma Tor Vergata, Italy
Abstract.
Tiling recognizable twodimensional languages, also known as REC, generalize
recognizable string languages to two dimensions and share with
them several theoretical properties. Nevertheless REC is not closed
under complementation and the membership problem is NPcomplete. This
implies that
this family REC is intrinsically nondeterministic. The natural and
immediate definition of unambiguity corresponds to a family UREC of
languages that is strictly contained in REC. On the other hand this
definition of unambiguity leads to an undecidability result and
therefore it cannot correspond to any deterministic notion. We
introduce the notion of lineunambiguous tiling recognizable
languages and prove that it corresponds, or somehow naturally
introduces, different notions of determinism that define a
hierarchy inside REC.

