Liens avec la logique temporelle

Un premier travail (en cours de rédaction) concerne les langages
rationnels de mots indexés par des ordres linéaires. Julien Cristau fait le
lien entre les langages reconnus par des transducteurs finis sur ces
mots et les langages exprimés par des formules de LTL.   

Jeux de longueur ordinale

Plus récemment, Julien Cristau s'est intéressé aux jeux
d'accessibilité de longueur ordinale, en collaboration avec Florian
Horn.  Ils ont prouvé que les jeux de longueur inférieure à
$\omega^\omega$ sont déterminés et que le problème consistant à
trouver le vainqueur est PSPACE-complet. Leurs résultats ont
été soumis à SOFSEM 2008.