Comparison of Two-Way Two-Dimensional Finite Automata and Three-Way Two-Dimensional Finite Automata
Jing Dong, Wenbing Jin · 2012
Three types of two-way two-dimensional finite automata and three-way two-dimensional finite automata are studied, including deterministic, nondeterministic and Las Vegas finite automata. By comparing the languages recognized by above automata, two results are obtained: (1) The power of two-way two-dimensional nondeterministic finite automata and three-way two-dimensional deterministic finite automata cannot be compared, (2) The power of two-way two-dimensional nondeterministic finite automata and three-way two-dimensional Las Vegas finite automata cannot be compared.