Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/30376
Title: | Descriptive Complexity of Deterministic Polylogarithmic Time | Authors: | Ferrarotti, Flavio González, Senén Turull Torres, José María VAN DEN BUSSCHE, Jan VIRTEMA, Jonni |
Issue Date: | 2019 | Publisher: | Springer Nature | Source: | Iemhoff, Rosalie; Moortgat, Michael; de Queiroz, Ruy (Ed.). Logic, Language, Information, and Computation, Springer Nature, p. 208 -222 | Series/Report: | Lecture Notes in Computer Science | Abstract: | We propose a logical characterization of problems solvable in deterministic polylogarithmic time (PolylogTime). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit positions needed to address these elements. 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 the structure directly. We investigate whether an explicit predicate for the ordering of the domain is needed in our logic. Finally, we present the open problem of finding an exact characterization of order-invariant queries in PolylogTime. | Document URI: | http://hdl.handle.net/1942/30376 | ISBN: | 9783662595329 | ISSN: | 0302-9743 | DOI: | 10.1007/978-3-662-59533-6_13 | Rights: | 2019 Springer Nature Switzerland AG. Part of Springer Nature. | Category: | A1 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dplog.pdf | Peer-reviewed author version | 346.13 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 7, 2020
WEB OF SCIENCETM
Citations
2
checked on May 2, 2024
Page view(s)
48
checked on Sep 7, 2022
Download(s)
16
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.