A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A Survey on Picture-Walking Automata
Tekijät: Kari J, Salo V
Toimittaja: Werner Kuich, George Rahonis
Julkaisuvuosi: 2011
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement
Tietokannassa oleva lehden nimi: ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 7020
Aloitussivu: 183
Lopetussivu: 213
Sivujen määrä: 31
ISBN: 978-3-642-24896-2
ISSN: 0302-9743
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali