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;]

---

L-Recursion and a new Logic for Logarithmic Space

Martin Grohe ; Berit Grußien ; André Hernich ; Bastian Laubner.

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and&nbsp;[&hellip;]

---