Unambiguous recognizable two-dimensional languages
Anselmo, Marcella ; Giammarresi, Dora ; Madonia, Maria ; Restivo, Antonio
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006), p. 277-293 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of UREC are presented. Finally we show that it is undecidable whether a given tiling system is unambiguous.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2006008
Classification:  68Q45,  68Q10 
@article{ITA_2006__40_2_277_0,
     author = {Anselmo, Marcella and Giammarresi, Dora and Madonia, Maria and Restivo, Antonio},
     title = {Unambiguous recognizable two-dimensional languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {40},
     year = {2006},
     pages = {277-293},
     doi = {10.1051/ita:2006008},
     mrnumber = {2252639},
     zbl = {1112.68085},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2006__40_2_277_0}
}

Anselmo, Marcella; Giammarresi, Dora; Madonia, Maria; Restivo, Antonio. Unambiguous recognizable two-dimensional languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) pp. 277-293. doi : 10.1051/ita:2006008. http://gdmltest.u-ga.fr/item/ITA_2006__40_2_277_0/

[1] M. Anselmo, D. Giammarresi and M. Madonia, New Operations and Regular Expressions for two-dimensional languages over one-letter alphabet. Theoret. Comput. Sci. 340 (2005) 408-431. | Zbl 1078.68072

[2] J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985). | MR 797069 | Zbl 0587.68066

[3] A. Bertoni, G. Mauri and N. Sabadini, Unambiguous regular trace languages, in Algebra, Combinatorics and Logic in Computer Science, edited by J. Demetrovics, G. Katona and A. Salomaa, North Holland. Math. Soc. Janos Bolyay 42 (1985). | MR 875858 | Zbl 0627.68060

[4] S. Bozapalidis and A. Grammatikopoulou, Recognizable picture series, in Special Issue on Weighted Automata. Journal of Automata, Languages and Combinatorics, Vol. 10, No. 2 (2005). | MR 2285327 | Zbl 1161.68514

[5] M. Blum and C. Hewitt, Automata on a two-dimensional tape, in IEEE Symposium on Switching and Automata Theory (1967) 155-160.

[6] C. Choffrut and B. Durak, Collage of two-dimensional words. Theoret. Comput. Sci. 340 (2005) 364-380. | Zbl 1078.68079

[7] M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets. Fundamenta Informatica X (1987) 323-336. | Zbl 0634.94014

[8] S. Crespi Reghizzi and M. Pradella, Tile rewriting grammars and picture languages. Theoret. Comput. Sci. 340 (2005) 257-272. | Zbl 1079.68047

[9] S. Eilenberg, Automata, Languages and Machines. Vol. A, Academic Press (1974). | MR 530382 | Zbl 0317.94045

[10] D. Giammarresi and A. Restivo, Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence 6 (1992) 241-256.

[11] D. Giammarresi and A. Restivo, Two-dimensional languages, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin III (1997) 215-268.

[12] D. Giammarresi, A. Restivo, S. Seibert and W. Thomas, Monadic second order logic over pictures and recognizability by tiling systems. Inform. Computat. 125 (1996) 32-45. | Zbl 0853.68131

[13] J. Hromkovic, J. Karumäki, H. Klauck, G. Schnitger and S. Seibert, Communication Complexity Method for Measuring Nondeterminism in Finite Automata. Inform. Comput. 172 (2002) 202-217. | Zbl 1009.68067

[14] K. Inoue and A. Nakamura, Some properties of two-dimensional on-line tessellation acceptors. Information Sciences 13 (1977) 95-121. | Zbl 0371.94067

[15] K. Inoue and A. Nakamura, Nonclosure properties of two-dimensional on-line tessellation acceptors and one-way parallel/sequential array acceptors. Trans. IECE Japan 6 (1977) 475-476.

[16] K. Inoue and I. Takanami, A Characterization of recognizable picture languages, in Proc. Second International Colloquium on Parallel Image Processing, edited by A. Nakamura et al. Lect. Notes Comput. Sci. 654 (1993). | MR 1230226

[17] J. Kari and C. Moore, Rectangles and squares recognized by two-dimensional automata, in Theory is Forever, edited by Karhumaki et al. Lect. Notes Comput. Sci. 3113 (2004) 134-144. | Zbl 1055.68071

[18] O. Matz, On piecewise testable, starfree, and recognizable picture languages, in Foundations of Software Science and Computation Structures, edited by M. Nivat, Springer-Verlag, Berlin 1378 (1998). | MR 1641340

[19] O. Matz and W. Thomas, The Monadic Quantifier Alternation Hierarchy over Graphs is Infinite, in IEEE Symposium on Logic in Computer Science, LICS. IEEE (1997) 236-244.

[20] I. Mäurer, Recognizable and Rational Picture Series, in Procs. Conf. on Algebraic Informatics, Thessaloniki (2005), Aristotte University of Thessaloniki. | MR 2186460

[21] I. Mäurer, Weighted Picture Automata and Weighted Logics, in Procs. STACS 2006, Springer Belin. Lect. Notes Comput. Sci. 3884 (2006) 313-324. | Zbl 1136.68421

[22] A. Potthoff, S. Seibert and W. Thomas, Nondeterminism versus determinism of finite automata over directed acyclic graphs. Bulletin Belgian Math. Soc. 1 (1994) 285-298. | Zbl 0803.68032

[23] J. Sakarovitch, Eléments de théorie des automates. Vuibert, Paris (2003).

[24] W. Thomas, On Logics, Tilings, and Automata, in Proc. 18th ICALP, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 510 (1991) 441-453. | Zbl 0769.68100