Hanf normal form for first-order logic with unary counting quantifiers
Hanf normal form for first-order logic with unary counting quantifiers
复制标题
具有一元计数量词的一阶逻辑的 Hanf 范式
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Nicole Schweikardt
中科院分区：
文献类型：
--
作者：
Lucas Heimberg;D. Kuske;Nicole Schweikardt
我们通过集合$ {\ Mathbf {q}} \ subseteq \ Mathcal {p}（\ Mathbb {n}）$的一阶逻辑的扩展（Q）研究了HANF的正常形式公式为HANF普通形式，如果是公式的布尔$ \ xi（\ bar x）$的布尔组合，描述了其自由变量$ \ bar x $的同构类型的同构类型，则表格的语句” ψ（y）属于（q+k）“这里q∈Q，k∈ℕ，ψ描述了其唯一的自由变量y的局部邻域的同构类型。我们表明，来自fo（q）的公式可以转换为HANF中的公式当所有计数量化器出现在公式中时，在所有程度上的结构上等效的正常形式最终才能进行周期性。尤其是，这产生了Nurmonen对Hanf定理的算法版本，用于使用模量计数的量词作为直接的结果。使用Modulo-Counting量词是固定参数可进行的。
We study the existence of Hanf normal forms for extensions FO(Q) of first-order logic by sets ${\mathbf{Q}} \subseteq \mathcal{P}(\mathbb{N})$ of unary counting quantifiers. A formula is in Hanf normal form if it is a Boolean combination of formulas $\xi (\bar x)$ describing the isomorphism type of a local neighbourhood around its free variables $\bar x$ and statements of the form "the number of witnesses y of ψ(y) belongs to (Q+k)" here Q ∈ Q, k ∈ ℕ, and ψ describes the isomorphism type of a local neighbourhood around its unique free variable y.We show that a formula from FO(Q) can be transformed into a formula in Hanf normal form that is equivalent on all structures of degree ⩽ d if, and only if, all counting quantifiers occurring in the formula are ultimately periodic. This transformation can be carried out in worst-case optimal 3-fold exponential time.In particular, this yields an algorithmic version of Nurmonen’s extension of Hanf’s theorem for first-order logic with modulo-counting quantifiers. As an immediate consequence, we obtain that on finite structures of degree ⩽ d, model checking of first-order logic with modulo-counting quantifiers is fixed-parameter tractable.