Údaje o výsledku |
Identifikační kód | RIV/00216224:14330/13:00072831 |
Název v původní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 | IN - Informatika |
Rok uplatnění | 2013 |
Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
Počet výskytů výsledku | 1 |
Údaje z Hodnocení výsledků výzkumných organizací 2014 |
Výsledek byl hodnocen v Pilíři I |
Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
Zařazení výsledku v hodnocení | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
Konkrétní způsob(y) hodnocení výsledku | Článek v impaktovaném časopise evidovaném ve Web of Science |
Bodové ohodnocení | 15,414 |
Faktor korekce | 86,1 % |
Body (upravené podle přílohy č. 8 Metodiky) | 13,274 |
Rozdělení výsledku mezi předkladatele |
Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
Masarykova univerzita / Fakulta informatiky | ano | 57,1 % | 8,808 | 7,585 |
|
Tvůrci výsledku |
Počet tvůrců celkem | 5 |
Počet domácích tvůrců | 2 |
Tvůrce | Zheng Shenggen (státní příslušnost: CN - Čínská lidová republika; A - domácí tvůrce) |
Tvůrce | Qiu Daowen (státní příslušnost: CN - Čínská lidová republika) |
Tvůrce | Gruska Jozef (státní příslušnost: SK - Slovenská republika; A - domácí tvůrce; vedidk: 9594744) |
Tvůrce | Li Lvzhou (státní příslušnost: CN - Čínská lidová republika) |
Tvůrce | Mateus Paulo (státní příslušnost: PT - Portugalská republika) |
Údaje blíže specifikující výsledek |
Popis v původní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 corresponding deterministic 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 | Computing models; Quantum finite automata; State complexity; Succinctness |
Kód UT ISI | 000323809200007 |
Rozsah stran | 98-112 |
Název periodka | 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 |
DOI výsledku | 10.1016/j.tcs.2013.06.005 |
Údaje o tomto záznamu 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 |
Systémové označení dodávky dat | RIV14-MSM-14330___/01:1 |
Specifikace | RIV/00216224:14330/13:00072831!RIV14-MSM-14330___ |
Kontrolní kód | [2F7197945BD8] |
Jiný výskyt tohoto výsledku se v RIV nenachází |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
Projekt | LG13010 - Zastoupení ČR v European Research Consortium for Informatics and Mathematics (2013-2015, MSM/LG) |
I - Instit. podpora na rozvoj výzkumné organizace |