# ACM/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 2001)

## Paper: The Crane Beach Conjecture (at LICS 2001)

Authors: David A. Mix Barrington Neil Immerman Clemens Lautemann Nicole Schweikardt Denis Thérien

### Abstract

A language L over an alphabet A is said to have a neutral letter if there is a letter e\in A such that inserting or deleting e's from any word in A* does not change its membership (or non-membership) in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set {\cal N} of numerical predicates. We investigate this conjecture in detail, showing that it fails already for {\cal N} =\{+; \ast\}, or, possibly stronger, for any set {\cal N} that allows counting up to the m times iterated logarithm, lg(m), for any constant m. On the positive side, we prove the conjecture for the case of all monadic numerical predicates, for {\cal N} = \{+\}, for the fragment BC(S1) of first-order logic, and for binary alphabets.

### BibTeX

  @InProceedings{Thrien-TheCraneBeachConjec,
author = 	 {David A. Mix Barrington and Neil Immerman and Clemens Lautemann and Nicole Schweikardt and Denis Thérien},
title = 	 {The Crane Beach Conjecture},
booktitle =  {Proceedings of the Sixteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2001)},
year =	 {2001},
month =	 {June},
pages =      {187--196},
location =   {Boston, MA, USA},
publisher =	 {IEEE Computer Society Press}
}