"Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata"@en . . . "http://link.springer.com.ezproxy.is.cuni.cz/chapter/10.1007/978-3-642-39274-0_24" . . "0302-9743" . "2013-07-16+02:00"^^ . "Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata"@en . . "66118" . . "We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion." . "RIV/00216208:11320/13:10145554!RIV14-GA0-11320___" . "P(GAP103/10/0783), P(GAP202/10/1333)" . . . "Berlin" . "We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion."@en . "RIV/00216208:11320/13:10145554" . "Mr\u00E1z, Franti\u0161ek" . "Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata" . . "Otto, Friedrich" . . . "two-dimensional one-marker automaton; sgraffito automaton; recognizable picture languages; picture languages"@en . "12"^^ . . "Springer-Verlag" . "Halifax, Kanada" . . "978-3-642-39273-3" . . . "Pr\u016F\u0161a, Daniel" . . "11320" . . . "3"^^ . . . "Implementation and Application of Automata" . "1"^^ . "[6AF49D3F1118]" . "Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata" . "10.1007/978-3-642-39274-0_24" .