Search

• < Previous
• 1
• Next >

---

Capturing Polynomial Time using Modular Decomposition

Berit Grußien.

The question of whether there is a logic that captures polynomial time is one of the main open problems in descriptive complexity theory and database theory. In 2010 Grohe showed that fixed point logic with counting captures polynomial time on all classes of graphs with excluded minors. We now&nbsp;[&hellip;]

---

Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

Berit Grußien.

We show that the class of chordal claw-free graphs admits LREC$_=$-definable canonization. LREC$_=$ is a logic that extends first-order logic with counting by an operator that allows it to formalize a limited form of recursion. This operator can be evaluated in logarithmic space. It follows that&nbsp;[&hellip;]

---