We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier $\exists^{\ge c} y$ that determines whether the number of different $y$ satisfying some formula is at least $c \in \mathbb N$, where $c$ is given in binary. Using a standard quantifier elimination procedure for Presburger arithmetic, the resulting theory is easily seen to be decidable in 4ExpTime. Our main contribution is to develop a novel quantifier-elimination procedure for a more general counting quantifier that decides this theory in 3ExpTime, meaning that it is no harder to decide than standard Presburger arithmetic. As a side result, we obtain an improved quantifier elimination procedure for Presburger arithmetic with counting quantifiers as studied by Schweikardt [ACM Trans. Comput. Log., 6(3), pp. 634-671, 2005], and a 3ExpTime quantifier-elimination procedure for Presburger arithmetic extended with a generalised modulo counting quantifier.
翻译：我们给Presburger算术的扩展提供了一个量化取消程序, 其附加一个未完的阈值计分 $\ expences ⁇ ge c} y$, 确定满足某些公式的不同美元数量是否至少为 $c\ in mathbbn $, 其二进制为 $cbc$。 使用Presburger算术的标准量化取消程序, 由此得出的理论很容易在 4 Exptime 中被看成是可判分的。 我们的主要贡献是开发一个创新的量化取消程序, 用于一个在 3 Exptertime 中决定这一理论的通用量化程序, 意思是, 要决定比标准的Presburger算术更难。 作为副结果, 我们获得了改进的预堡计算的量化程序, 其量化符数由 Schweikart [ACM Trans. comput., Log., 6(3), pp.634-671, 2005] 和 3Exptimetime dictication- Elicationationationationationation prburger算算术的3 程序, 延延展延展延一个通用的全调调调数量化。
相关内容
微信扫码咨询专知VIP会员