摘要
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.
| 源语言 | 英语 |
|---|---|
| 页（从-至） | 1129-1133 |
| 页数 | 5 |
| 期刊 | Beijing Ligong Daxue Xuebao/Transaction of Beijing Institute of Technology |
| 卷 | 32 |
| 期 | 11 |
| 出版状态 | 已出版 - 11月 2012 |