Operads, quasiorders, and regular languages

Samuele Giraudo (1) , Jean-Gabriel Luque (2) , Ludovic Mignot (2) , Florent Nicart (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 CA - LITIS - Equipe Combinatoire et algorithmes

We generalize the construction of multi-tildes in the aim to provide double multi-tilde operators for regular languages. We show that the underlying algebraic structure involves the action of some operads. An operad is an algebraic structure that mimics the composition of the functions. The involved operads are described in terms of combinatorial objects. These operads are obtained from more primitive objects, namely precompositions, whose algebraic counterparts are investigated. One of these operads acts faithfully on languages in the sense that two different operators act in two different ways.

Domaines: Théorie et langage formel [cs.FL]; Combinatoire [math.CO]

Samuele Giraudo, Jean-Gabriel Luque, Ludovic Mignot, Florent Nicart. Operads, quasiorders, and regular languages. Advances in Applied Mathematics, 2016, 75, pp.56-93. ⟨10.1016/j.aam.2016.01.002⟩. ⟨hal-01260550⟩