论文标题
在有限扩展类中模拟计数的一阶逻辑
Modulo-Counting First-Order Logic on Bounded Expansion Classes
论文作者
论文摘要
我们证明，在有限的扩展类别上，每个具有模量计数的一阶公式在线性时间可计算的单层扩展中与存在的一阶公式相等。结果，我们在有限的扩展类别上得出，具有模量计数的一阶转导具有与存在的一阶转导能力相同的编码功率。同样，可以在有限的扩展类别上的线性时间内实现Modulo计数的一阶模型检查和计算可定义的一阶逻辑的集合大小的计算。作为一个应用程序，我们证明一类具有结构界限的扩展，并且仅当它是一个有界扩展类中图形的界面深度较小者的类别。我们还展示了我们的结果如何用于在有限场上的有限扩展矩阵上实现快速矩阵演算。
We prove that, on bounded expansion classes, every first-order formula with modulo counting is equivalent, in a linear-time computable monadic expansion, to an existential first-order formula. As a consequence, we derive, on bounded expansion classes, that first-order transductions with modulo counting have the same encoding power as existential first-order transductions. Also, modulo-counting first-order model checking and computation of the size of sets definable in modulo-counting first-order logic can be achieved in linear time on bounded expansion classes. As an application, we prove that a class has structurally bounded expansion if and only if it is a class of bounded depth vertex-minors of graphs in a bounded expansion class. We also show how our results can be used to implement fast matrix calculus on bounded expansion matrices over a finite field.
