Evènement pour le groupe Graphes et Logique

Date 2011-02-15  11:00-12:00
TitreExpressive Power of FO2 on finite trees 
RésuméThis work belongs to a general effort for understanding the expressive power of first-order logic on finite trees. In particular we seek to obtain decidable characterizations. Meaning a decision procedure for the following problem: given a regular tree language is it definable in FO? This particular work concerns the study of a fragment of FO: First-Order Logic using only two variables (FO2). I will present various results concerning decidable characterizations for FO2. This is joint work with Luc Segoufin  
Lieusalle 76 
OrateurThomas Place 
UrlLSV, ENS Cachan 

Aucun document lié à cet événement.

Retour à l'index