Finite-Degree Predicates and Two-Variable First-Order Logic

In this talk, I will resent two new results about the expressivity of two-variable first-order logic over finite words equipped with arbitrary numerical predicates. This fragment of logic is equivalent to languages recognized by linear size and constant depth boolean circuit. I will focus on the so-called Crane Beach conjecture for FO^2. Proving the Crane Beach conjecture in this context would improve on a known lower bound for addition, stating that the function of addition is not computable by circuits of constant depth with a linear number of wires. First we will explain how languages with a neutral letter definable in two-variable logic with arbitrary numerical predicates can be defined using only the linear order and the following predicates: •The class F of finite-degree predicates, that is, binary predicates that are relations over integers and such that each vertex of their underlying infinite directed graph has a finite degree. •A predicate called MSB0, true of positions x and y if the binary decomposition of y is obtained by zeroing the most significant bit of x. Then, a Crane Beach result will be presented for the restricted signature containing < and F predicates. Thus, this a result which is one predicate shy from showing the Crane Beach conjecture for FO^2.

Authors

• Charles Paperman

Keywords

No keywords are indexed for this paper.