D.M. Barrington, N. Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Thérien ``First-Order Expressibility of Languages with Neutral Letters Or: The Crane Beach Conjecture,'' JCSS 70(2) (2005), 101-127. A preliminary version appeared in, LICS '01, 187-196.

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 A of numerical predicates. We investigate this conjecture in detail, showing that it fails already for A={+,x}, or, possibly stronger, for any set A 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 A={+}, for the fragment BC(Sigma1) of first-order logic, and for binary alphabets.

Recent Publications of Neil Immerman