论文标题
MSO+U逻辑的组成性
Compositionality of the MSO+U Logic
论文作者
论文摘要
我们证明，MSO+U逻辑在以下意义上是组成：MSO+U公式是否仅在树T中保存仅取决于t的t和t根部的t和t子树的MSO+u-u可定义属性，而t则直接始于根部下方。另一种组成性如下：每个自由变量仅在有限的节点集（尤其是其所有自由变量均为一阶）上的每个MSO+U公式都可以重写为MSO公式，该公式可以访问由MSO+U句子可定义的子树属性的MSO公式。
We prove that the MSO+U logic is compositional in the following sense: whether an MSO+U formula holds in a tree T depends only on MSO+U-definable properties of the root of T and of subtrees of T starting directly below the root. Another kind of compositionality follows: every MSO+U formula whose all free variables range only over finite sets of nodes (in particular, whose all free variables are first-order) can be rewritten into an MSO formula having access to properties of subtrees definable by MSO+U sentences (without free variables).
