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

Motivated by the search for a logic for polynomial time, we study rank logic(FPR) which extends fixed-point logic with counting (FPC) by operators thatdetermine the rank of matrices over finite fields. While FPR can express mostof the known queries that separate FPC from PTIME, nearly nothing was knownabout the limitations of its expressive power.  In our first main result we show that the extensions of FPC by rank operatorsover different prime fields are incomparable. This solves an open questionposed by Dawar and Holm and also implies that rank logic, in its originaldefinition with a distinct rank operator for every field, fails to capturepolynomial time. In particular we show that the variant of rank logic FPR* withan operator that uniformly expresses the matrix rank over finite fields is moreexpressive than FPR.  One important step in our proof is to consider solvability logic FPS which isthe analogous extension of FPC by quantifiers which express the solvabilityproblem for linear equation systems over finite fields. Solvability logic caneasily be embedded into rank logic, but it is open whether it is a strictfragment. In our second main result we give a partial answer to this question:in the absence of counting, rank operators are strictly more expressive thansolvability quantifiers.

Rank logic is dead, long live rank logic!