UPDATE  = { 2010-02-18 },
  author =	{Daniel Pr{\r u}{\v s}a},
  title =	{Two-dimensional Languages},
  school = 	{Faculty of Mathematics and Physics, Charles University},
  address =	{Prague, Czech Republic},
  year =	{2005},
  month =	{July},
  day =         {03},
  type =	{PhD Thesis},
  pages =	{118},
  supervisor =  {Martin Pl{\' a}tek},
  authorship =	{100},
  psurl =	{[pdf, 641 KB]},
  annote = { The thesis deal with generalizations of the theory of formal languages to two dimensions.
    The basic structure the theory works with is a two-dimensional array of symbols in a finite alphabet.
    The main studied two-dimensional computational/generative models in the thesis include
    2D Turing machine, 2D finite-state automaton, 2D forgetting automaton, 2D on-line tessellation automaton 
    and 2D grammars with productions in context-free form. Results on computational/generative power, time
    complexity and closure properties are given. The question whether the Chomsky hierarchy can be generalized
    to two dimensions is discussed as well. },
  keywords =    {two-dimensional languages, context-free grammars, automata},