@InProceedings{Prusa-DCFS2014, IS = { zkontrolovano 03 Jan 2015 }, UPDATE = { 2014-12-16 }, author = {Pr{\r u}{\v s}a, Daniel}, affiliation = {13133}, title = {Non-recursive Trade-offs between Two-Dimensional Automata and Grammars}, booktitle = {DCFS 2014: Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems}, year = {2014}, isbn = {978-3-319-09703-9}, volume = {8614}, series = {Lecture Notes in Computer Science}, editor = {J{\" u}rgensen, Helmut and Karhum{\" a}ki, Juhani and Okhotin, Alexander}, doi = {10.1007/978-3-319-09704-6_31}, url = {http://dx.doi.org/10.1007/978-3-319-09704-6_31}, publisher = {Springer}, address = {Berlin, Germany}, annote = {We study succinctness of descriptional systems for picture languages. Basic models of two-dimensional finite automata and generalizations of context-free grammars are considered. It is shown t hat non-recursive trade-offs between the systems are very common. The results are based on the ability of th e systems to simulate Turing machines.}, keywords = {picture languages, four-way automata, two-dimensional context-free grammars, des criptional complexity}, month = {August}, day = {5-8}, venue = {Turku, Finland}, pages = {352--363}, book_pages = {363}, project = {GACR P103/10/0783}, }