Abstract
We present a new model of a two-dimensional computing device called sgraffito automaton and demonstrate its significance. In general, the model is simple, allows a clear design of important computations and defines families exhibiting good properties. It does not exceed the power of finite-state automata when working over one-dimensional inputs. On the other hand, it induces a family of picture languages that strictly includes REC and the deterministic variant recognizes languages in DREC as well as those accepted by four-way automata.
The authors were supported by the Grant Agency of the Czech Republic: the first author under the project P103/10/0783 and the second author under the projects P103/10/0783 and P202/10/1333.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Anselmo, M., Giammarresi, D., Madonia, M.: From Determinism to Non-determinism in Recognizable Two-Dimensional Languages. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 36–47. Springer, Heidelberg (2007)
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)
Giammarresi, D., Restivo, A.: Recognizable picture languages. International Journal of Pattern Recognition and Artificial Intelligence 6(2-3), 32–45 (1992)
Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer-Verlag New York, Inc., New York (1997)
Hennie, F.: One-tape, off-line Turing machine computations. Information and Control 8(6), 553–578 (1965)
Hopcroft, J., Ullman, J.: Formal languages and their relation to automata. Addison-Wesley (1969)
Inoue, K., Nakamura, A.: Some properties of two-dimensional on-line tessellation acceptors. Information Sciences 13, 95–121 (1977)
Jiřička, P., Král, J.: Deterministic forgetting planar automata are more powerful than non-deterministic finite-state planar automata. In: Rozenberg, G., Thomas, W. (eds.) Developments in Language Theory, pp. 71–80. World Scientific (1999)
Kari, J., Moore, C.: New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 396–406. Springer, Heidelberg (2001)
Lindgren, K., Moore, C., Nordahl, M.: Complexity of two-dimensional patterns. Journal of Statistical Physics 91(5-6), 909–951 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Průša, D., Mráz, F. (2012). Two-Dimensional Sgraffito Automata. In: Yen, HC., Ibarra, O.H. (eds) Developments in Language Theory. DLT 2012. Lecture Notes in Computer Science, vol 7410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31653-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-31653-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31652-4
Online ISBN: 978-3-642-31653-1
eBook Packages: Computer ScienceComputer Science (R0)