Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.

Lower bounds for Generalized Quantum Finite Automata

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

Scientific Areas: 
PIRSA Number: 


For most variations of Quantum finite automata (QFA), it is an open question to characterize the language recognition power of these machines. We extend several techniques used to obtain lower bounds on Kondacs and Watrous' 1-way Quantum Finite Automata to the case of Nayak's Generalized Quantum Finite Automata (GQFA). A consequence of these results is that the class of languages recognized by GQFAs is not closed under union.