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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139267" target="_blank" >RIV/00216224:14330/24:00139267 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.jcss.2023.103494" target="_blank" >https://doi.org/10.1016/j.jcss.2023.103494</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2023.103494" target="_blank" >10.1016/j.jcss.2023.103494</a>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

1090-2724

Volume of the periodical

141

Issue of the periodical within the volume

103494

Country of publishing house

US - UNITED STATES

Number of pages

13

Pages from-to

1-13

UT code for WoS article

001138384300001

EID of the result in the Scopus database

2-s2.0-85179893976