Recognition Power Analysis of Two-Way Two-Dimensional Finite Automata

The recognition power of three types of two-way two-dimensional finite automata were investigated, including deterministic, nondeterministic and Las Vegas finite automata. By inferences in theory, it was proved that there is a language that can be recognized by two-way two-dimensional Las Vegas finite automaton but can't be recognized by deterministic one, and that there is a language that can be recognized by two-way two-dimensional nondeterministic finite automaton but can't be recognized by Las Vegas one. The following two results are obtained: languages recognized by two-way two-dimensional Las Vegas finite automata strictly contain languages that recognized by deterministic ones; languages recognized by two-way two-dimensional nondeterministic finite automata strictly contain languages that recognized by Las Vegas ones.