Order Invariance on Decomposable Structures
Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe · 2016
Order-invariant formulas access an ordering on a structure's universe, but the model relation is independent of the used ordering. They are frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. We study the expressive power of order-invariant monadic second-order (MSO) and first-order (FO) logic on restricted classes of structures that admit certain forms of tree decompositions (not necessarily of bounded width).