Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 1129-1133 |
Number of pages | 5 |
Journal | Beijing Ligong Daxue Xuebao/Transaction of Beijing Institute of Technology |
Volume | 32 |
Issue number | 11 |
Publication status | Published - Nov 2012 |
Keywords
- Deterministic
- Las Vegas
- Nondeterministic
- Two-dimensional two way