# Unambiguous recognizable two-dimensional languages

Marcella Anselmo; Dora Giammarresi; Maria Madonia; Antonio Restivo

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 2, page 277-293
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAnselmo, Marcella, et al. "Unambiguous recognizable two-dimensional languages." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 277-293. <http://eudml.org/doc/249682>.

@article{Anselmo2006,

abstract = {
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.
},

author = {Anselmo, Marcella, Giammarresi, Dora, Madonia, Maria, Restivo, Antonio},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Automata and formal languages; unambiguity;
determinism; two-dimensional languages.; automata and formal languages; determinism; two-dimensional languages},

language = {eng},

month = {7},

number = {2},

pages = {277-293},

publisher = {EDP Sciences},

title = {Unambiguous recognizable two-dimensional languages},

url = {http://eudml.org/doc/249682},

volume = {40},

year = {2006},

}

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

DA - 2006/7//

PB - EDP Sciences

VL - 40

IS - 2

SP - 277

EP - 293

AB -
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.

LA - eng

KW - Automata and formal languages; unambiguity;
determinism; two-dimensional languages.; automata and formal languages; determinism; two-dimensional languages

UR - http://eudml.org/doc/249682

ER -

## References

top- 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.
- J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985).
- 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 Bolyay42 (1985).
- 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).
- M. Blum and C. Hewitt, Automata on a two-dimensional tape, in IEEE Symposium on Switching and Automata Theory (1967) 155–160.
- C. Choffrut and B. Durak, Collage of two-dimensional words. Theoret. Comput. Sci.340 (2005) 364–380.
- M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets. Fundamenta InformaticaX (1987) 323–336.
- S. Crespi Reghizzi and M. Pradella, Tile rewriting grammars and picture languages. Theoret. Comput. Sci.340 (2005) 257–272.
- S. Eilenberg, Automata, Languages and Machines. Vol. A, Academic Press (1974).
- D. Giammarresi and A. Restivo, Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence6 (1992) 241–256.
- 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.
- 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.
- 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.
- K. Inoue and A. Nakamura, Some properties of two-dimensional on-line tessellation acceptors. Information Sciences13 (1977) 95–121.
- K. Inoue and A. Nakamura, Nonclosure properties of two-dimensional on-line tessellation acceptors and one-way parallel/sequential array acceptors. Trans. IECE Japan6 (1977) 475–476.
- 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).
- 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.
- 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).
- 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.
- I. Mäurer, Recognizable and Rational Picture Series, in Procs. Conf. on Algebraic Informatics, Thessaloniki (2005), Aristotte University of Thessaloniki.
- I. Mäurer, Weighted Picture Automata and Weighted Logics, in Procs. STACS 2006, Springer Belin. Lect. Notes Comput. Sci.3884 (2006) 313–324.
- 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.
- J. Sakarovitch, Eléments de théorie des automates. Vuibert, Paris (2003).
- W. Thomas, On Logics, Tilings, and Automata, in Proc. 18th ICALP, Springer-Verlag, Berlin. Lect. Notes Comput. Sci.510 (1991) 441–453.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.