Search

• < Previous
• 1
• Next >

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

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