RIV/00216224:14330/13:00072831 - State succinctness of two-way finite automata with quantum and classical states (2013)

Údaje o výsledku
Identifikační kódRIV/00216224:14330/13:00072831
Název v původním jazyceState succinctness of two-way finite automata with quantum and classical states
DruhJ - Článek v odborném periodiku
Jazykeng - angličtina
OborIN - 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ýsledku1
Údaje z Hodnocení výsledků výzkumných organizací 2014
Výsledek byl hodnocen v Pilíři I
Rozsah vyřazení výsledkuTento 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 korekce86,1 %
Body (upravené podle přílohy č. 8 Metodiky)13,274
Rozdělení výsledku mezi předkladatele
OrganizaceVýzkumná organizace?PodílBodyBody (upravené podle přílohy č. 8 Metodiky)
Masarykova univerzita / Fakulta informatikyano57,1 %8,8087,585
Tvůrci výsledku
Počet tvůrců celkem5
Počet domácích tvůrců2
TvůrceZheng Shenggen (státní příslušnost: CN - Čínská lidová republika; A - domácí tvůrce)
TvůrceQiu Daowen (státní příslušnost: CN - Čínská lidová republika)
TvůrceGruska Jozef (státní příslušnost: SK - Slovenská republika; A - domácí tvůrce; vedidk: 9594744)
TvůrceLi Lvzhou (státní příslušnost: CN - Čínská lidová republika)
TvůrceMateus Paulo (státní příslušnost: PT - Portugalská republika)
Údaje blíže specifikující výsledek
Popis v původním jazyceTwo-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á slovaComputing models; Quantum finite automata; State complexity; Succinctness
Kód UT ISI000323809200007
Rozsah stran98-112
Název periodkaTheoretical Computer Science
ISSN0304-3975
Svazek periodika499
Číslo periodika v rámci uvedeného svazku1
Stát vydavatele periodikaNL - Nizozemsko
Počet stran výsledku15
DOI výsledku10.1016/j.tcs.2013.06.005
Údaje o tomto záznamu o výsledku
PředkladatelMasarykova univerzita / Fakulta informatiky
DodavatelMSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT)
Rok sběru2014
Systémové označení dodávky datRIV14-MSM-14330___/01:1
SpecifikaceRIV/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
ProjektLG13010 - Zastoupení ČR v European Research Consortium for Informatics and Mathematics (2013-2015, MSM/LG)
I - Instit. podpora na rozvoj výzkumné organizace