Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/34150
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ferrarotti, Flavio | - |
dc.contributor.author | Gonzalez, Senen | - |
dc.contributor.author | Turull Torres, Jose Maria | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.contributor.author | VIRTEMA, Jonni | - |
dc.date.accessioned | 2021-05-30T17:06:19Z | - |
dc.date.available | 2021-05-30T17:06:19Z | - |
dc.date.issued | 2021 | - |
dc.date.submitted | 2021-04-27T10:02:53Z | - |
dc.identifier.citation | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 119 , p. 145 -163 | - |
dc.identifier.uri | http://hdl.handle.net/1942/34150 | - |
dc.description.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. | - |
dc.description.sponsorship | The research reported in this paper results from the project Higher-Order Logics and Structures supported by the Austrian Science Fund (FWF:[I2420N31]) and the Research Foundation Flanders (FWO:[G0G6516N]). It was further supported by the Austrian Ministry for Transport, Innovation and Technology, the Federal Ministry of Science, Research and Economy, and the Province of Upper Austria in the frame of the COMET center SCCH. The last author was partially suported by the DFG grant VI 1045/1-1. | - |
dc.language.iso | en | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.rights | © 2021 Elsevier Inc. All rights reserved. | - |
dc.subject.other | Descriptive complexity | - |
dc.subject.other | Polylogarithmic queries | - |
dc.title | Descriptive complexity of deterministic polylogarithmic time and space | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 163 | - |
dc.identifier.spage | 145 | - |
dc.identifier.volume | 119 | - |
local.format.pages | 19 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Ferrarotti, F (corresponding author), Software Competence Ctr Hagenberg, Hagenberg Im Muhlkreis, Austria. | - |
dc.description.notes | flavio.ferrarotti@scch.at | - |
dc.description.other | Ferrarotti, F (corresponding author), Software Competence Ctr Hagenberg, Hagenberg Im Muhlkreis, Austria. flavio.ferrarotti@scch.at | - |
local.publisher.place | 525 B ST, STE 1900, SAN DIEGO, CA 92101-4495 USA | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.1016/j.jcss.2021.02.003 | - |
dc.identifier.isi | WOS:000634149800010 | - |
local.provider.type | wosris | - |
local.uhasselt.uhpub | yes | - |
local.description.affiliation | [Ferrarotti, Flavio; Gonzalez, Senen] Software Competence Ctr Hagenberg, Hagenberg Im Muhlkreis, Austria. | - |
local.description.affiliation | [Turull Torres, Jose Maria] Univ Nacl La Matanza, San Justo, Argentina. | - |
local.description.affiliation | [Van den Bussche, Jan; Virtema, Jonni] Hasselt Univ, Hasselt, Belgium. | - |
local.description.affiliation | [Virtema, Jonni] Leibniz Univ Hannover, Hannover, Germany. | - |
local.uhasselt.international | yes | - |
item.contributor | Ferrarotti, Flavio | - |
item.contributor | Gonzalez, Senen | - |
item.contributor | Turull Torres, Jose Maria | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.contributor | VIRTEMA, Jonni | - |
item.fullcitation | Ferrarotti, Flavio; Gonzalez, Senen; Turull Torres, Jose Maria; VAN DEN BUSSCHE, Jan & VIRTEMA, Jonni (2021) Descriptive complexity of deterministic polylogarithmic time and space. In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 119 , p. 145 -163. | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2022 | - |
crisitem.journal.issn | 0022-0000 | - |
crisitem.journal.eissn | 1090-2724 | - |
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 |
WEB OF SCIENCETM
Citations
1
checked on May 2, 2024
Page view(s)
40
checked on Sep 7, 2022
Download(s)
22
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.