English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $\mathrm{SO}^{\mathit{plog}}$ denote the restriction of second-orderlogic, where second-order quantification ranges over relations of size at mostpoly-logarithmic in the size of the structure. In this article we investigatethe problem, which Turing machine complexity class is captured by Booleanqueries over ordered relational structures that can be expressed in this logic.For this we define a hierarchy of fragments $\Sigma^{\mathit{plog}}_m$ (and$\Pi^{\mathit{plog}}_m$) defined by formulae with alternating blocks ofexistential and universal second-order quantifiers in quantifier-prenex normalform. We first show that the existential fragment $\Sigma^{\mathit{plog}}_1$captures NPolyLogTime, i.e. the class of Boolean queries that can be acceptedby a non-deterministic Turing machine with random access to the input in time$O((\log n)^k)$ for some $k \ge 0$. Using alternating Turing machines withrandom access input allows us to characterise also the fragments$\Sigma^{\mathit{plog}}_m$ (and $\Pi^{\mathit{plog}}_m$) as those Booleanqueries with at most $m$ alternating blocks of second-order quantifiers thatare accepted by an alternating Turing machine. Consequently,$\mathrm{SO}^{\mathit{plog}}$ captures the whole poly-logarithmic timehierarchy. We demonstrate the relevance of this logic and complexity class byseveral problems in database theory.

The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic