A crevice on the Crane Beach: finite-degree predicates
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 MSB0, and the finite-degree predicates: FO[ARB] = FO[≤, MSB0, FIN]. The Crane Beach Property (CBP), introduced more than a decade ago,...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
IEEE
2017
|