| Summary: | We study quantum finite automata with control language (<span style="font-variant: small-caps;">qfc</span>s), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measure-once, measure-many, reversible, and Latvian <span style="font-variant: small-caps;">qfa</span>s by <span style="font-variant: small-caps;">qfc</span>s, emphasizing the size cost of such simulations. Next, we prove the decidability of testing the periodicity of the stochastic events induced by a given <span style="font-variant: small-caps;">qfc</span>. Thanks to our <span style="font-variant: small-caps;">qfa</span> simulations, we can extend such a decidability result to measure-once, measure-many, reversible, and Latvian <span style="font-variant: small-caps;">qfa</span>s as well. Finally, we focus on comparing the size efficiency of quantum and classical finite state automata on unary regular language recognition. We show that unary regular languages can be recognized by isolated cut point <span style="font-variant: small-caps;">qfc</span>s for which the size is generally quadratically smaller than the size of equivalent <span style="font-variant: small-caps;">dfa</span>s.
|
|---|