A Crevice on the Crane Beach: Finite-Degree Predicates

Michaël Cadilhac, Charles Paperman

First-order logic (FO) over words is shown to be equiexpressive with FO equipped with a restricted set of numerical predicates, namely the order, a binary predicate MSB${}_0$, and th…