Revision as of 09:55, 7 February 2014 edit Jochen Burghardt (talk \| contribs) Extended confirmed users 24,311 edits →References: ((reflist)) ← Previous edit		Revision as of 09:56, 7 February 2014 edit undo Jochen Burghardt (talk \| contribs) Extended confirmed users 24,311 edits inlined quantum ref Next edit →
Line 11: The concept of 2DFAs, originated by [[Michael O. Rabin\|Rabin]] and [[Dana Scott\|Scott]] in their 1959 seminal work "Finite automata and their decision problems", was in 1997 generalized to [[quantum computing]] by [[John Watrous (computer scientist)\|John Watrous]]'s "On the Power of 2-Way Quantum Finite State Automata", in which he demonstrates that these machines can recognize nonregular languages and so are more powerful than DFAs. * <ref>[[John Watrous (computer scientist)\|John Watrous]]. [http://citeseer.ist.psu.edu/article/watrous97power.html On the Power of 2-Way Quantum Finite State Automata]. CS-TR-1997-1350. 1997. [ftp://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf]</ref>▼ ==Two-way pushdown automaton== Line 29 ⟶ 30: * Hing Leung. [http://www.math.nmsu.edu/hist_projects/2DFA.pdf Two-Way Deterministic Finite Automata]. * M. O. Rabin and D. Scott. Finite automata and their decision problems. ''IBM Journal of Research and Development'', 3, 114–125. 1959. ▲* [[John Watrous (computer scientist)\|John Watrous]]. [http://citeseer.ist.psu.edu/article/watrous97power.html On the Power of 2-Way Quantum Finite State Automata]. CS-TR-1997-1350. 1997. [ftp://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf] [[Category:Automata theory]]

Two-way finite automaton: Difference between revisions