Unambiguous recognizable two-dimensional languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 277-293.

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.

DOI : 10.1051/ita:2006008
Classification : 68Q45, 68Q10
Mots clés : automata and formal languages, unambiguity, determinism, two-dimensional languages
@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},
     pages = {277--293},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ita:2006008},
     mrnumber = {2252639},
     zbl = {1112.68085},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2006008/}
}
TY  - JOUR
AU  - Anselmo, Marcella
AU  - Giammarresi, Dora
AU  - Madonia, Maria
AU  - Restivo, Antonio
TI  - Unambiguous recognizable two-dimensional languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 277
EP  - 293
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2006008/
DO  - 10.1051/ita:2006008
LA  - en
ID  - ITA_2006__40_2_277_0
ER  - 
%0 Journal Article
%A Anselmo, Marcella
%A Giammarresi, Dora
%A Madonia, Maria
%A Restivo, Antonio
%T Unambiguous recognizable two-dimensional languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 277-293
%V 40
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2006008/
%R 10.1051/ita:2006008
%G en
%F 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) no. 2, pp. 277-293. doi : 10.1051/ita:2006008. http://archive.numdam.org/articles/10.1051/ita:2006008/

[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

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

[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 | Zbl

[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 | Zbl

[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

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

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

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

[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

[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

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

[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

[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

[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

[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

[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

[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

[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

Cité par Sources :