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

Issue		RAIRO-Theor. Inf. 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²

¹ 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 $2\sqrt{6n}+25$ states inducing the event ap+b, for constants a>0, $b\!\geq 0$ , satisfying $a+b\leq1$ . 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 $2\sqrt{6n}+26$ 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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.