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.
known for
Wikipage redirect
Automated reasoningAutomated theorem provingBüchi arithmeticComplete theoryComputational complexity theoryConsistencyDecidability (logic)Double exponential functionEntscheidungsproblemGeneralized arithmetic progressionGeneric-case complexityGödel's incompleteness theoremsInfinite chessList of computability and complexity topicsList of first-order theoriesList of mathematical logic topicsMojżesz PresburgerNP-completenessP versus NP problemPeano axiomsPresberger arithmeticPresburger ArithmeticPresburger AwardPressburgerPressburger arithmeticQuantifier eliminationRecursive languageRegular numerical predicateRobinson arithmeticSatisfiability modulo theoriesSecond-order arithmeticSkolem arithmeticStable theoryThoralf SkolemTime complexityTimeline of mathematical logicType systemWilliam Pugh (computer scientist)Z-group
Link from a Wikipage to another Wikipage
known for
primaryTopic
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.
has abstract
Aritmetica di Presburger è la ...... urger è una teoria decidibile.
@it
Aritmética de Presburger é a t ...... do por Fischer e Rabin (1974).
@pt
Arytmetyka Presburgera jest uk ...... roków dla pewnej stałej c > 0.
@pl
Die Presburger-Arithmetik ist ...... nd Rabin doppelt exponentiell.
@de
En logique mathématique, l'ari ...... l'arithmétique de Presburger.
@fr
Presburger arithmetic is the f ...... ential, however, as shown by .
@en
Presburgerova aritmetika je je ...... matiku publikoval v roce 1929.
@cs
Арифметика Пресcбургера — це т ...... ів в Арифметика Прессбургера).
@uk
Арифметика Пресбургера — это т ...... также показал её разрешимость.
@ru
プレスバーガー算術(英: Presburger arithm ...... 計算複雑性は漸近的に二重指数関数であることがで示されている。
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
996,830,246
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
hypernym
type
comment
Aritmetica di Presburger è la ...... urger è una teoria decidibile.
@it
Aritmética de Presburger é a t ...... o inclui o esquema de indução.
@pt
Arytmetyka Presburgera jest uk ...... ∧ ∀x(P(x) → P(x + 1))) → P(y).
@pl
Die Presburger-Arithmetik ist ...... a der vollständigen Induktion.
@de
En logique mathématique, l'ari ...... l'arithmétique de Presburger.
@fr
Presburger arithmetic is the f ...... include a schema of induction.
@en
Presburgerova aritmetika je je ...... matiku publikoval v roce 1929.
@cs
Арифметика Пресcбургера — це т ...... імейство двомісних предикатів.
@uk
Арифметика Пресбургера — это т ...... также показал её разрешимость.
@ru
プレスバーガー算術(英: Presburger arithm ...... 計算複雑性は漸近的に二重指数関数であることがで示されている。
@ja
label
Arithmétique de Presburger
@fr
Aritmetica di Presburger
@it
Aritmética de Presburger
@pt
Arytmetyka Presburgera
@pl
Presburger arithmetic
@en
Presburger-Arithmetik
@de
Presburgerova aritmetika
@cs
Арифметика Пресбургера
@ru
Арифметика Пресбургера
@uk
プレスバーガー算術
@ja