Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A Survey on Picture-Walking Au...

A Survey on Picture-Walking Automata

Jarkko Kari, Ville Salo, A Survey on Picture-Walking Automata. In: Werner Kuich, George Rahonis (Eds.), Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement, Lecture Notes in Computer Science 7020, 183–213, Springer, 2011.

Abstract:

Picture walking automata were introduced by M. Blum and C. Hewitt in 1967 as a generalization of one-dimensional two-way finite automata to recognize pictures, or two-dimensional words. Several variants have been investigated since then, including deterministic, non-deterministic and alternating transition rules; four-, three- and two-way movements; single- and multi-headed variants; automata that must stay inside the input picture, or that may move outside. We survey results that compare the recognition power of different variants, consider their basic closure properties and study decidability questions.

BibTeX entry:

@INBOOK{cKaSa11a,
  title = {A Survey on Picture-Walking Automata},
  booktitle = {Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement},
  author = {Kari, Jarkko and Salo, Ville},
  volume = {7020},
  series = {Lecture Notes in Computer Science},
  editor = {Kuich, Werner and Rahonis, George},
  publisher = {Springer},
  pages = {183–213},
  year = {2011},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication