(Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars

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 1967, pp. 155–160. IEEE Computer Society, Washington, DC (1967)

   Google Scholar 

2. Bremner, A.: Positively prodigious powers or how Dudeney done it? Math. Mag. 84(2), 120–125 (2011)

   Article  MATH  Google Scholar 

3. Drewes, F., Ewert, S., Klempien-Hinrichs, R., Kreowski, H.: Computing raster images from grid picture grammars. J. Automata, Lang. Comb. 8(3), 499–519 (2003)

   MathSciNet  MATH  Google Scholar 

4. Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer, New York (1997)

   Chapter  Google Scholar 

5. Hopcroft, J., Ullman, J.: Formal languages and their relation to automata. Addison-Wesley, Reading (1969)

   Google Scholar 

6. Ito, T., Sakamoto, M., Okabe, H., Furutani, H., Kono, M., Ikeda, S.: Marker versus inkdot over three-dimensional patterns. Artif. Life Robot. 13(1), 65–68 (2008)

   Article  Google Scholar 

7. Matiyasevich, Y.: Hilbert’s tenth problem: Diophantine equations in the twentieth century. In: Bolibruch, A., Osipov, Y., Sinai, Y. (eds.) Mathematical Events of the Twentieth Century, pp. 185–213. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

8. Matz, O.: Regular expressions and context-free grammars for picture languages. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 283–294. Springer, Heidelberg (1997)

   Chapter  Google Scholar 

9. Nakamura, A.: Three-dimensional connected pictures are not recognizable by finite-state acceptors. Inf. Sci. 66(3), 225–234 (1992)

   Article  MATH  Google Scholar 

10. Nakamura, A.: Two-dimensional connected pictures are not recognizable by finite-state acceptors. Inf. Sci. 69(1–2), 55–64 (1993)

    Article  MATH  Google Scholar 

11. Pighizzini, G., Shallit, J., Wang, M.: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. J. Comput. Syst. Sci. 65(2), 393–414 (2002)

    Article  MathSciNet  MATH  Google Scholar 

12. Pradella, M., Cherubini, A., Reghizzi, S.C.: A unifying approach to picture grammars. Inf. Comput. 209(9), 1246–1267 (2011)

    Article  Google Scholar 

13. Průša, D.: Two-dimensional Languages. Ph.D. thesis, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic (2004)

    Google Scholar 

14. Průša, D.: Non-recursive trade-offs between two-dimensional automata and grammars. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 352–363. Springer, Heidelberg (2014)

    Google Scholar 

15. Schlesinger, M.I.: Matematiceskie sredstva obrabotki izobrazenij (Mathematic tools for image processing). Naukova Dumka, Kiev (1989) (in Russian)

    Google Scholar 

16. Schlesinger, M.I., Hlaváč, V.: Ten Lectures on Statistical and Structural Pattern Recognition (Computational Imaging and Vision). 1st edn. Springer, Heidelberg, May 2012

    Google Scholar 

17. Siromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages. Comput. Graph. Image Proces. 1(3), 284–307 (1972)

    Article  MathSciNet  Google Scholar 

18. Siromoney, G., Siromoney, R., Krithivasan, K.: Picture languages with array rewriting rules. Inf. Control 22(5), 447–470 (1973)

    Article  MathSciNet  MATH  Google Scholar 

19. Uchida, Y., Ito, T., Sakamoto, M., Uchida, K., Ide, T., Katamune, R., Furutani, H., Kono, M., Yoshinaga, T.: Cooperating systems of four-dimensional finite automata. Artif. Life Robot. 16(4), 555–558 (2012)

    Article  Google Scholar 

Download references