A Common Framework to Recognize Two-dimensional Languages

• Autorzy: Anselmo Marcella , Giammarresi Dora , Madonia Maria

Identyfikatory

DOI

10.3233/FI-2020-1869

• Języki publikacji: EN

Abstrakty

EN

We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages.

Słowa kluczowe

EN

finite state machine; image processing; machine theory; transducers; two-dimensional model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 1--17
• Opis fizyczny: Bibliogr. 25 poz., rys., tab.

Twórcy

autor

Anselmo Marcella

• Dip. di Informatica, Università di Salerno, V. G. Paolo II, 132, I-84084 Fisciano (SA), Italy

autor

Giammarresi Dora

• Dip. di Matematica, Università Roma "Tor Vergata", Via della Ricerca Scientifica, 00133 Roma, Italy

autor

Madonia Maria

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

Bibliografia

• [1] Blum M, Hewitt C. Automata on a 2-Dimensional Tape. In: SWAT (FOCS). 1967 pp. 155-160. doi:10.1109/FOCS.1967.6.
• [2] Giammarresi D, Restivo A. Recognizable picture languages. Int. Journal Pattern Recognition and Artificial Intelligence, 1992. 6(2-3):241-256. doi:10.1142/S021800149200014X.
• [3] Giammarresi D, Restivo A. Two-dimensional languages. In: Handbook of Formal Languages. Springer Verlag, G.Rozenberg, Eds, Vol. III, 1997 pp. 215-268. doi:10.1007/978-3-642-59126-6_4.
• [4] Eilenberg S. Automata, languages, and machines. A. Pure and applied mathematics. Academic Press, 1974. ISBN: 0122340019.
• [5] De Prophetis L, Varricchio S. Recognizability of Rectangular Pictures by Wang Systems. Journal of Automata, Languages and Combinatorics, 1997. 2(4):269-288.
• [6] Giammarresi D, Restivo A, Seibert S, Thomas W. Monadic Second-Order Logic Over Rectangular Pictures and Recognizability by Tiling Systems. Inf. Comput., 1996. 125(1):32-45. doi:10.1006/inco.1996.0018.
• [7] Latteux M, Simplot D. Recognizable Picture Languages and Domino Tiling. Theor. Comput. Sci., 1997. 178(1-2):275-283. doi:10.1016/S0304-3975(96)00283-6.
• [8] Inoue K, Nakamura A. Some properties of two-dimensional on-line tessellation acceptors. Inf. Sci., 1977. 13(2):95-121. doi:10.1016/0020-0255(77)90023-8.
• [9] Anselmo M, Giammarresi D, Madonia M. Deterministic and unambiguous families within recognizable two-dimensional languages. Fund. Inform, 2010. 98(2-3):143-166. doi:10.3233/FI-2010-221.
• [10] Lonati V, Pradella M. Deterministic recognizability of picture languages with Wang automata. Discrete Mathematics & Theoretical Computer Science, 2010. 12(4):73-94. URL https://hal.inria.fr/hal-00990448.
• [11] Anselmo M, Giammarresi D, Madonia M. A computational model for tiling recognizable two-dimensional languages. Theor. Comput. Sci., 2009. 410(37):3520-3529. doi:10.1016/j.tcs.2009.03.016.
• [12] Průša D, Mráz F. Restarting Tiling Automata. Int. J. Found. Comput. Sci., 2013. 24(6):863-878. doi:10.1142/S0129054113400236.
• [13] Otto F. Restarting Automata for Picture Languages: A Survey on Recent Developments. In: Implementation and Application of Automata - 19th International Conference, CIAA 2014, Giessen, Germany, July 30 - August 2, 2014. Proceedings. 2014 pp. 16-41. doi:10.1007/978-3-319-08846-4_2.
• [14] Průša D, Mráz F, Otto F. Two-dimensional Sgraffito automata. RAIRO - Theor. Inf. and Applic., 2014. 48(5):505-539. doi:10.1051/ita/2014023.
• [15] Bonizzoni P, Ferretti C, Sagaya Mary AR, Mauri G. Picture Languages Generated by Assembling Tiles. Fundam. Inform., 2011. 110(1-4):77-93. doi:10.3233/FI-2011-529.
• [16] Matz O. On Piecewise Testable, Starfree, and Recognizable Picture Languages. In: Nivat M (ed.), Procs. FoSSaCS’98. LNCS 1378, Springer, 1998 pp. 203-210. doi:10.1007/BFb0053551.
• [17] Anselmo M, Giammarresi D, Madonia M. Two-Dimensional Rational Automata: A Bridge Unifying One and Two-Dimensional Language Theory. In: van Emde Boas P, Groen FCA, Italiano G, Nawrocki J, Sack H (eds.), Procs. SOFSEM 2013. LNCS 7741, Springer, 2013 pp. 133-145. doi:10.1007/978-3-642-35843-2_13.
• [18] Dolzhenko E, Jonoska N. On Complexity of Two Dimensional Languages Generated by Transducers. In: Ibarra OH, Ravikumar B (eds.), Procs. CIAA2008. LNCS 5148, Springer, 2008 pp. 181-190. doi:10.1007/978-3-540-70844-5_19.
• [19] Carayol A, Meyer A. Context-Sensitive Languages, Rational Graphs and Determinism. Logical Methods in Computer Science, 2006. 2(2). doi:10.2168/LMCS-2(2:6)2006.
• [20] CrespiReghizzi S, Giammarresi D, Lonati V. Two dimensional models. In: J. E. Pin (ed), Automata from mathematics to application. European Mathematical Society, to appear.
• [21] Anselmo M, Madonia M. Deterministic and unambiguous two-dimensional languages over one-letter alphabet. Theoretical Computer Science, 2009. 410(16):1477-1485. doi:10.1016/j.tcs.2008.12.009.
• [22] Berstel J. Transductions and context-free languages, volume 38 of Teubner Studienbücher : Informatik. Teubner, 1979. ISBN- 10:3519023407, 13:978-3519023401.
• [23] Harju T, Karhumäki J. Finite transducers and rational transduction. In: J. E. Pin (ed), Automata from mathematics to application. European Mathematical Society, to appear.
• [24] Sakarovitch J. Elements of Automata Theory. Cambridge University Press, 2009. ISBN: 0521844258 9780521844253.
• [25] Medvedev Y. On the class of events representable in a finite automaton. In: Sequential machines – Selected papers (translated from Russian), pp. 215-227. Addison-Wesley, NY, USA, E.F. Moore, ed., 1964.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).