Question

Presburger arithmetic是什么意思 《欧路词典》英汉

Answer 1

预膨胀算术
预报算术是自然数的一阶理论，加法，以荣誉MojżeszPresburger为名，他在1929年介绍了它。Presburger算法的签名只包含加法运算和相等，完全省略乘法运算。 公理包括归纳方案。
预饱和算术比Peano算术弱得多，包括加法运算和乘法运算。 与Peano算术不同，Presburger算术是一个可判定的理论。 这意味着，对于Presburger算术语言中的任何句子，可以算法地确定该句子是否可以从Presburger算术的公理证明。 Fischer＆Rabin（1974）所示，这个决策问题的渐近运行时运算复杂度是双指数的。

Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The axioms include a schema of induction.
Presburger arithmetic is much weaker than Peano arithmetic, which includes both addition and multiplication operations. Unlike Peano arithmetic, Presburger arithmetic is a decidable theory. This means it is possible to algorithmically determine, for any sentence in the language of Presburger arithmetic, whether that sentence is provable from the axioms of Presburger arithmetic. The asymptotic running-time computational complexity of this decision problem is doubly exponential, however, as shown by Fischer & Rabin (1974).