# IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

# Logic in Computer Science (LICS 2003)

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

Winner of the Kleene Award in 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 Symposium on Logic in Computer Science (LICS 2003)},
year =	 {2003},
month =	 {June},
pages =      {148--157},