Computer Science – Discrete Mathematics
Scientific paper
2008-07-03
Computer Science
Discrete Mathematics
This is a draft and primary version, and a deep study will be done
Scientific paper
This paper deals with the size complexity of minimal {\it two-way quantum finite automata} (2qfa's) necessary for operations to perform on all inputs of each fixed length. Such a complexity measure, known as state complexity of operations, is useful in measuring how much information is necessary to convert languages. We focus on intersection, union, reversals, and catenation operations and show some upper bounds of state complexity of operations on 2qfa's. Also, we present a number of non-regular languages and prove that these languages can be accepted by 2qfa's with one-sided error probabilities within linear time. Notably, these examples show that our bounds obtained for these operations are not tight, and therefore worth improving. We give an instance to show that the upper bound of the state number for the simulation of one-way deterministic finite automata by two-way reversible finite automata is not tight in general.
No associations
LandOfFree
Research report: State complexity of operations on two-way quantum finite 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 Research report: State complexity of operations on two-way quantum finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Research report: State complexity of operations on two-way quantum finite automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-115172