Successor-Invariant First-Order Logic on Classes of Bounded Degree

09/24/2020
by   Julien Grange, et al.
0

We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of an additional successor relation on the structure is allowed, as long as the validity of formulas is independent on the choice of a particular successor. We show that when the degree is bounded, successor-invariant first-order logic is no more expressive than first-order logic.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset