一句话：通过余密度单子与对偶理论，在识别器上添加量词层，证明 Reutenauer 型定理并刻画 profinite 单子。
论文研究正则语言之外、与词逻辑相关的拓扑代数识别技术。它提出在识别器上添加一层各类量词的一般构造，并证明相应的 Reutenauer 型定理。核心工具是余密度单子与对偶理论。作为结果，该构造为有限且交换半环 S 的自由 S-半模单子的 profinite 单子给出新刻画，并推广了作者此前关于 Boolean 空间上 Vietoris 单子是有限幂集函子的余密度单子的认识。这意味着可用统一的范畴论框架处理量词扩展下的语言识别，并连接逻辑、自动机与代数对偶。
This paper contributes to the techniques of topoalgebraic recognition for languages beyond the regular setting as they relate to logic on words. In particular, we provide a general construction on recognisers corresponding to adding one layer of various kinds of quantifiers and prove a related Reutenauer-type theorem. Our main tools are codensity monads and duality theory. Our construction yields, in particular, a new characterisation of the profinite monad of the free S-semimodule monad for finite and commutative semirings S, which generalises our earlier insight that the Vietoris monad on Boolean spaces is the codensity monad of the finite powerset functor.
DOI 原文 ·
@inproceedings{paperbot4151,
title = {Quantifiers on languages and codensity monads},
author = {Mai Gehrke and Daniela Petrisan and Luca Reggio},
booktitle = {LICS},
year = {2017},
doi = {10.1109/lics.2017.8005140}
}