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/

Zendy Plus

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

Zendy Tools

Zendy Open

The question of whether there is a logic that captures polynomial time wasformulated by Yuri Gurevich in 1988. It is still wide open and regarded as oneof the main open problems in finite model theory and database theory. Partialresults have been obtained for specific classes of structures. In particular,it is known that fixed-point logic with counting captures polynomial time onall classes of graphs with excluded minors. The introductory part of this paperis a short survey of the state-of-the-art in the quest for a logic capturingpolynomial time.  The main part of the paper is concerned with classes of graphs defined byexcluding induced subgraphs. Two of the most fundamental such classes are theclass of chordal graphs and the class of line graphs. We prove that capturingpolynomial time on either of these classes is as hard as capturing it on theclass of all graphs. In particular, this implies that fixed-point logic withcounting does not capture polynomial time on these classes. Then we prove thatfixed-point logic with counting does capture polynomial time on the class ofall graphs that are both chordal and line graphs.

Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs