A Survey on Picture-Walking Automata



: Kari J, Salo V

: Werner Kuich, George Rahonis

: 2011

: Lecture Notes in Computer Science

: Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement

: ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE

: LECT NOTES COMPUT SC

: 7020

: 183

: 213

: 31

: 978-3-642-24896-2

: 0302-9743


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.



Last updated on 2024-26-11 at 20:12