Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On the Lower Bounds for One-Way Quantum Automata

Farid AblayevContact Information and Aida GainutdinovaContact Information

(6)  Dept. of Theoretical Cybernetics, Kazan State University, 420008 Kazan, Russia
Abstract
In the paper we consider measured-once (MO-QFA) oneway quantum finite automaton. We prove that for MO-QFA Q that (1/2+ε)-accepts (ε ∈ (0,1/2)) regular language L it holds that dim(Q) = Ω (log dim (A)/log log dim (A)). In the case ε (3/8, 1/2) we have more precise lower bound dim(Q) = Ω (log dim (A)) where A is a minimal deterministic finite automaton accepting L, dim(Q), and dim(A) are complexity (number of states) of automata Q and A respectively, (1/2 - ε) is the error of Q.
The example of language presented in [2] show that our lower bounds are tight enough.
The research supported by Russia Fund for Basic Research 99-01-00163 and Fund “Russia Universities” 04.01.52. The research partially done while first author visited Aahen and Trier Universities

Contact Information Farid Ablayev
Email: ablayev@ksu.ru

Contact Information Aida Gainutdinova
Email: aida@ksu.ru
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)