Issue Theoret. Informatics Appl. Volume 36, Number 3, July-September 2002 Page(s) 277 - 291 DOI 10.1051/ita:2002014

Theoret. Informatics Appl. 36, 277-291 (2002)
DOI: 10.1051/ita:2002014

On the Size of One-way Quantum Finite Automata with Periodic Behaviors

Carlo Mereghetti¹ and Beatrice Palano<sup>2

1</sup>  Dipartimento di Informatica, Sist. e Com., Università degli Studi di Milano - Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy; mereghetti@disco.unimib.it.
²  Dipartimento di Informatica, Università degli Studi di Torino, Corso Svizzera 185, 10149 Torino, Italy; beatrice@di.unito.it.

(Received February 19, 2002. Accepted May 28, 2002.)

Abstract
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, , satisfying . 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

What is OpenURL?