A1 Refereed original research article in a scientific journal
A Survey on Picture-Walking Automata
Authors: Kari J, Salo V
Editors: Werner Kuich, George Rahonis
Publication year: 2011
Journal: Lecture Notes in Computer Science
Book title : Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement
Journal name in source: ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE
Journal acronym: LECT NOTES COMPUT SC
Volume: 7020
First page : 183
Last page: 213
Number of pages: 31
ISBN: 978-3-642-24896-2
ISSN: 0302-9743
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.
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.
UTU Research Portal