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
Fingerprint
Dive into the research topics of 'Recognition power analysis of two-way two-dimensional finite automata'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver