State succinctness of two-way finite automata with quantum and classical states (2013)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/13:00072831 |
|---|---|
| Název v anglickém jazyce | State succinctness of two-way finite automata with quantum and classical states |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2013 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 2 |
| Výčet všech uvedených jednotlivých tvůrců | Shenggen Zheng (státní příslušnost: CN - Čínská lidová republika, domácí tvůrce: A) Daowen Qiu (státní příslušnost: CN - Čínská lidová republika) Jozef Gruska (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9594744) Lvzhou Li (státní příslušnost: CN - Čínská lidová republika) Paulo Mateus (státní příslušnost: PT - Portugalská republika) |
| Popis výsledku v anglickém jazyce | Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m from Z+ and any e<1/2, we show that: 1.there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error e in a polynomial expected running time with a constant number (that depends neither on m nor on eps) of quantum states and View the MathML source classical states, whereas the sizes of the correspondingdeterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m+2, View the MathML source, and View the MathML source, respectively; 2. |
| Klíčová slova oddělená středníkem | Computing models; Quantum finite automata; State complexity; Succinctness |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1016/j.tcs.2013.06.005 |
Údaje o výsledku v závislosti na druhu výsledku
| Název periodika | Theoretical Computer Science |
|---|---|
| ISSN | 0304-3975 |
| Svazek periodika | 499 |
| Číslo periodika v rámci uvedeného svazku | 1 |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 15 |
| Strana od-do | 98-112 |
| Kód UT WoS článku podle Web of Science | 000323809200007 |
| EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2014 |
| Specifikace | RIV/00216224:14330/13:00072831!RIV14-MSM-14330___ |
| Datum poslední aktualizace výsledku | 29.05.2014 |
| Kontrolní číslo | 56540959 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný MŠMT v programu LG | LG13010 - Zastoupení ČR v European Research Consortium for Informatics and Mathematics (2013 - 2015) |
|---|---|
| Podpora / návaznosti | Institucionální podpora na rozvoj výzkumné organizace |