Recognition of two-dimensional patterns
Patrick Shen-Pei Wang · 1977
A class of machines capable of recognizing 2-dimensional sequential/parallel matrix languages is introduced. It is called “finite-turn repetitive checking automata” (FTRCA). This checking automaton is provided with three read-write heads, one read only head and a control register in its memory to keep track of the internal transition states and the stack symbols. The value of the register ranges from 0 to a finite positive integer k and can repetitively appear as many times as necessary. A one-to-one correspondence is established between the class of FTRCA and (R:R)ML - the smallest class of the sequential/parallel matrix languages.