We consider the extension of 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 of 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 theoretic based algorithm.
翻译:我们考虑与本地的Presburger 量化符一起扩展两种可变的保守碎片逻辑。 这些量化符可以表达“ 流入的蓝边缘数加上出红边缘数的两倍” 等属性, 最多是进进绿边缘数的三倍, 并且捕捉了各种描述逻辑, 带有计数, 但是没有恒定的符号。 我们显示这个逻辑的可比较性是 EXP 完整的。 虽然较低约束值已经维持了标准的两种可变的保守碎片逻辑, 但上限值是由新颖的, 但是简单的确定性图形理论的算法建立的 。