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.

Basic information

Original name

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

Authors

ZHENG, Shenggen (156 China); Yaqiao LI; Minghua PAN; Jozef GRUSKA (703 Slovakia, belonging to the institution) and Lvzhou LI

Edition

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

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

is not subject to a state or trade secret

References:

URL

Impact factor

Impact factor: 0.900

RIV identification code

RIV/00216224:14330/24:00139267

Organization unit

Faculty of Informatics

DOI

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

UT WoS

001138384300001

EID Scopus

2-s2.0-85179893976

Keywords in English

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

Abstract

In the original language

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.

Cite

ZHENG, Shenggen; Yaqiao LI; Minghua PAN; Jozef GRUSKA and Lvzhou LI. Lifting query complexity to time-space complexity for two-way finite automata. Journal of Computer and System Sciences. San Diego: Elsevier, 2024, vol. 141, No 103494, p. 1-13. ISSN 0022-0000. Available from: 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 and 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, vol.~141, No~103494, p.~1-13. ISSN~0022-0000. Available from: https://doi.org/10.1016/j.jcss.2023.103494.

Přehled o publikaci