论文标题
伪数芬太尼单词的二阶理论
The pseudofinite monadic second order theory of words
论文作者
论文摘要
我们分析了固定有限字母上单词的假芬太尼单一二阶理论。特别是，我们介绍了该理论的公理化，以一级的一阶框架工作。该分析取决于单词的串联与Monadic二阶逻辑很好地相互作用。更准确地说，给出一个签名，在每个自然数k下，（最多最多k的量子）对（monadic二阶版本的）单词的等效性（最多k的公式）是串联的一致性。我们使用分析为连接可识别语言的定理提供了替代证明，并且由于Gehrke，Grigorieff和Pin，通过扩展的石材双重性通过延长的石材双重性提供了有限生成的免费profinite单体。
We analyse the pseudofinite monadic second order theory of words over a fixed finite alphabet. In particular we present an axiomatisation of this theory, working in a one-sorted first order framework. The analysis hinges on the fact that concatenation of words interacts nicely with monadic second order logic. More precisely, give a signature under which for each natural number k, equivalence of (monadic second order versions of) words with respect to formulas of quantifier depth at most k is a congruence for concatenation. We use our analysis to present an alternative proof of a theorem connecting recognisable languages and finitely generated free profinite monoids via extended Stone duality, due to Gehrke, Grigorieff, and Pin.
