2010/12/03 by Dora Giammarresi, Giammarresi, Dora
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Physical sciences #cs.CC #nlin.CG #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1012.0672
Journées Automates Cellulaires 2010, Turku : Finland (2010)
arxiv created 2010/12/03 · openalex publication_date 2010/12/03 · arxiv updated 2010/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 the membership problem is NP-complete. This implies that this family REC is intrinsically non-deterministic. 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 line-unambiguous tiling recognizable languages and prove that it corresponds or somehow naturally introduces different notions of determin- ism that define a hierarchy inside REC.