3 citations · 3 across the 1 of their papers we have counts for
4 papers
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…
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…