One-way finite automata with quantum and classical states
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00059150" target="_blank" >RIV/00216224:14330/12:00059150 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-31644-9_19" target="_blank" >http://dx.doi.org/10.1007/978-3-642-31644-9_19</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-31644-9_19" target="_blank" >10.1007/978-3-642-31644-9_19</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
One-way finite automata with quantum and classical states
Popis výsledku v původním jazyce
In this paper, we introduce and explore a new model of quantum finite automata (QFA). Namely, one-way finite automata with quantum and classical states (1QCFA), a one way version of two-way finite automata with quantum and classical states (2QCFA) introduced by Ambainis and Watrous in 2002. First, we prove that one-way probabilistic finite automata (1PFA) and one-way quantum finite automata with control language (1QFACL), as well as several other models of QFA, can be simulated by 1QCFA. Afterwards, weexplore several closure properties for the family of languages accepted by 1QCFA. Finally, the state complexity of 1QCFA is explored and the main succinctness result is derived.
Název v anglickém jazyce
One-way finite automata with quantum and classical states
Popis výsledku anglicky
In this paper, we introduce and explore a new model of quantum finite automata (QFA). Namely, one-way finite automata with quantum and classical states (1QCFA), a one way version of two-way finite automata with quantum and classical states (2QCFA) introduced by Ambainis and Watrous in 2002. First, we prove that one-way probabilistic finite automata (1PFA) and one-way quantum finite automata with control language (1QFACL), as well as several other models of QFA, can be simulated by 1QCFA. Afterwards, weexplore several closure properties for the family of languages accepted by 1QCFA. Finally, the state complexity of 1QCFA is explored and the main succinctness result is derived.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2012
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Languages Alive Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
ISBN
9783642316432
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
18
Strana od-do
273-290
Název nakladatele
Springer-Verlag
Místo vydání
Německo
Místo konání akce
Německo
Datum konání akce
1. 1. 2012
Typ akce podle státní příslušnosti
CST - Celostátní akce
Kód UT WoS článku
—