Monadic Expressions and their Derivatives

Samira Attou
(LITIS, Université de Rouen Normandie)
Ludovic Mignot
(GR2IF, Université de Rouen Normandie)
Clément Miklarz
(GR2IF, Université de Rouen Normandie)
Florent Nicart
(GR2IF, Université de Rouen Normandie)

We propose another interpretation of well-known derivatives computations from regular expressions, due to Brzozowski, Antimirov or Lombardy and Sakarovitch, in order to abstract the underlying data structures (e.g. sets or linear combinations) using the notion of monad. As an example of this generalization advantage, we introduce a new derivation technique based on the graded module monad.

We also extend operators defining expressions to any n-ary functions over value sets, such as classical operations (like negation or intersection for Boolean weights) or more exotic ones (like algebraic mean for rational weights).

Moreover, we present how to compute a (non-necessarily finite) automaton from such an extended expression, using the Colcombet and Petrisan categorical definition of automata. These category theory concepts allow us to perform this construction in a unified way, whatever the underlying monad.

Finally, to illustrate our work, we present a Haskell implementation of these notions using advanced techniques of functional programming, and we provide a web interface to manipulate concrete examples.

In Henning Bordihn, Géza Horváth and György Vaszil: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), Debrecen, Hungary, August 26-27, 2022, Electronic Proceedings in Theoretical Computer Science 367, pp. 49–64.
Published: 27th August 2022.

ArXived at: https://dx.doi.org/10.4204/EPTCS.367.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org