Descriptive complexity of deterministic polylogarithmic time

F. Ferrarotti, S. González Cornejo, J. Turull Torres, J. Van den Bussche, J. Virtema. Descriptive complexity of deterministic polylogarithmic time. volume 11541, pages 208-222, DOI https://doi.org/10.1007/978-3-662-59533-6_13, 7, 2019.

Autoren	Flavio Ferrarotti Senén Andrés González Cornejo José María Turull Torres Jan Van den Bussche Jonni Virtema
Buch	Logic, Language, Information, and Computation - Proc. WoLLIC 2019
Typ	In Konferenzband
Verlag	Springer
Serie	Lecture Notes in Computer Science
Band	11541
DOI	https://doi.org/10.1007/978-3-662-59533-6_13
ISBN	978-3-662-59532-9
Monat	7
Jahr	2019
Seiten	208-222
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 $P o l y l o g T i m e 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$ .