Julien Grange

Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)

We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of a successor relation on the vertices of the graph is allowed, as long as the validity of formulas is independent on the choice of a particular successor. We show tha…