Two-dimensional Automata: Shift Spaces and Recognizable Languages

Computers are essentially one-dimensional finite state automata capable of reading instructions via one-dimensional strings of data. Two-dimensional automata and the increased computing power that comes with the ability to read two-dimensional blocks of data could revolutionize technology. This text defines the first working model for two-dimensional automata recognizing shift spaces and then describes characteristics related to the languages of the shift spaces that are represented. In particular, graphs are used to examine periodicity in two-dimensional shift spaces and to categorize certain types of transitivity in two-dimensional languages. The text is an excellent introduction to two-dimensional computing. The clear exposition, along with a variety of illustrations, makes the subject matter accessible to undergraduate students and to anyone casually interested in the subject, while the inclusion of groundbreaking theorems and open questions provides content for consideration by the serious mathematician or computer scientist.