On the class of languages recognizable by 1-way quantum finite automata

Simple item page
dc.creatorAmbainis, Andris
dc.creatorKikusts, Arnolds
dc.creatorValdats, Maris
dc.date2000-09-01
dc.date.accessioned2026-07-07T06:00:44Z
dc.date.available2026-07-07T06:00:44Z
dc.descriptionIt is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
dc.description18 pages, 16 figures, extends quant-ph/0001005
dc.identifierhttps://arxiv.org/abs/quant-ph/0009004
dc.identifierhttp://arxiv.org/abs/quant-ph/0009004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/89052
dc.subjectQuantum Physics
dc.titleOn the class of languages recognizable by 1-way quantum finite automata
dc.typetext

Files

Collections

arXiv