On the Size of One-way Quantum Finite Automata with Periodic Behaviors
Dipartimento di Informatica, Sist. e Com.,
Università degli Studi di Milano – Bicocca,
Via Bicocca degli Arcimboldi 8,
20126 Milano, Italy; firstname.lastname@example.org.
2 Dipartimento di Informatica, Università degli Studi di Torino, Corso Svizzera 185, 10149 Torino, Italy; email@example.com.
Accepted: 28 May 2002
We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata.
Mathematics Subject Classification: 68Q10 / 68Q19 / 68Q45
Key words: Quantum finite automata / periodic events and languages
© EDP Sciences, 2002