1 citations · 1 across the 3 of their papers we have counts for
4 papers · 1 filter
The Descriptive Complexity of Relation Modification Problems
Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz +2
A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined p…
On the Descriptive Complexity of Vertex Deletion Problems
Max Bannach, Florian Chudigiewitsch, Till Tantau
Vertex deletion problems for graphs are studied intensely in classical and parameterized complexity theory. They ask whether we can delete at most k vertices from an input graph su…
Existential Second-Order Logic Over Graphs: Parameterized Complexity
Max Bannach, Florian Chudigiewitsch, Till Tantau
By Fagin's Theorem, NP contains precisely those problems that can be described by formulas starting with an existential second-order quantifier, followed by only first-order quanti…
Computational Complexity of Deciding Provability in Linear Logic and its Fragments
Florian Chudigiewitsch
Linear logic was conceived in 1987 by Girard and, in contrast to classical logic, restricts the usage of the structural inference rules of weakening and contraction. With this, ato…