{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T00:13:58Z","timestamp":1710548038830},"reference-count":22,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T00:00:00Z","timestamp":1710460800000},"content-version":"vor","delay-in-days":74,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2023,11,23]]},"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p>There are several well-known ways to compute derivatives of regular expressions due to Brzozowski, Antimirov or Lombardy and Sakarovitch. We propose another one which abstracts the underlying data structures (<jats:italic>e.g<\/jats:italic>. sets or linear combinations) using the notion of monad. As an example of this generalization advantage, we first introduce a new derivation technique based on the graded module monad and then show an application of this technique to generalize the parsing of expressions with capture groups and back references. We also extend operators defining expressions to any <jats:italic>n<\/jats:italic>-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.<\/jats:p>","DOI":"10.1051\/ita\/2023014","type":"journal-article","created":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T08:58:52Z","timestamp":1710493132000},"page":"6","source":"Crossref","is-referenced-by-count":0,"title":["Monadic Expressions and Their Derivatives"],"prefix":"10.1051","volume":"58","author":[{"given":"Samira","family":"Attou","sequence":"first","affiliation":[]},{"given":"Ludovic","family":"Mignot","sequence":"additional","affiliation":[]},{"given":"Cl\u00e9ment","family":"Miklarz","sequence":"additional","affiliation":[]},{"given":"Florent","family":"Nicart","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,3,15]]},"reference":[{"key":"R1","first-page":"3","volume":"34","author":"Kleene","year":"1956","journal-title":"Ann. Math. Stud."},{"key":"R2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"Sch\u00fctzenberger","year":"1961","journal-title":"Inf. Control."},{"key":"R3","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(86)90088-5","volume":"48","author":"Berry","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"R4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/FI-2011-427","volume":"109","author":"Caron","year":"2011","journal-title":"Fundam. Informaticae"},{"key":"R5","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1142\/S0129054104002698","volume":"15","author":"Champarnaud","year":"2004","journal-title":"Int. J. Found. Comput. Sci."},{"key":"R6","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"Brzozowski","year":"1964","journal-title":"J. ACM"},{"key":"R7","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"Antimirov","year":"1996","journal-title":"Theor. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.tcs.2004.10.016","volume":"332","author":"Lombardy","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Sulzmann M. and Zhuo Ming Lu K., POSIX regular expression parsing with derivatives, in FLOPS. Vol. 8475 of Lecture Notes in Computer Science. Springer (2014) 203\u2013220.","DOI":"10.1007\/978-3-319-07151-0_13"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Attou S., Mignot L., Miklarz C. and Nicart F., Monadic expressions and their derivatives, in NCMA. Vol. 367 of EPTCS (2022) 49\u201364.","DOI":"10.4204\/EPTCS.367.4"},{"key":"R11","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/3090064.3090066","volume":"4","author":"Colcombet","year":"2017","journal-title":"SIGLOG News"},{"key":"R12","unstructured":"Mignot L., Une proposition d\u2019implantation des structures d\u2019automates, d\u2019expressions et de leurs algorithmes associes utilisant les cat\u00e9gories enrichies (in French). Habilitation \u00e0 diriger des recherches, Universit\u00e9 de Rouen normandie, D\u00e9cembre 2020. 212 pages."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Jones M.P., Functional programming with overloading and higher-order Polymorphism, in Adv. Func. Prog.. Vol. 925 of LNCS. Springer (1995) 97\u2013136.","DOI":"10.1007\/3-540-59451-5_4"},{"key":"R14","unstructured":"Mac Lane S., Categories for the Working Mathematician, Vol. 5. Springer Science & Business Media (2013)."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Loday J.-L. and Vallette B., Algebraic Operads, Vol. 346. Springer Science & Business Media (2012).","DOI":"10.1007\/978-3-642-30362-3"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"May J.P., The Geometry of Iterated Loop Spaces. Vol. 271 of Lecture Notes in Mathematics. Springer, Berlin, New York (1972).","DOI":"10.1007\/BFb0067491"},{"key":"R17","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1090\/S0002-9939-1965-0177024-4","volume":"16","author":"Kleisli","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Eisenberg R.A. and Weirich S., Dependently typed programming with singletons, in Haskell. ACM (2012) 117\u2013130.","DOI":"10.1145\/2430532.2364522"},{"key":"R19","unstructured":"Mignot L., Monadic derivatives. https:\/\/github.com\/LudovicMignot\/MonadicDerivatives, 2022."},{"key":"R20","unstructured":"IEEE Std 1003.1 \u2014 posix regular expressions. https:\/\/pubs.opengroup.org\/onlinepubs\/9699919799\/basedefs\/VUchap09.html."},{"key":"R21","unstructured":"Pcre \u2014 perl compatible regular expressions. https:\/\/www.pcre.org."},{"key":"R22","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.entcs.2018.11.013","volume":"341","author":"Klin","year":"2018","journal-title":"Electr. Notes Theor. Comput. Sci."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2023014\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T08:59:19Z","timestamp":1710493159000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2023014"}},"subtitle":[],"editor":[{"given":"H.","family":"Bordihn","sequence":"first","affiliation":[]},{"given":"G.","family":"Vaszil","sequence":"additional","affiliation":[]},{"given":"G.","family":"Horv\u00e1th","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":22,"alternative-id":["ita230006"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2023014","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]}}}