@inproceedings{PrusaDLT2012, IS = { zkontrolovano 14 Jan 2013 }, UPDATE = { 2012-10-01 }, author = {Pr{\r u}{\v s}a, Daniel and Mr{\' a}z, Franti{\v s}ek}, title = {Two-dimensional sgraffito automata}, booktitle = {Proceedings of the 16th international conference on Developments in Language Theory}, series = {Lecture Notes in Computer Science}, volume = {7410}, editor = {Yen, Hsu-Chun and Ibarra, Oscar H.}, year = {2012}, month = {August}, day = {14-17}, isbn = {978-3-642-31652-4}, venue = {Taipei, Taiwan}, pages = {251--262}, numpages = {12}, url = {http://dx.doi.org/10.1007/978-3-642-31653-1_23}, doi = {10.1007/978-3-642-31653-1_23}, acmid = {2364335}, publisher = {Springer-Verlag}, address = {Heidelberg, Germany}, book_pages = {476}, annote = {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. }, authorship = {50-50}, project = {GACR P103/10/0783}, keywords = {REC, bounded Turing machine, sgraffito automaton, two-dimensional languages}, }