论文标题
单调的Monadic二阶逻辑
Monadic Monadic Second Order Logic
论文作者
论文摘要
普通语言对应的主要原因之一和Monadic的二阶逻辑是，在溢流字母到字母同构图像下，普通语言类是关闭的。这种封闭特性适用于有限单词，有限的树，无限的单词，无限树，自由组的元素等结构。这些结构可以使用单子建模。在本文中，我们研究了哪些结构（集合类别中的单调理解）是这样的，以至于普通语言类（即有限代数认可的语言）是在直接图像的直接信函同态同态的直接图像下封闭的。 我们提供了各种条件，以使单元满足这一财产。我们还提供了许多单调的例子，包括无法满足我们足够条件的积极例子，以及封闭特性失败的反例。
One of the main reasons for the correspondence of regular languages and monadic second-order logic is that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for structures such as finite words, finite trees, infinite words, infinite trees, elements of the free group, etc. Such structures can be modelled using monads. In this paper, we study which structures (understood via monads in the category of sets) are such that the class of regular languages (i.e. languages recognized by finite algebras) are closed under direct images of surjective letter-to-letter homomorphisms. We provide diverse sufficient conditions for a monad to satisfy this property. We also present numerous examples of monads, including positive examples that do not satisfy our sufficient conditions, and counterexamples where the closure property fails.
