Picture Scanning Automata and Group Actions on Pictures

摘要

We are systematically discussing finite automata working on rectangular-shaped arrays (i. e., pictures), reading them with different scanning strategies. We show that all 32 different variants only describe two different classes of array languages. Our main proof tool is using the dihedral group D_4.