论文标题
使用丰富类别的自动机和表达结构以及相关算法的统一实现
A unified implementation of automata and expression structures, and of the associated algorithms using enriched categories
论文作者
论文摘要
在本文档中，我们通过Haskell实现提出了一个对正则表达式概念的概括的描述，使我们能够基于一个富集的类别理论工具将（树或单词）自动机构造的定义和方法分组（树或单词）自动机构建体。我们首先回想起从表达式到自动机的几种转换方法，从而启发了单词和树木案例之间的相似之处。然后，我们使用功能编程的高级概念，同时构建了丰富的类别理论和相关自动组的概念的同时实施，同时构建了实施了丰富的类别概念和相关的自动组，我们将对应用于自动机和表达式实施的丰富类别理论的力量进行了原始研究。更确切地说，Haskell实施和通用自动机结构的代数定义基于以下思想： - 可以在Haskell中实施丰富的类别，丰富的功能子，丰富的单子等； - 类型级别的编程可用于正确编码函数arity； - 单型（单词结构）和oprads（树结构）可以编码为单体对象； - 树和单词自动机可以通过丰富的类别以相同的代数结构来表示。 这种概括导致了令人惊讶的言论。例如，可以将某些经典算法（确定，完成，从确定性自动机交替的转换）仅在一个函数中重组。然后，我们将根据单张量张量产物的概念来定义广义表达式的概念。 Haskell资源可在以下网址提供：http：//ludovicmignot.free.fr/hdr/src-hdr.zip
In this document, we propose a description, via a Haskell implementation, of a generalization of the notion of regular expression allowing us to group the definitions and the methods of (tree or word) automata constructions over one generic structure, based on enriched category theory tools. We first recall several methods of conversion from expressions to automata, enlightening the similarities between the words and trees cases. We then produce an original study of the power of enriched category theory applied 1) to automata and expressions implementation, and 2) to the study of associated algorithms, using advanced concepts of functional programming, while simultaneously constructing a Haskell implementation of notions of enriched category theory and associated automata. More precisely, the Haskell implementation and the algebraic definition of the generic automaton structure are based on the following ideas: - enriched categories, enriched functors, enriched monads, etc. can be implemented in Haskell; - Type level programming can be used to properly encode function arity; - monoids (word structure) and operads (tree structure) can be encoded as monoid objects; - tree and word automata can be represented by the same algebraic structure, via enriched categories. This generalization leads to surprising remarks. As an example, some classical algorithms (determinization, completion, conversion from alternating to deterministic automaton) can be regrouped in only one function. We will then define a notion of generalized expressions based on the notion of monoidal tensor product. Haskell sources are available at: http://ludovicmignot.free.fr/HDR/src-HDR.zip
