PIRSA:07060028

Video URL

https://pirsa.org/07060028

Lower bounds for Generalized Quantum Finite Automata

Mercer, M. (2007). Lower bounds for Generalized Quantum Finite Automata. Perimeter Institute for Theoretical Physics. https://pirsa.org/07060028

Mercer, Mark. Lower bounds for Generalized Quantum Finite Automata. Perimeter Institute for Theoretical Physics, Jun. 04, 2007, https://pirsa.org/07060028 

          @misc{ scivideos_PIRSA:07060028,
            doi = {10.48660/07060028},
            url = {https://pirsa.org/07060028},
            author = {Mercer, Mark},
            keywords = {Quantum Information},
            language = {en},
            title = {Lower bounds for Generalized Quantum Finite Automata},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2007},
            month = {jun},
            note = {PIRSA:07060028 see, \url{https://scivideos.org/index.php/pirsa/07060028}}
          }

Mark Mercer McGill University

Talk numberPIRSA:07060028
DOI10.48660/07060028
Source RepositoryPIRSA
Collection
Talk Type Conference
Subject

Abstract

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.