Title :
Comparison of Two-Way Two-Dimensional Finite Automata and Three-Way Two-Dimensional Finite Automata
Author :
Dong, Jing ; Jin, Wenbing
Author_Institution :
Sch. of Comput. Sci., Beijing Inst. of Technol., Beijing, China
Abstract :
Three types of two-way two-dimensional finite automata and three-way two-dimensional finite automata are studied, including deterministic, nondeterministic and Las Vegas finite automata. By comparing the languages recognized by above automata, two results are obtained: (1) The power of two-way two-dimensional nondeterministic finite automata and three-way two-dimensional deterministic finite automata cannot be compared, (2) The power of two-way two-dimensional nondeterministic finite automata and three-way two-dimensional Las Vegas finite automata cannot be compared.
Keywords :
deterministic automata; finite automata; Las Vegas finite automata; deterministic finite automata; nondeterministic finite automata; three way two dimensional finite automata; two way two dimensional finite automata; Automata; Complexity theory; Computer science; Educational institutions; Electronic mail; Finishing; Magnetic heads; Las Vegas finite automata; deterministic finite automata; nondeterministic finite automata; two-dimensional finite automata;
Conference_Titel :
Computer Science & Service System (CSSS), 2012 International Conference on
Conference_Location :
Nanjing
Print_ISBN :
978-1-4673-0721-5
DOI :
10.1109/CSSS.2012.474
