Séminaires : Séminaire Général de Logique

Equipe(s) : lm,
Responsables :S. Anscombe, A. Khélif, A. Vignati
Email des responsables : sylvy.anscombe@imj-prg.fr, vignati@imj-prg.fr
Salle : 1013
Adresse :Sophie Germain

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion

Orateur(s) Charles Paperman - ,
Titre Some news from the Crane Beach
Horaire15:10 à 16:10
Résume 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.
AdresseSophie Germain