Lifting query complexity to time-space complexity for two-way
finite automata

J 2024

Lifting query complexity to time-space complexity for two-way finite automata

ZHENG, Shenggen; Yaqiao LI; Minghua PAN; Jozef GRUSKA; Lvzhou LI et. al.

Základní údaje

Originální název

Lifting query complexity to time-space complexity for two-way finite automata

Autoři

ZHENG, Shenggen (156 Čína); Yaqiao LI; Minghua PAN; Jozef GRUSKA (703 Slovensko, domácí) a Lvzhou LI

Vydání

Journal of Computer and System Sciences, San Diego, Elsevier, 2024, 0022-0000

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.900

Kód RIV

RIV/00216224:14330/24:00139267

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/j.jcss.2023.103494

UT WoS

001138384300001

EID Scopus

2-s2.0-85179893976

Klíčová slova anglicky

Quantum computing; Time-space complexity; Two-way finite automata; Communication complexity; Lifting theorems; Query algorithms

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 2. 4. 2025 00:48, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language L such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is ⠂⠂(n2), while of exact two-way quantum finite automata with classical states (2QCFA) is O ⠂(n5/3), that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing. (c) 2023 Elsevier Inc. All rights reserved.

Citovat

ZHENG, Shenggen; Yaqiao LI; Minghua PAN; Jozef GRUSKA a Lvzhou LI. Lifting query complexity to time-space complexity for two-way finite automata. Journal of Computer and System Sciences. San Diego: Elsevier, 2024, roč. 141, č. 103494, s. 1-13. ISSN 0022-0000. Dostupné z: https://doi.org/10.1016/j.jcss.2023.103494.

@article{2488460,
   author = {Zheng, Shenggen and Li, Yaqiao and Pan, Minghua and Gruska, Jozef and Li, Lvzhou},
   article_location = {San Diego},
   article_number = {103494},
   doi = {https://doi.org/10.1016/j.jcss.2023.103494},
   keywords = {Quantum computing; Time-space complexity; Two-way finite automata; Communication complexity; Lifting theorems; Query algorithms},
   language = {eng},
   issn = {0022-0000},
   journal = {Journal of Computer and System Sciences},
   title = {Lifting query complexity to time-space complexity for two-way finite automata},
   url = {https://doi.org/10.1016/j.jcss.2023.103494},
   volume = {141},
   year = {2024}
}

TY  - JOUR
ID  - 2488460
AU  - Zheng, Shenggen - Li, Yaqiao - Pan, Minghua - Gruska, Jozef - Li, Lvzhou
PY  - 2024
TI  - Lifting query complexity to time-space complexity for two-way finite automata
JF  - Journal of Computer and System Sciences
VL  - 141
IS  - 103494
SP  - 1-13
EP  - 1-13
PB  - Elsevier
SN  - 00220000
KW  - Quantum computing
KW  - Time-space complexity
KW  - Two-way finite automata
KW  - Communication complexity
KW  - Lifting theorems
KW  - Query algorithms
UR  - https://doi.org/10.1016/j.jcss.2023.103494
N2  - Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language L such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is ⠂⠂(n2), while of exact two-way quantum finite automata with classical states (2QCFA) is O ⠂(n5/3), that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing. (c) 2023 Elsevier Inc. All rights reserved.
ER  -

ZHENG, Shenggen; Yaqiao LI; Minghua PAN; Jozef GRUSKA a Lvzhou LI. Lifting query complexity to time-space complexity for two-way finite automata. \textit{Journal of Computer and System Sciences}. San Diego: Elsevier, 2024, roč.~141, č.~103494, s.~1-13. ISSN~0022-0000. Dostupné z: https://doi.org/10.1016/j.jcss.2023.103494.

Přehled o publikaci