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 to understand exactly which order-invariant queries are in PolylogTime. |
Year | Venue | Field |
---|---|---|
2019 | WoLLIC | Discrete mathematics,Open problem,Computer science,Descriptive complexity theory,Turing machine,Predicate (grammar) |
DocType | Volume | Citations |
Journal | abs/1903.03413 | 0 |
PageRank | References | Authors |
0.34 | 4 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Flavio Ferrarotti | 1 | 89 | 17.05 |
Senén González | 2 | 0 | 0.34 |
José Maria Turull Torres | 3 | 0 | 0.34 |
Jan Van den Bussche | 4 | 1859 | 602.40 |
Jonni Virtema | 5 | 79 | 11.93 |