Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages

• Autorzy: Anselmo M. , Giammarresi D. , Madonia M.
• Języki publikacji: EN

Abstrakty

EN

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties.

Słowa kluczowe

EN

automata and formal languages; unambiguity; determinism; tiling systems; two dimensional languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 2/3
• Strony: 143--166
• Opis fizyczny: Bibliogr. 29 poz., tab.

Twórcy

autor

Anselmo M.

autor

Giammarresi D.

autor

Madonia M.

• Dip. Matematica e Informatica, Universit`a di Catania, Viale Andrea Doria 6/a, 95125 Catania, Italy,

Bibliografia

• [1] M. Anselmo, D. Giammarresi, M. Madonia. From determinism to non-determinism in recognizable twodimensional languages. In Procs. DLT 07, T. Harju, J. Karhumaki and A. Lepisto (Eds.), LNCS 4588, Springer-Verlag, Berlin 2007.
• [2] M. Anselmo, D. Giammarresi, M. Madonia. Tiling automaton: a Computational Model for Recognizable Two-dimensional Languages. In Procs. CIAA 07, J. Holub and J. Zdarek (Eds.), LNCS 4783, Springer- Verlag, Berlin 2007.
• [3] M. Anselmo, D. Giammarresi, M. Madonia. A Computational Model for Tiling Recognizable Twodimensional Languages. Theoretical Computer Science 410 (2009) 3520 - 3529.
• [4] M. Anselmo, D. Giammarresi, M. Madonia, A. Restivo. Unambiguous Recognizable Two-dimensional Languages. RAIRO: Theoretical Informatics and Applications, Vol. 40, 2, 227-294, EDP Sciences 2006.
• [5] M. Anselmo, N. Jonoska,M.Madonia. Framed VersusUnframed Two-dimensional Languages. InM. Nielsen et al. (Eds.) Procs. SOFSEM 09, LNCS 5404, 79-92. Springer-Verlag Berlin Heidelberg 2009.
• [6] M. Anselmo,M. Madonia. Deterministic two-dimensional languages over one-letter alphabet. In S. Bozapalidis and G. Rahonis (Eds.) Procs. CAI 07, LNCS 4728, 147-159. Springer-Verlag Berlin Heidelberg 2007.
• [7] M. Anselmo, M. Madonia. Deterministic and unambiguous two-dimensional languages over one-letter alphabet. Theoretical Computer Science 410 (2009) 1477 - 1485.
• [8] M. Anselmo,M.Madonia, A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-dimensional Languages, in S. Bozapalidis and G. Rahonis (Eds.): CAI 2009, LNCS 5725, pp. 147-159, Springer-Verlag, Berlin Heidelberg 2009.
• [9] A. Bertoni,M. Goldwurm, V. Lonati. The complexity of unary tiling-recognizable picture languages. Fundamenta Informaticae vol. 90 (2), 2009, 231-249.
• [10] M. Blum, C. Hewitt. Automata on a two-dimensional tape. IEEE Symposium on Switching and Automata Theory, 155-160, 1967.
• [11] B. Borchert, K. Reinhardt. Deterministically and Sudoku-DeterministicallyRecognizable Picture Languages. In Proc. LATA 07, Tarragona (Spain) March 29 - April 4, 2007.
• [12] A. Carayol, A. Meyer. Context-Sensitive Languages, Rational Graphs and Determinism. Logical Methods in Computer Science, vol 2(2), 1-24, 2006.
• [13] A. Cherubini, M. Pradella, Picture Languages: from Wang tiles to 2D grammars, in S. Bozapalidis and G. Rahonis (Eds.): CAI 2009, LNCS 5725, pp. 13-46, Springer-Verlag, Berlin Heidelberg 2009.
• [14] S. Eilenberg. Automata, Languages and Machines. Vol. A, Academic Press, 1974.
• [15] D. Giammarresi, A. Restivo. Recognizable picture languages. Int. Journal Pattern Recognition and Artificial Intelligence. Vol. 6, No. 2&3, 241-256, 1992.
• [16] D. Giammarresi, A. Restivo. Two-dimensional languages. Handbook of Formal Languages, G.Rozenberg, et al. Eds, Vol. III, 215-268. Springer Verlag, 1997.
• [17] D. Giammarresi, A. Restivo. Matrix-based complexity functions and recognizable picture languages. In Logic and Automata: History and Perspectives, E. Grader, J.Flum, T. Wilke. Eds., 315-337. Texts in Logic and Games 2. : Amsterdam University Press, 2007.
• [18] D. Giammarresi, A. Restivo. Ambiguity and complementation in recognizable two-dimensional languages. In Procs. Intern. Conf. on Theoret. Compu. Sci., G. Ausiello, J. Karhumäki, G. Mauri, L. Ong eds. (Boston: Springer) IFIP vol. 273, 5-20, 2008.
• [19] D. Giammarresi, A. Restivo, S. Seibert,W. Thomas. Monadic second order logic over pictures and recognizability by tiling systems. Information and Computation, Vol 125, 1, 32-45, 1996.
• [20] K. Inoue, A. Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sciences, Vol. 13, 95-121, 1977.
• [21] K. Inoue, A. Nakamura. Nonclosure properties of two-dimensional on-line tessellation acceptors and oneway parallel/sequential array acceptors. Transaction of IECE of Japan, Vol. 6, 475-476, 1977.
• [22] K. Inoue, I. Takanami. A characterization of recognizable picture languages. In Proc. Second International Colloquium on Parallel Image Processing, A. Nakamura et al. (Eds.), LNCS 654, Springer-Verlag, Berlin 1993.
• [23] K. Lindgren, C. Moore,M. Nordahl. Complexity of two-dimensional patterns. Journal of Statistical Physics, 91 (5-6), 909-951, 1998.
• [24] V. Lonati,M. Pradella. Snake-Deterministic Tiling Systems. In Proc.MFCS 2009, 34st International Symposium on Mathematical Foundations of Computer Science, R. Krlovic, D. Niwinski (Eds.). LNCS, Vol. 5734, 549-560, Berlin 2009 .
• [25] O. Matz. On piecewise testable, starfree, and recognizable picture languages. In Foundations of Software Science and Computation Structures, M. Nivat Ed., vol. 1378, Springer-Verlag, Berlin, 1998.
• [26] A. Potthoff, S. Seibert, W. Thomas. Nondeterminism versus determinism of finite automata over directed acyclic graphs. Bull. Belgian Math. Soc. 1, 285-298, 1994.
• [27] M. Pradella, S. Crespi Reghizzi. A SAT-based parser and completer for pictures specified by tiling. Pattern Recognition, 41, 555-566, 2008.
• [28] K. Reinhardt. On some recognizable picture-languages. In Proc. 23thMFCS, LNCS 1450, 760-770. Springer-Verlag, 1998.
• [29] W. Thomas. Automata Theory on Trees and PartialOrders. InM. Bidoit andM. Dauchet, editors, Proceedings of the 7th International Joint Conference on Theory and Practice of Software Development, TAPSOFT '97, volume 1214 of Lecture Notes in Computer Science, 20-38. Springer, 1997