Definability of linear equation systems over groups and rings
Definability of linear equation systems over groups and rings
复制标题
群和环上线性方程组的可定义性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Wied Pakusa
中科院分区：
文献类型：
--
作者：
A. Dawar;E. Grädel;Bjarki Holm;Eryk Kopczynski;Wied Pakusa
基于对时间逻辑的探索，以及最近关于线性代数问题的描述复杂性是这个问题的一个重要方面的见解，我们从逻辑(互)可定义性的角度研究了有限群和环上的线性方程组的可解性。我们考虑的所有问题在多项式时间内都是可判定的，但不能用带计数的定点逻辑来表示。它们还为多项式时间与秩逻辑的分离提供了自然的候选者，秩逻辑通过确定可定义矩阵的秩来扩展不动点逻辑，并且对于域上的可解性问题是足够的。
基于有限环的结构理论，我们建立了各种可解性问题之间的逻辑归约。我们的结果表明，将带计数的不动点逻辑从ptime中分离出来的线性方程组的所有可解性问题都可以归结为交换环上的可解性。进一步，我们证明了环上降为可解的查询类的闭包性质。作为应用，这些闭包性质为扩展了可解性算子的逻辑提供了范式。
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are decidable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields.
Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that all solvability problems for linear equation systems that separate fixed-point logic with counting from PTIME can be reduced to solvability over commutative rings. Further, we prove closure properties for classes of queries that reduce to solvability over rings. As an application, these closure properties provide normal forms for logics extended with solvability operators.
带计数的定点逻辑中的最大匹配和线性规划
DOI：
10.1109/lics.2013.23
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Anderson M
通讯作者：
Anderson M