Computer Science – Computational Complexity
Scientific paper
2007-01-22
Computer Science
Computational Complexity
19 pages. A preliminary version appears under the title "On a Model of Computation based on Optical Interference" in Proc. of
Scientific paper
We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of optical interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis and J. Watrous, Two-way Finite Automata With Quantum and Classical States, Theoretical Computer Science, 287 (1), 299-311, (2002)] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Finally we show the existence of a language that cannot be recognized by a 2OIA but can be recognized by an $O(n^3)$ space Turing machine.
No associations
LandOfFree
Interference Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interference Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interference Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-516089