7 citations · 13 across the 5 of their papers we have counts for
5 papers
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 t…
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 allo…
L-Recursion and a new Logic for Logarithmic Space
Martin Grohe, Berit Grußien, André Hernich +1
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…
Isoperimetric Inequalities on Hexagonal Grids
Berit Grußien
We consider the edge- and vertex-isoperimetric probem on finite and infinite hexagonal grids: For a subset W of the hexagonal grid of given cardinality, we give a lower bound for t…
Arc Consistency and Friends
Hubie Chen, Victor Dalmau, Berit Grußien
A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a c…