Mercredi 8 Novembre

Retour à la vue des calendrier
Mercredi 8 Novembre
Heure: 15:00 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Formal language theory beyond trees and forests
Description: Tobias Heindel The talk presents the theorems of Myhill-Nerode and Chomsky-Schützenberger, replacing trees and words by rewriting diagrams of semi-Thue systems, which are the paradigm example of planar acyclic circuit diagrams (PLACIDs)---the “graphical syntax” of monoidal categories. The talk will focus on the proposal of a definition of recognizable language in monoidal categories, namely sets of arrows that coincide with the inverse image of their direct image under a monoidal functor to a finite monoidal category. For the case of PLACIDs, this class of languages is shown to coincide with the languages of automata in the sense of Bossut, under modest assumptions on gates of circuit diagrams; moreover, the usual notion of recognizable tree language is recovered. The talk presents the Myhill-Nerode theorem as a tool for solving Bossut's open problem of automata complementation. The remainder of the talk describes work in progress and future work, in particular the Chomsky-Schützenberger theorem for PLACIDs.