First-order logic over words is known to be equivalent to the circuits complexity class AC0 when equipped with arbitrary predicates. In this talk I will present result about the expressivity of first order logic when we restrict the class of predicates. I will focus in particular on the Crane Beach Property. Introduced more than a decade ago, this property is true of a logic if all the expressible languages admitting a neutral letter are regular. Finally I will present it’s closely tied to the counting (in)ability of a logic as an application.

URL:https://www.imj-prg.fr/spip.php?article189 END:VEVENT END:VCALENDAR