Varieties of Languages in a Category
Varieties of Languages in a Category
复制标题
DOI：
10.1109/lics.2015.46
复制
发表时间：
2015-01
期刊：
影响因子：
--
通讯作者：
J. Adámek;R. Myers;Henning Urbat;Stefan Milius
中科院分区：
文献类型：
--
作者：
J. Adámek;R. Myers;Henning Urbat;Stefan Milius
Eilenberg的变分定理是代数自动机理论的核心，它建立了一元群的伪变分和语言的变分之间的双射对应关系。本文将这一结果推广到一个抽象的代数范畴对上：我们在范畴C中引入语言的变种，并证明它们对应于闭一元范畴D中一元的伪变种，只要C和D在有限对象水平上是对偶的。通过适当地选择这些类别，我们的结果统一地涵盖了Eilenberg定理和三个变体，分别是由于Pin， Polák和Reutenauer，并产生了新的Eilenberg型对应。
Eilenberg's variety theorem, a centerpiece of algebraic automata theory, establishes a bijective correspondence between varieties of languages and pseudovarieties of monoids. In the present paper this result is generalized to an abstract pair of algebraic categories: we introduce varieties of languages in a category C, and prove that they correspond to pseudovarieties of monoids in a closed monoidal category D, provided that C and D are dual on the level of finite objects. By suitable choices of these categories our result uniformly covers Eilenberg's theorem and three variants due to Pin, Polák and Reutenauer, respectively, and yields new Eilenberg-type correspondences.