Recognition power analysis of two-way two-dimensional finite automata

Jing Dong, Qing Hui Liu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)1129-1133
Number of pages5
JournalBeijing Ligong Daxue Xuebao/Transaction of Beijing Institute of Technology
Volume32
Issue number11
Publication statusPublished - 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

Dong, J., & Liu, Q. H. (2012). Recognition power analysis of two-way two-dimensional finite automata. Beijing Ligong Daxue Xuebao/Transaction of Beijing Institute of Technology, 32(11), 1129-1133.