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

We study first-order model checking, by which we refer to the problem ofdeciding whether or not a given first-order sentence is satisfied by a givenfinite structure. In particular, we aim to understand on which sets ofsentences this problem is tractable, in the sense of parameterized complexitytheory. To this end, we define the notion of a graph-like sentence set, whichdefinition is inspired by previous work on first-order model checking whereinthe permitted connectives and quantifiers were restricted. Our main theorem isthe complete tractability classification of such graph-like sentence sets,which is (to our knowledge) the first complexity classification theoremconcerning a class of sentences that has no restriction on the connectives andquantifiers. To present and prove our classification, we introduce and developa novel complexity-theoretic framework which is built on parameterizedcomplexity and includes new notions of reduction.

The Tractability Frontier of Graph-Like First-Order Query Sets