## Paper: Successor-Invariance in the Finite (at LICS 2003)

Authors:**Benjamin Rossman**

### Abstract

A first-order sentence \theta of vocabulary \sigma \cup {S} is successor-invariant in the finite if for every finite \sigma-structure M and successor relations S and S on M, (M,S) \models \theta \iff (M, S) \models \theta. In this paper I give an example of a non-first-order definable class of finite structures which is, however, defined by a successor-invariant first-order sentence. This strengthens a corresponding result for order-invariance in the finite, due to Y. Gurevich.

### BibTeX

@InProceedings{Rossman-SuccessorInvariance, author = {Benjamin Rossman}, title = {Successor-Invariance in the Finite}, booktitle = {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003}, year = 2003, editor = {Phokion G. Kolaitis}, month = {June}, pages = {148--}, location = {Ottawa, Canada}, publisher = {IEEE Computer Society Press} }