Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/34150
Title: | Descriptive complexity of deterministic polylogarithmic time and space | Authors: | Ferrarotti, Flavio Gonzalez, Senen Turull Torres, Jose Maria VAN DEN BUSSCHE, Jan VIRTEMA, Jonni |
Issue Date: | 2021 | Publisher: | ACADEMIC PRESS INC ELSEVIER SCIENCE | Source: | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 119 , p. 145 -163 | Abstract: | We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two sorted logic that separates the elements of the input domain from the bit positions needed to address these elements. We prove that the inflationary and partial fixed point variants of this logic capture PolylogTime and PolylogSpace, respectively. In the course of proving that our logic indeed captures PolylogTime on finite ordered structures, we introduce a variant of random-access Turing machines that can access the relations and functions of a structure directly. We investigate whether an explicit predicate for the ordering of the domain is needed in our PolylogTime logic. Finally, we present the open problem of finding an exact characterization of order-invariant queries in PolylogTime. (C) 2021 Elsevier Inc. All rights reserved. | Notes: | Ferrarotti, F (corresponding author), Software Competence Ctr Hagenberg, Hagenberg Im Muhlkreis, Austria. flavio.ferrarotti@scch.at |
Other: | Ferrarotti, F (corresponding author), Software Competence Ctr Hagenberg, Hagenberg Im Muhlkreis, Austria. flavio.ferrarotti@scch.at | Keywords: | Descriptive complexity;Polylogarithmic queries | Document URI: | http://hdl.handle.net/1942/34150 | ISSN: | 0022-0000 | e-ISSN: | 1090-2724 | DOI: | 10.1016/j.jcss.2021.02.003 | ISI #: | WOS:000634149800010 | Rights: | © 2021 Elsevier Inc. All rights reserved. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2022 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dplog.pdf | Peer-reviewed author version | 485.3 kB | Adobe PDF | View/Open |
1-s20-S0022000021000180-main.pdf Restricted Access | Published version | 560.59 kB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.