2 papers
cs.LO2016
Order-Invariance of Two-Variable Logic is Decidable
Thomas Zeume, Frederik Harwath
It is shown that order-invariance of two-variable first-logic is decidable in the finite. This is an immediate consequence of a decision procedure obtained for the finite satisfiab…
cs.LO2016
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…