3 citations · 4 across the 4 of their papers we have counts for
6 papers
The parameterized space complexity of model-checking bounded variable first-order logic
Yijia Chen, Michael Elberfeld, Moritz Müller
The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational stru…
Order Invariance on Decomposable Structures
Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe
Order-invariant formulas access an ordering on a structure's universe, but the model relation is independent of the used ordering. Order invariance is frequently used for logic-bas…
Succinctness of Order-Invariant Logics on Depth-Bounded Structures
Kord Eickmeyer, Michael Elberfeld, Frederik Harwath
We study the expressive power and succinctness of order-invariant sentences of first-order (FO) and monadic second-order (MSO) logic on structures of bounded tree-depth. Order- inv…
Canonizing Graphs of Bounded Tree Width in Logspace
Michael Elberfeld, Pascal Schweitzer
Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if…
Where First-Order and Monadic Second-Order Logic Coincide
Michael Elberfeld, Martin Grohe, Till Tantau
We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for all classes C of graphs that are cl…
Perfect Phylogeny Haplotyping is Complete for Logspace
Michael Elberfeld
Haplotyping is the bioinformatics problem of predicting likely haplotypes based on given genotypes. It can be approached using Gusfield's perfect phylogeny haplotyping (PPH) method…