A Brief Excursion Inside the Class of Tiling Recognizable Two-Dimensional Languages

摘要

Tiling recognizable two-dimensional 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 this implies that it is intrinsically non-deterministic. As result, all subclasses corresponding to different notion of unambiguity and determinism define a hierarchy inside REC. Moreover we show that some definitions of unambiguity are equivalent to corresponding notions of determinism and therefore correspond decidable classes closed under complementation and linear parsing algorithms.