@TechReport{Prusa-TR-2012-08,
  IS = { zkontrolovano 15 Jan 2013 },
  UPDATE  = { 2012-05-25 },
author =      {Pr{\accent23 u}{\v s}a, Daniel and Mr{\'a}z, Franti{\v s}ek},
title =       {New Models for Recognition of Picture Languages: Sgraffito and Restarting Tiling Automata},
institution = {Center for Machine Perception, K13133 FEE
               Czech Technical University},
address =     {Prague, Czech Republic},
year =        {2012},
month =       {March},
type =        {Research Report},
number =      {CTU--CMP--2012--08},
issn =        {1213-2365},
pages =       {32},
figures =     {6},
authorship =  {50-50},
psurl       = {[Prusa-TR-2012-08.pdf]},
project =     {GACR P103/10/0783},
annote =      {We introduce two new models of two-dimensional
  computing devices called sgraffito automaton and restarting tiling
  automaton. The models fulfill two conditions. Firstly, they do not
  exceed the power of finite-state automata when working over
  one-dimensional inputs. And secondly, they allow a clear design of
  important computations. We study properties of the induced families
  of picture languages. We show that they include strictly REC and
  that restarting tiling automata are able to simulate sgraffito
  automata. An interesting family is settled by deterministic
  sgraffito automata. It can be seen as an alternative to DREC.},
keywords =    {two-dimensional languages, automata, family REC, 
  lower bounds on time complexity},
}