Two-Dimensional Limited Context Restarting Automata

• Autorzy: Krtek L. , Mráz F.

Identyfikatory

DOI

10.3233/FI-2016-1437

• Języki publikacji: EN

Abstrakty

EN

Motivated by possible machine learning of picture languages, we introduce a new twodimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited context restarting automata.

Słowa kluczowe

EN

machine learning; deterministic finite automata; robots; computational complexity; formal languages; np-hard problems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 3/4
• Strony: 309--340
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Krtek L.

• Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám, 25, 118 00 Prague 1, Czech Republic

autor

Mráz F.

• Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám, 25, 118 00 Prague 1, Czech Republic

Bibliografia

• [1] Blum M, Hewitt C. Automata on a 2-Dimensional Tape. In: Proceedings of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967). FOCS ’67. Washington, DC, USA: IEEE Computer Society; 1967. p. 155–160.
• [2] Inoue K, Takanami I. A Survey of Two-Dimensional Automata Theory. Information Sciences. 1991; 55(1):99–121.
• [3] Giammarresi D, Restivo A. Recognizable Picture Languages. International Journal of Pattern Recognition and Artificial Intelligence. 1992;6(2–3):32–45.
• [4] Průša D, Mráz F. Two-Dimensional Sgraffito Automata. In: Yen HC, Ibarra OH, editors. Developments in Language Theory. vol. 7410 of Lecture Notes in Computer Science. Berlin: Springer; 2012. p. 251–262.
• [5] Průša D, Mráz F, Otto F. Two-Dimensional Sgraffito Automata. RAIRO-Theoretical Informatics and Applications. 2014;48(5):505–539. Available from: http://www.rairo-ita.org/action/article_S098837541400023X. doi:10.1051/ita/2014023.
• [6] Inoue K, Nakamura A. Some Properties of Two-Dimensional On-Line Tessellation Acceptors. Information Sciences. 1977;13(2):95–121. Available from: http://dx.doi.org/10.1016/0020-0255(77)90023-8.
• [7] Anselmo M, Giammarresi D, Madonia M. Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages. In: Holub J, Žd’árek J, editors. Implementation and Application of Automata. vol. 4783 of Lecture Notes in Computer Science. Berlin: Springer; 2007. p. 290–302. Available from: http://dx.doi.org/10.1007/978-3-540-76336-9_27. doi:10.1007/978-3-540-76336-9_27.
• [8] Anselmo M, Giammarresi D, Madonia M. A Computational Model for Tiling Recognizable Two-Dimensional Languages. Theoretical Computer Science. 2009;410(37):3520–3529. doi:10.1016/j.tcs.2009.03.016.
• [9] Lonati V, Pradella M. Picture Recognizability with Automata Based on Wang Tiles. In: van Leeuwen et al J, editor. SOFSEM 2010. vol. 5901 of Lecture Notes in Computer Science. Berlin: Springer; 2010. p. 576–587.
• [10] Lonati V, Pradella M. Deterministic recognizability of picture languages with Wang automata. Discrete Mathematics & Theoretical Computer Science. 2010;12(4):73–94. Available from: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1471.
• [11] Giammarresi D, Restivo A. Two-Dimensional Languages. In: Salomaa A, Rozenberg G, editors. Handbook of Formal Languages. vol. 3 – Beyond Words. Berlin: Springer; 1997. p. 215–267.
• [12] Průša D, Mráz F. Restarting Tiling Automata. In: Moreira N, Reis R, editors. Implementation and Application of Automata. vol. 7381 of Lecture Notes in Computer Science. Berlin: Springer; 2012. p. 289–300. Available from: http://dx.doi.org/10.1007/978-3-642-31606-7_25. doi:10.1007/978-3-642-31606-7_25.
• [13] Průša D, Mráz F. Restarting Tiling Automata. International Journal of Foundations of Computer Science. 2013;24(6):863–878. doi:10.1142/S0129054113400236.
• [14] Otto F, Černo P, Mráz F. On the Classes of Languages Accepted by Limited Context Restarting Automata. RAIRO-Theoretical Informatics and Applications. 2014;48:61–84. Available from: http://www.rairo-ita.org/article_S0988375414000010. doi:10.1051/ita/2014001.
• [15] Mráz F, Otto F. Ordered Restarting Automata for Picture Languages. In: Geffert V, Preneel B, Rovan B, Štuller J, Tjoa A, editors. SOFSEM 2014: Theory and Practice of Computer Science. vol. 8327 of Lecture Notes in Computer Science. Berlin: Springer; 2014. p. 431–442. doi:10.1007/978-3-319-04298-5_38.
• [16] Otto F, Mráz F. Extended Two-Way Ordered Restarting Automata for Picture Languages. In: Dediu AH, Martín-Vide C, Sierra-Rodríguez JL, Truthe B, editors. Language and Automata Theory and Applications. vol. 8370 of Lecture Notes in Computer Science. Berlin: Springer; 2014. p. 541–552. doi:10.1007/978-3-319-04921-2_44.
• [17] Otto F, Mráz F. Deterministic Ordered Restarting Automata for Picture Languages. Acta Informatica. 2015;p. 1–31. published online, DOI 10.1007/s00236-015-0230-5. Available from: http://dx.doi.org/10.1007/s00236-015-0230-5. doi:10.1007/s00236-015-0230-5.
• [18] Borchert B, Reinhardt K. Deterministically and Sudoku-Deterministically Recognizable Picture Languages. In: Loos R, Fazekas SZ, Martín-Vide C, editors. LATA 2007, Preproc. Report 35/07. Tarragona: Research Group on Mathematical Linguistics, Universitat Rovira i Virgili; 2007. p. 175–186.
• [19] Průša D, Mráz F, Otto F. New Results on Deterministic Sgraffito Automata. In: Béal MP, Carton O, editors. Developments in Language Theory. vol. 7907 of Lecture Notes in Computer Science. Berlin: Springer; 2013. p. 409–419. doi:10.1007/978-3-642-38771-5_36.
• [20] Giammarresi D. Exploring Inside Tiling Recognizable Picture Languages to Find Deterministic Subclasses. International Journal of Foundations of Computer Science. 2011;22(7):1519–1532.
• [21] Jančar P, Mráz F, Plátek M, Vogel J. Restarting Automata. In: Reichel H, editor. Fundamentals of Computation Theory. vol. 965 of Lecture Notes in Computer Science. Berlin: Springer; 1995. p. 283–292.
• [22] Otto F. Restarting Automata. In: Ésik Z, Martín-Vide C, Mitrana V, editors. Recent Advances in Formal Languages and Applications. vol. 25 of Studies in Computational Intelligence. Berlin: Springer; 2006. p. 269–303.
• [23] Latteux M, Simplot D. Recognizable Picture Languages and Domino Tiling. Theoretical Computer Science. 1997;178(1–2):275–283. Available from: http://dx.doi.org/10.1016/S0304-3975(96)00283-6. doi:10.1016/S0304-3975(96)00283-6.
• [24] Krtek L. Learning Picture Languages Using Restarting Automata [Master Thesis]. Faculty of Mathematics and Physics, Charles University. Prague; 2014. accessible oline at https://is.cuni.cz/webapps/zzp/detail/138686.
• [25] Lindgren K, Moore C, Nordahl M. Complexity of Two-Dimensional Patterns. Journal of Statistical Physics. 1998;91(5-6):909–951.
• [26] Russell SJ, Norvig P. Artificial Intelligence – A Modern Approach (3rd internat. edition). Pearson Education; 2010. Available from: http://vig.pearsoned.com/store/product/1,1207,store-12521_isbn-0136042597,00.html.
• [27] Pradella M, Crespi Reghizzi S. A SAT-Based Parser and Completer for Pictures Specified by Tiling. Pattern Recognition. 2008;41(2):555–566. Available from: http://www.sciencedirect.com/science/article/pii/S0031320307003226. doi:http://dx.doi.org/10.1016/j.patcog.2007.06.018.
• [28] Lonati V, Pradella M. Towards More Expressive 2D Deterministic Automata. In: Bouchou-Markhoff B, Caron P, Champarnaud JM, Maurel D, editors. Implementation and Application of Automata. vol. 6807 of Lecture Notes in Computer Science. Berlin: Springer; 2011. p. 225–237. Available from: http://dx.doi.org/10.1007/978-3-642-22256-6_21.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).