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 MyhillNerode and ChomskySchützenberger, replacing trees and words by rewriting diagrams of semiThue 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 MyhillNerode 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 ChomskySchützenberger theorem for PLACIDs. 

