First-order expressibility of languages with neutral letters or: The Crane Beach conjecture

摘要

A language L over an alphabet A is said to have a neutral letter if there is a letter e∈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 N of numerical predicates. Named after the location of its first, flawed, proof this conjecture is called the Crane Beach conjecture (CBC, for short). The CBC is closely related to uniformity conditions in circuit complexity theory and to collapse results in database theory.We investigate the CBC in detail, showing that it fails for N={+,×}, or, possibly stronger, for any set N that allows counting up to the m times iterated logarithm, for any constant m. On the positive side, we prove the conjecture for the case of all monadic numerical predicates, for the addition predicate +, for the fragment BC(Σ1) of first-order logic, for regular languages, and for languages over a binary alphabet. We explain the precise relation between the CBC and so-called natural-generic collapse results in database theory. Furthermore, we introduce a framework that gives better understanding of what exactly may cause a failure of the conjecture.