Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-14T20:06:48.936Z Has data issue: false hasContentIssue false
  • English
  • Français

Two-dimensional Sgraffito automata∗∗∗

Published online by Cambridge University Press:  06 November 2014

Daniel Průša,
František Mráz and
Friedrich Otto
Daniel Průša
Affiliation:
Czech Technical University, Faculty of Electrical Engineering, Karlovo náměstí 13, 12135 Prague 2, Czech Republic.. prusapa1@cmp.felk.cvut.cz
František Mráz
Affiliation:
Charles University at Prague, Faculty of Mathematics and Physics, Department of Computer Science, Malostranské nám. 25, 11800 Prague 1, Czech Republic. ; frantisek.mraz@mff.cuni.cz
Friedrich Otto
Affiliation:
Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany.; otto@theory.informatik.uni-kassel.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present a new model of a two-dimensional computing device called Sgraffitoautomaton. In general, the model is quite simple, which allows a clear designof computations. When restricted to one-dimensional inputs, that is, strings, theSgraffito automaton does not exceed the power of finite-state automata. On the other hand,for two-dimensional inputs, it yields a family of picture languages with good closureproperties that strictly includes the class REC  of recognizable picture languages. Thedeterministic Sgraffito automata define a class of picture languages that includes theclass of deterministic recognizable picture languages DREC, the class of picture languagesthat are accepted by four-way alternating automata, those that are accepted bydeterministic one-marker automata, and the sudoku-deterministically recognizable picturelanguages, but the membership problem for the accepted languages is still decidable inpolynomial time. In addition, the deterministic Sgraffito automata accept some unarypicture languages that are outside of the class REC.

Keywords

Two-dimensional languageSgraffito automatonbounded Turing machineREC

Information

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 5 , December 2014, pp. 505 - 539
Copyright
© EDP Sciences 2014

References

M. Anselmo, D. Giammarresi and M. Madonia, From determinism to non-determinism in recognizable two-dimensional languages, in Proc. of Developments in Language Theory, DLT 2007. Vol. 4588 of Lect. Notes Comput. Sci. Edited by T. Harju, J. Karhumäki and A. Lepistö. Heidelberg. Springer (2007) 36–47.
M. Blum and C. Hewitt, Automata on a 2-dimensional tape, in Proc. of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), FOCS ’67, Washington, DC, USA. IEEE Computer Society (1967) 155–160.
B. Borchert and K. Reinhardt, Deterministically and sudoku-deterministically recognizable picture languages, in Proc. of LATA 2007. Edited by R. Loos, S.Z. Fazekas and C. Martín-Vide. Report 35/07, Tarragona. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili (2007) 175–186.
S. Even and G. Even, Graph Algorithms. Computer Software Engineering Series. Cambridge University Press (2011).
Giammarresi, D. and Restivo, A., Recognizable picture languages. Int. J. Pattern Recogn. Artif. Intell. 6 (1992) 241–256. Google Scholar
D. Giammarresi and A. Restivo, Two-dimensional languages. Handbook of Formal Languages, vol. 3. Edited by G. Rozenberg and A. Salomaa. Springer, New York, NY, USA (1997) 215–267.
Giammarresi, D., Restivo, A., Seibert, S. and Thomas, W., Monadic second order logic over rectangular pictures and recognizability by tiling systems. Inf. Comput. 125 (1996) 32–45. Google Scholar
Hennie, F.C., One-tape, off-line Turing machine computations. Inf. Control 8 (1965) 553–578. Google Scholar
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA (1979).
P. Hsia and R.T. Yeh, Finite automata with markers, in Proc. of ICALP. Edited by M. Nivat. North-Holland, Amsterdam (1972) 443–451.
Inoue, K. and Nakamura, A., Some properties of two-dimensional on-line tessellation acceptors. Information Sci. 13 (1977) 95–121. Google Scholar
K. Inoue and I. Takanami, A characterization of recognizable picture languages, in Proc. of Parallel Image Analysis. Vol. 654 of Lect. Notes Comput. Sci. Edited by A. Nakamura, M. Nivat, A. Saoudi, P.S.P. Wang and K. Inoue. Springer, Heidelberg (1993) 133–143.
Inoue, A., Inoue, K., Ito, A., Wang, Y. and Okazaki, T., A note on one-pebble two-dimensional Turing machines. Information Sci. 162 (2004) 295–314. Google Scholar
P. Jančar, F. Mráz and M. Plátek, Characterization of context-free languages by erasing automata, in Proc. of MFCS 1992. Vol. 629 of Lect. Notes Comput. Sci. Edited by I.M. Havel and V. Koubek. Springer, Heidelberg (1992) 307–314.
P. Jiřička and J. Král, Deterministic forgetting planar automata are more powerful than non-deterministic finite-state planar automata. In Developments in Language Theory, Singapore. Edited by G. Rozenberg and W. Thomas. World Scientific (1999) 71–80.
J. Kari and C. Moore, New results on alternating and non-deterministic two-dimensional finite-state automata, in Proc. of STACS 2001. Vol. 2010 of Lect. Notes Comput. Sci. Edited by A. Ferreira and H. Reichel. Springer, Heidelberg (2001) 396–406.
Lindgren, K., Moore, C. and Nordahl, M., Complexity of two-dimensional patterns. J. Statist. Phys. 91 (1998) 909–951. Google Scholar
D. Prsůˇa, F. Mráz and F. Otto, Comparing two-dimensional one-marker automata to sgraffito automata, in Proc. of CIAA 2013. Vol. 7982 of Lect. Notes Comput. Sci. Edited by S. Konstantinidis. Springer, Heidelberg (2013) 268–279.
D. Prsůˇa, Weight-reducing Hennie machines and their descriptional complexity. In Proc. of LATA 2014. Vol. 8370 of Lect. Notes Comput. Sci. Edited by A.-H. Dediu, C. Martín-Vide, J.-L. Sierra-Rodríguez and B. Truthe. Springer, Heidelberg (2014) 553–564.
D. Prsůˇa and F. Mráz, Two-dimensional sgraffito automata, in Proc. of DLT 2012. Vol. 7410 of Lect. Notes Comput. Sci. Edited by H.C. Yen and O.H. Ibarra. Springer, Heidelberg (2012) 251–262.
D. Prsůˇa, F Mráz and F. Otto, New results on deterministic sgraffito automata, in Proc. of DLT 2013. Vol. 7907 of Lect. Notes Comput. Sci. Edited by M.P. Béal and O. Carton. Springer, Heidelberg (2013) 409–419.
A. Rosenfeld, Picture Languages – Formal Models of Picture Recognition. Academic Press, New York (1979).