Frédéric Peschanski (LIP6 / UPMC Sorbonne Université)

La sémantique étudie les relations entre les objets (souvent des arbres) syntaxiques et leur interprétation. En théorie de la concurrence, les objets syntaxiques - généralement appelés des processus - peuvent être interprétés par des structures arborescentes : les computation trees. Ces objets ont été très peu étudiés d’un point de vue combinatoire.

Dans le cadre du projet Alpaca (puis Parco) nous avons revisité certains concepts fondamentaux de la concurrence et nous les avons relié à des classes combinatoires plus ou moins connues. Dans cet exposé, je présenterais la notion de parallélisme vue comme un étiquetage croissant (strict) des arbres syntaxiques. J’introduirais ensuite le principe du non-déterminisme interprété comme un étiquetage partiellement - ou sélectivement - croissant. Finalement, j’aborderais notre étude en cours concernant le phénomène de synchronisation, qui relâche la contrainte d’ordre strict dans l’étiquetage.