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.
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] , and, New Operations and Regular Expressions for two-dimensional languages over one-letter alphabet. Theoret. Comput. Sci. 340 (2005) 408-431. | Zbl
[2] and, Theory of Codes. Academic Press (1985). | MR | Zbl
[3] , and, 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] and, Recognizable picture series, in Special Issue on Weighted Automata. Journal of Automata, Languages and Combinatorics, Vol. 10, No. 2 (2005). | MR | Zbl
[5] and, Automata on a two-dimensional tape, in IEEE Symposium on Switching and Automata Theory (1967) 155-160.
[6] and, Collage of two-dimensional words. Theoret. Comput. Sci. 340 (2005) 364-380. | Zbl
[7] and, Unique decipherability for partially commutative alphabets. Fundamenta Informatica X (1987) 323-336. | Zbl
[8] and, Tile rewriting grammars and picture languages. Theoret. Comput. Sci. 340 (2005) 257-272. | Zbl
[9] , Automata, Languages and Machines. Vol. A, Academic Press (1974). | MR | Zbl
[10] and, Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence 6 (1992) 241-256.
[11] and, Two-dimensional languages, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin III (1997) 215-268.
[12] ,, and, Monadic second order logic over pictures and recognizability by tiling systems. Inform. Computat. 125 (1996) 32-45. | Zbl
[13] ,,, and, Communication Complexity Method for Measuring Nondeterminism in Finite Automata. Inform. Comput. 172 (2002) 202-217. | Zbl
[14] and, Some properties of two-dimensional on-line tessellation acceptors. Information Sciences 13 (1977) 95-121. | Zbl
[15] and, Nonclosure properties of two-dimensional on-line tessellation acceptors and one-way parallel/sequential array acceptors. Trans. IECE Japan 6 (1977) 475-476.
[16] and, 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] and, 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] , 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] and, The Monadic Quantifier Alternation Hierarchy over Graphs is Infinite, in IEEE Symposium on Logic in Computer Science, LICS. IEEE (1997) 236-244.
[20] , Recognizable and Rational Picture Series, in Procs. Conf. on Algebraic Informatics, Thessaloniki (2005), Aristotte University of Thessaloniki. | MR
[21] , Weighted Picture Automata and Weighted Logics, in Procs. STACS 2006, Springer Belin. Lect. Notes Comput. Sci. 3884 (2006) 313-324. | Zbl
[22] , and, Nondeterminism versus determinism of finite automata over directed acyclic graphs. Bulletin Belgian Math. Soc. 1 (1994) 285-298. | Zbl
[23] , Eléments de théorie des automates. Vuibert, Paris (2003).
[24] , On Logics, Tilings, and Automata, in Proc. 18th ICALP, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 510 (1991) 441-453. | Zbl
Cité par Sources :
