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

Abstract

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

How to cite

top

Anselmo, 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
  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.  
  2. J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985).  
  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 Bolyay42 (1985).  
  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).  
  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.  
  7. M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets. Fundamenta InformaticaX (1987) 323–336.  
  8. S. Crespi Reghizzi and M. Pradella, Tile rewriting grammars and picture languages. Theoret. Comput. Sci.340 (2005) 257–272.  
  9. S. Eilenberg, Automata, Languages and Machines. Vol. A, Academic Press (1974).  
  10. D. Giammarresi and A. Restivo, Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence6 (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.  
  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.  
  14. K. Inoue and A. Nakamura, Some properties of two-dimensional on-line tessellation acceptors. Information Sciences13 (1977) 95–121.  
  15. 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.  
  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).  
  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.  
  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).  
  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.  
  21. I. Mäurer, Weighted Picture Automata and Weighted Logics, in Procs. STACS 2006, Springer Belin. Lect. Notes Comput. Sci.3884 (2006) 313–324.  
  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.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.