一句话：证明带局部 Presburger 量词的二变量守卫片段可满足性是 EXP 完全，并给出简单确定性图算法。
本文研究二变量守卫片段逻辑（GF2）的扩展，引入局部 Presburger 量词。这类量词可表达如“入蓝边数加两倍出红边数不超过三倍入绿边数”等线性计数约束，并能刻画多种带计数的描述逻辑，但不含常量符号。作者证明该逻辑的可满足性问题是 EXP 完全的：下界继承自标准二变量守卫片段逻辑，上界则通过一个新颖而简单的确定性图基算法建立。该方法直接处理局部 Presburger 约束，避免了复杂的自动机或展开论证，从而精确刻画了该计数扩展的复杂度边界。
We consider the extension of the two-variable guarded fragment logic with local Presburger quantifiers. These are quantifiers that can express properties such as "the number of incoming blue edges plus twice the number of outgoing red edges is at most three times the number of incoming green edges" and captures various description logics with counting, but without constant symbols. We show that the satisfiability problem for this logic is EXP-complete. While the lower bound already holds for the standard two-variable guarded fragment logic, the upper bound is established by a novel, yet simple deterministic graph-based algorithm.
@article{paperbot2732,
title = {On two-variable guarded fragment logic with expressive local Presburger constraints},
author = {Chia-Hsuan Lu and Tony Tan},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 3},
year = {2024},
doi = {10.46298/lmcs-20(3:16)2024}
}