. "-periodic"@en . . . . . . . "Arithm\u00E9tique de Presburger"@fr . . "in ."@en . . "Muchnik's Theorem"@en . "Arytmetyka Presburgera jest uk\u0142adem aksjomatycznym liczb naturalnych z dodawaniem. Nazywana jest tak\u017Ce arytmetyk\u0105 Peana bez mno\u017Cenia. J\u0119zyk arytmetyki Presburgera zawiera 0 i 1, binarn\u0105 funkcj\u0119 + okre\u015Blan\u0105 jako dodawanie oraz relacj\u0119 r\u00F3wno\u015Bci. G\u0142\u00F3wne aksjomaty arytmetyki: 1. \n* \u00AC(0 = x + 1) 2. \n* x + 1 = y + 1 \u2192 x = y 3. \n* x + 0 = x 4. \n* (x + y) + 1 = x + (y + 1) 5. \n* Niech P(x) b\u0119dzie formu\u0142\u0105 w j\u0119zyku Presburgera i niech dana b\u0119dzie okre\u015Blona zmienna x. Wtedy nast\u0119puj\u0105ca formu\u0142a jest aksjomatem:(P(0) \u2227 \u2200x(P(x) \u2192 P(x + 1))) \u2192 P(y)."@pl . . . . "22906"^^ . . . . . . . . . "\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853(\u82F1: Presburger arithmetic)\u3068\u306F\u52A0\u6CD5\u3092\u542B\u3080\u81EA\u7136\u6570\u306B\u95A2\u3059\u308B\u4E00\u968E\u8FF0\u8A9E\u8AD6\u7406\u4F53\u7CFB\u3067\u3042\u308B\u3002\u306B\u3088\u308A1929\u5E74\u306B\u5C0E\u5165\u3055\u308C\u305F\u3002\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306E\u306B\u306F\u52A0\u6CD5\u3068\u7B49\u53F7\u306E\u307F\u304C\u542B\u307E\u308C\u4E57\u6CD5\u306F\u7701\u304B\u308C\u308B\u3002\u516C\u7406\u306B\u306F\u6570\u5B66\u7684\u5E30\u7D0D\u6CD5\u306E\u516C\u7406\u578B\u3092\u542B\u3080\u3002 \u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306F\u52A0\u6CD5\u3068\u4E57\u6CD5\u4E21\u65B9\u542B\u3080\u30DA\u30A2\u30CE\u7B97\u8853\u3088\u308A\u5F31\u3044\u4F53\u7CFB\u3067\u3042\u308B\u3002\u30DA\u30A2\u30CE\u7B97\u8853\u3068\u306F\u7570\u306A\u308A\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306F\u6C7A\u5B9A\u53EF\u80FD\u3067\u3042\u308B\u3002\u3053\u308C\u306F\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306E\u8A00\u8A9E\u3067\u66F8\u304B\u308C\u305F\u4EFB\u610F\u306E\u9589\u8AD6\u7406\u5F0F\u304C\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306E\u516C\u7406\u3067\u8A3C\u660E\u53EF\u80FD\u304B\u3069\u3046\u304B\u3092\u5224\u5B9A\u3059\u308B\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u5B58\u5728\u3059\u308B\u3053\u3068\u3092\u610F\u5473\u3059\u308B\u3002\u3053\u306E\u6C7A\u5B9A\u554F\u984C\u306E\u8A08\u7B97\u8907\u96D1\u6027\u306F\u6F38\u8FD1\u7684\u306B\u4E8C\u91CD\u6307\u6570\u95A2\u6570\u3067\u3042\u308B\u3053\u3068\u304C\u3067\u793A\u3055\u308C\u3066\u3044\u308B\u3002"@ja . . "En logique math\u00E9matique, l'arithm\u00E9tique de Presburger est la th\u00E9orie du premier ordre des nombres entiers naturels munis de l'addition. Elle a \u00E9t\u00E9 introduite en 1929 par Moj\u017Cesz Presburger. Il s'agit de l'arithm\u00E9tique de Peano sans la multiplication, c\u2019est-\u00E0-dire avec seulement l'addition, en plus du z\u00E9ro et de l'op\u00E9ration successeur. Contrairement \u00E0 l'arithm\u00E9tique de Peano, l'arithm\u00E9tique de Presburger est d\u00E9cidable. Cela signifie qu'il existe un algorithme qui d\u00E9termine si un \u00E9nonc\u00E9 du langage de l'arithm\u00E9tique de Presburger est d\u00E9montrable \u00E0 partir des axiomes de l'arithm\u00E9tique de Presburger."@fr . "Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Moj\u017Cesz 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 algorithm is at least doubly exponential, however, as shown by ."@en . "Presburgerova aritmetika je jeden z axiomatick\u00FDch syst\u00E9m\u016F form\u00E1ln\u00ED teorie aritmetiky. Je podstatn\u011B slab\u0161\u00ED ne\u017E Peanova aritmetika, zejm\u00E9na proto, \u017Ee v jazyce neobsahuje symbol pro n\u00E1soben\u00ED. Pojmenov\u00E1na je po polsk\u00E9m matematikovi , kter\u00FD tuto axiomatiku publikoval v roce 1929."@cs . . . "Arytmetyka Presburgera"@pl . . . . . . . . . . . . . . "Aritmetica di Presburger \u00E8 la teoria del primo ordine dei numeri naturali con l'aggiunta introdotta nel 1929 da Moj\u017Cesz Presburger, da cui prende il nome. La firma dell'aritmetica Presburger contiene solo l'operazione di addizione e l'uguaglianza, omettendo completamente l'operazione di moltiplicazione. Gli assiomi includono uno schema di induzione. L'aritmetica di Presburger \u00E8 meno potente dell'aritmetica di Peano, che include sia le operazioni di addizione che di moltiplicazione. Diversamente dall'aritmetica di Peano, l'aritmetica di Presburger \u00E8 una teoria decidibile."@it . . . . . . "Arytmetyka Presburgera jest uk\u0142adem aksjomatycznym liczb naturalnych z dodawaniem. Nazywana jest tak\u017Ce arytmetyk\u0105 Peana bez mno\u017Cenia. J\u0119zyk arytmetyki Presburgera zawiera 0 i 1, binarn\u0105 funkcj\u0119 + okre\u015Blan\u0105 jako dodawanie oraz relacj\u0119 r\u00F3wno\u015Bci. G\u0142\u00F3wne aksjomaty arytmetyki: 1. \n* \u00AC(0 = x + 1) 2. \n* x + 1 = y + 1 \u2192 x = y 3. \n* x + 0 = x 4. \n* (x + y) + 1 = x + (y + 1) 5. \n* Niech P(x) b\u0119dzie formu\u0142\u0105 w j\u0119zyku Presburgera i niech dana b\u0119dzie okre\u015Blona zmienna x. Wtedy nast\u0119puj\u0105ca formu\u0142a jest aksjomatem:(P(0) \u2227 \u2200x(P(x) \u2192 P(x + 1))) \u2192 P(y). Ostatni aksjomat okre\u015Blany jest schematem indukcji reprezentuj\u0105cym niesko\u0144czon\u0105 liczb\u0119 aksjomat\u00F3w.W roku 1929 Moj\u017Cesz Presburger udowodni\u0142, \u017Ce arytmetyka ta jest rozstrzygalna. Rozstrzygalno\u015B\u0107 (decydowalno\u015B\u0107) problemu matematycznego to nast\u0119puj\u0105ca jego w\u0142a\u015Bciwo\u015B\u0107: zawsze mo\u017Cna okre\u015Bli\u0107 czy dana odpowied\u017A na pytanie stawiane przez problem jest poprawna. Presburger udowodni\u0142 tak\u017Ce, \u017Ce taka arytmetyka jest niesprzeczna i zupe\u0142na (istnieje dow\u00F3d T lub negacji T).Arytmetyka Presburgera przydaje si\u0119 do rozstrzygalno\u015Bci problem\u00F3w, cho\u0107 czas dzia\u0142ania zgrubnego algorytmu jest niejasny. Czas najlepszych algorytm\u00F3w jest potr\u00F3jnie wyk\u0142adniczy. Niech n b\u0119dzie d\u0142ugo\u015Bci\u0105 twierdzenia w arytmetyce Presburgera; Fischer i Rabin (1974) udowodnili, \u017Ce ka\u017Cdy algorytm sprawdzaj\u0105cy prawdziwo\u015B\u0107 twierdzenia musi wykona\u0107 w pesymistycznym przypadku co najmniej krok\u00F3w dla pewnej sta\u0142ej c > 0."@pl . . . "\u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430 \u2014 \u044D\u0442\u043E \u0442\u0435\u043E\u0440\u0438\u044F \u043F\u0435\u0440\u0432\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0430, \u043E\u043F\u0438\u0441\u044B\u0432\u0430\u044E\u0449\u0430\u044F \u043D\u0430\u0442\u0443\u0440\u0430\u043B\u044C\u043D\u044B\u0435 \u0447\u0438\u0441\u043B\u0430 \u0441\u043E \u0441\u043B\u043E\u0436\u0435\u043D\u0438\u0435\u043C, \u043D\u043E \u0432 \u043E\u0442\u043B\u0438\u0447\u0438\u0435 \u043E\u0442 \u0430\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0438 \u041F\u0435\u0430\u043D\u043E, \u0438\u0441\u043A\u043B\u044E\u0447\u0430\u044E\u0449\u0430\u044F \u0432\u044B\u0441\u043A\u0430\u0437\u044B\u0432\u0430\u043D\u0438\u044F \u043E\u0442\u043D\u043E\u0441\u0438\u0442\u0435\u043B\u044C\u043D\u043E \u0443\u043C\u043D\u043E\u0436\u0435\u043D\u0438\u044F. \u041D\u0430\u0437\u0432\u0430\u043D\u0430 \u0432 \u0447\u0435\u0441\u0442\u044C \u043F\u043E\u043B\u044C\u0441\u043A\u043E\u0433\u043E \u043C\u0430\u0442\u0435\u043C\u0430\u0442\u0438\u043A\u0430 \u041C\u043E\u0439\u0436\u0435\u0448\u0430 \u041F\u0440\u0435\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430, \u043A\u043E\u0442\u043E\u0440\u044B\u0439 \u0432 1929 \u0433\u043E\u0434\u0443 \u043F\u0440\u0435\u0434\u043B\u043E\u0436\u0438\u043B \u0441\u043E\u043E\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044E\u0449\u0443\u044E \u0441\u0438\u0441\u0442\u0435\u043C\u0443 \u0430\u043A\u0441\u0438\u043E\u043C \u0432 \u043B\u043E\u0433\u0438\u043A\u0435 \u043F\u0435\u0440\u0432\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0430, \u0430 \u0442\u0430\u043A\u0436\u0435 \u043F\u043E\u043A\u0430\u0437\u0430\u043B \u0435\u0451 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043C\u043E\u0441\u0442\u044C."@ru . . "A Aritm\u00E9tica de Presburger \u00E9 uma teoria de primeira-ordem dos n\u00FAmeros naturais com soma. Tem esse nome em honra de Moj\u017Cesz Presburger, o qual a apresentou em 1929. A assinatura da aritm\u00E9tica de Presburguer cont\u00E9m apenas a opera\u00E7\u00E3o de adi\u00E7\u00E3o e equaliza\u00E7\u00E3o, suprimindo a opera\u00E7\u00E3o de multiplica\u00E7\u00E3o totalmente. Isso inclui o esquema de indu\u00E7\u00E3o."@pt . . "\u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430"@uk . . . . "\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853(\u82F1: Presburger arithmetic)\u3068\u306F\u52A0\u6CD5\u3092\u542B\u3080\u81EA\u7136\u6570\u306B\u95A2\u3059\u308B\u4E00\u968E\u8FF0\u8A9E\u8AD6\u7406\u4F53\u7CFB\u3067\u3042\u308B\u3002\u306B\u3088\u308A1929\u5E74\u306B\u5C0E\u5165\u3055\u308C\u305F\u3002\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306E\u306B\u306F\u52A0\u6CD5\u3068\u7B49\u53F7\u306E\u307F\u304C\u542B\u307E\u308C\u4E57\u6CD5\u306F\u7701\u304B\u308C\u308B\u3002\u516C\u7406\u306B\u306F\u6570\u5B66\u7684\u5E30\u7D0D\u6CD5\u306E\u516C\u7406\u578B\u3092\u542B\u3080\u3002 \u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306F\u52A0\u6CD5\u3068\u4E57\u6CD5\u4E21\u65B9\u542B\u3080\u30DA\u30A2\u30CE\u7B97\u8853\u3088\u308A\u5F31\u3044\u4F53\u7CFB\u3067\u3042\u308B\u3002\u30DA\u30A2\u30CE\u7B97\u8853\u3068\u306F\u7570\u306A\u308A\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306F\u6C7A\u5B9A\u53EF\u80FD\u3067\u3042\u308B\u3002\u3053\u308C\u306F\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306E\u8A00\u8A9E\u3067\u66F8\u304B\u308C\u305F\u4EFB\u610F\u306E\u9589\u8AD6\u7406\u5F0F\u304C\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853\u306E\u516C\u7406\u3067\u8A3C\u660E\u53EF\u80FD\u304B\u3069\u3046\u304B\u3092\u5224\u5B9A\u3059\u308B\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u5B58\u5728\u3059\u308B\u3053\u3068\u3092\u610F\u5473\u3059\u308B\u3002\u3053\u306E\u6C7A\u5B9A\u554F\u984C\u306E\u8A08\u7B97\u8907\u96D1\u6027\u306F\u6F38\u8FD1\u7684\u306B\u4E8C\u91CD\u6307\u6570\u95A2\u6570\u3067\u3042\u308B\u3053\u3068\u304C\u3067\u793A\u3055\u308C\u3066\u3044\u308B\u3002"@ja . . . "Presburgerova aritmetika"@cs . . . . . . . . . . . "\u30D7\u30EC\u30B9\u30D0\u30FC\u30AC\u30FC\u7B97\u8853"@ja . . . . . . "Presburgerova aritmetika je jeden z axiomatick\u00FDch syst\u00E9m\u016F form\u00E1ln\u00ED teorie aritmetiky. Je podstatn\u011B slab\u0161\u00ED ne\u017E Peanova aritmetika, zejm\u00E9na proto, \u017Ee v jazyce neobsahuje symbol pro n\u00E1soben\u00ED. Pojmenov\u00E1na je po polsk\u00E9m matematikovi , kter\u00FD tuto axiomatiku publikoval v roce 1929."@cs . . . "En logique math\u00E9matique, l'arithm\u00E9tique de Presburger est la th\u00E9orie du premier ordre des nombres entiers naturels munis de l'addition. Elle a \u00E9t\u00E9 introduite en 1929 par Moj\u017Cesz Presburger. Il s'agit de l'arithm\u00E9tique de Peano sans la multiplication, c\u2019est-\u00E0-dire avec seulement l'addition, en plus du z\u00E9ro et de l'op\u00E9ration successeur. Contrairement \u00E0 l'arithm\u00E9tique de Peano, l'arithm\u00E9tique de Presburger est d\u00E9cidable. Cela signifie qu'il existe un algorithme qui d\u00E9termine si un \u00E9nonc\u00E9 du langage de l'arithm\u00E9tique de Presburger est d\u00E9montrable \u00E0 partir des axiomes de l'arithm\u00E9tique de Presburger."@fr . . "Presburger-Arithmetik"@de . . "Presburger arithmetic"@en . . . "Aritm\u00E9tica de Presburger"@pt . . . . . . . . . . . . . . . . "Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Moj\u017Cesz 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."@en . "Aritmetica di Presburger \u00E8 la teoria del primo ordine dei numeri naturali con l'aggiunta introdotta nel 1929 da Moj\u017Cesz Presburger, da cui prende il nome. La firma dell'aritmetica Presburger contiene solo l'operazione di addizione e l'uguaglianza, omettendo completamente l'operazione di moltiplicazione. Gli assiomi includono uno schema di induzione. L'aritmetica di Presburger \u00E8 meno potente dell'aritmetica di Peano, che include sia le operazioni di addizione che di moltiplicazione. Diversamente dall'aritmetica di Peano, l'aritmetica di Presburger \u00E8 una teoria decidibile."@it . . . . "\u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430"@ru . . . . . "1112785748"^^ . . . . . . "Aritmetica di Presburger"@it . . "Die Presburger-Arithmetik ist eine in der Pr\u00E4dikatenlogik erster Stufe formulierte mathematische Theorie der nat\u00FCrlichen Zahlen mit Addition.Sie ist benannt nach Moj\u017Cesz Presburger, der sie im Jahre 1929 einf\u00FChrte.Die Signatur der Presburger-Arithmetik enth\u00E4lt nur Addition, nicht jedoch die Multiplikation.Zum Axiomensystem geh\u00F6rt auch ein Axiomenschema der vollst\u00E4ndigen Induktion."@de . . . "23756"^^ . "\u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441c\u0431\u0443\u0440\u0433\u0435\u0440\u0430 \u2014 \u0446\u0435 \u0442\u0435\u043E\u0440\u0456\u044F \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u044F\u043A\u0430 \u043E\u043F\u0438\u0441\u0443\u0454 \u043D\u0430\u0442\u0443\u0440\u0430\u043B\u044C\u043D\u0456 \u0447\u0438\u0441\u043B\u0430 \u0437 \u0434\u043E\u0434\u0430\u0432\u0430\u043D\u043D\u044F\u043C, \u0430\u043B\u0435 \u043D\u0430 \u0432\u0456\u0434\u043C\u0456\u043D\u0443 \u0432\u0456\u0434 \u0430\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0438 \u041F\u0435\u0430\u043D\u043E, \u0432\u0438\u043A\u043B\u044E\u0447\u0430\u0454 \u0432\u0438\u0441\u043B\u043E\u0432\u043B\u044E\u0432\u0430\u043D\u043D\u044F \u0449\u043E\u0434\u043E \u043C\u043D\u043E\u0436\u0435\u043D\u043D\u044F. \u041D\u0430\u0437\u0432\u0430\u043D\u0430 \u0432 \u0447\u0435\u0441\u0442\u044C \u043F\u043E\u043B\u044C\u0441\u044C\u043A\u043E\u0433\u043E \u043C\u0430\u0442\u0435\u043C\u0430\u0442\u0438\u043A\u0430 , \u043A\u043E\u0442\u0440\u0438\u0439 \u0432 1929 \u0440\u043E\u0446\u0456 \u0437\u0430\u043F\u0440\u043E\u043F\u043E\u043D\u0443\u0432\u0430\u0432 \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u043D\u0443 \u0441\u0438\u0441\u0442\u0435\u043C\u0443 \u0430\u043A\u0441\u0456\u043E\u043C \u0432 \u043B\u043E\u0433\u0456\u0446\u0456 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0430 \u0442\u0430\u043A\u043E\u0436 \u043F\u043E\u043A\u0430\u0437\u0430\u0432 \u0457\u0457 . \u0423 \u0446\u044C\u043E\u043C\u0443 \u0440\u043E\u0437\u0434\u0456\u043B\u0456 \u043C\u0438 \u043E\u043F\u0438\u0441\u0443\u0454\u043C\u043E \u0432\u0438\u0440\u0430\u0437\u0438 \u0431\u0435\u0437\u043B\u0456\u0447\u0456 [1] [\u0410\u0440\u0445\u0456\u0432\u043E\u0432\u0430\u043D\u043E 24 \u0432\u0435\u0440\u0435\u0441\u043D\u044F 2015 \u0443 Wayback Machine.] \u0432 . \u0412\u0456\u0434\u0437\u043D\u0430\u0447\u0438\u043C\u043E \u0432\u0456\u0434\u0440\u0430\u0437\u0443 \u0436, \u0449\u043E \u0437 \u0442\u0430\u043A\u043E\u044E \u0441\u0438\u0433\u043D\u0430\u0442\u0443\u0440\u043E\u044E \u0435\u043B\u0456\u043C\u0456\u043D\u0430\u0446\u0456\u044F \u043A\u0432\u0430\u043D\u0442\u043E\u0440\u0456\u0432 \u043D\u0435\u043C\u043E\u0436\u043B\u0438\u0432\u0430. \u0421\u043F\u0440\u0430\u0432\u0434\u0456, \u0444\u043E\u0440\u043C\u0443\u043B\u0430 [2] [\u0410\u0440\u0445\u0456\u0432\u043E\u0432\u0430\u043D\u043E 24 \u0432\u0435\u0440\u0435\u0441\u043D\u044F 2015 \u0443 Wayback Machine.], \u0441\u043F\u0440\u0430\u0432\u0436\u043D\u044F \u0434\u043B\u044F \u043F\u0430\u0440\u043D\u0438\u0445 \u0425 , \u043D\u0435 \u0454 \u0435\u043A\u0432\u0456\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u043E\u044E \u043D\u0456\u044F\u043A\u043E\u0457 \u0431\u0435\u0441\u043A\u0432\u0430\u043D\u0442\u043E\u0440\u043D\u043E\u0439 \u0444\u043E\u0440\u043C\u0443\u043B\u0438. \u0422\u043E\u043C\u0443 \u043D\u0430\u043C \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E, \u043F\u0435\u0440\u0448 \u043D\u0456\u0436 \u043F\u0440\u043E\u0432\u043E\u0434\u0438\u0442\u0438 \u0435\u043B\u0456\u043C\u0456\u043D\u0430\u0446\u0456\u044E \u043A\u0432\u0430\u043D\u0442\u043E\u0440\u0456\u0432, \u0440\u043E\u0437\u0448\u0438\u0440\u0438\u0442\u0438 \u0441\u0438\u0433\u043D\u0430\u0442\u0443\u0440\u0443. \u041D\u0430\u0432\u0435\u0434\u0435\u043D\u0438\u0439 \u043F\u0440\u0438\u043A\u043B\u0430\u0434 \u0444\u043E\u0440\u043C\u0443\u043B\u0438 \u043F\u0456\u0434\u043A\u0430\u0437\u0443\u0454, \u044F\u043A\u0435 \u0440\u043E\u0437\u0448\u0438\u0440\u0435\u043D\u043D\u044F \u043D\u0430\u043C \u043D\u0435\u043E\u0431\u0445\u0456\u0434\u043D\u043E. \u0420\u043E\u0437\u0433\u043B\u044F\u043D\u0435\u043C\u043E \u0440\u0430\u0445\u0443\u043D\u043A\u043E\u0432\u0435 \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u0434\u0432\u043E\u043C\u0456\u0441\u043D\u0438\u0445 \u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442\u043D\u0438\u0445 \u0441\u0438\u043C\u0432\u043E\u043B\u0456\u0432 2\u2033\u2032, 3\u2033\u2032, 4\u2033\u2032,.... \u0421\u0438\u043C\u0432\u043E\u043B \u0421\u2033\u2032 \u0431\u0443\u0434\u0435 \u0456\u043D\u0442\u0435\u0440\u043F\u0440\u0435\u0442\u0443\u0432\u0430\u0442\u0438\u0441\u044F \u044F\u043A \u0440\u0456\u0432\u043D\u0456\u0441\u0442\u044C \u043F\u043E \u043C\u043E\u0434\u0443\u043B\u044E \u0421. \u0406\u043D\u0448\u0438\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u0444\u043E\u0440\u043C\u0443\u043B\u0430 \u0425 \u0431\u0443\u0434\u0435 \u0456\u0441\u0442\u0438\u043D\u043D\u043E\u044E \u0432 \u043D\u0430\u0448\u0456\u0439 \u0456\u043D\u0442\u0435\u0440\u043F\u0440\u0435\u0442\u0430\u0446\u0456\u0457, \u044F\u043A\u0449\u043E \u043F\u043E\u0440\u0456\u0432\u043D\u044F\u0442\u0438 \u0437 \u043F\u043E \u043C\u043E\u0434\u0443\u043B\u044E (\u0437\u0430\u043B\u0438\u0448\u043A\u0438 \u043F\u043E \u043C\u043E\u0434\u0443\u043B\u044E \u0440\u0456\u0432\u043D\u0456; \u043A\u0440\u0430\u0442\u043D\u043E). \u0412\u0430\u0436\u043B\u0438\u0432\u043E \u043C\u0430\u0442\u0438 \u043D\u0430 \u0443\u0432\u0430\u0437\u0456, \u0449\u043E \u0456\u043D\u0434\u0435\u043A\u0441 \u0432 \u043D\u0435 \u0454 \u0437\u043C\u0456\u043D\u043D\u043E\u044E: \u0443 \u043D\u0430\u0441 \u043D\u0435 \u0442\u0440\u0438\u043C\u0456\u0441\u043D\u0438\u0439\u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442, \u0430 \u0440\u0430\u0445\u0443\u043D\u043A\u043E\u0432\u0435 \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u0434\u0432\u043E\u043C\u0456\u0441\u043D\u0438\u0445 \u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442\u0456\u0432. \u0422\u0430\u043A\u0435 \u0440\u043E\u0437\u0448\u0438\u0440\u0435\u043D\u043D\u044F \u043D\u0435 \u043C\u0456\u043D\u044F\u0454 \u043A\u043B\u0430\u0441\u0443 \u0432\u0438\u0440\u0430\u0437\u043D\u0456\u0441\u0442\u044C \u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442\u0456\u0432, \u043E\u0441\u043A\u0456\u043B\u044C\u043A\u0438, \u043D\u0430\u043F\u0440\u0438\u043A\u043B\u0430\u0434, \u043C\u043E\u0436\u043D\u0430 \u0432\u0438\u0440\u0430\u0437\u0438\u0442\u0438 \u044F\u043A [3] [\u0410\u0440\u0445\u0456\u0432\u043E\u0432\u0430\u043D\u043E 24 \u0432\u0435\u0440\u0435\u0441\u043D\u044F 2015 \u0443 Wayback Machine.]. \u0417\u0430\u0442\u0435 \u043F\u0456\u0441\u043B\u044F \u0446\u044C\u043E\u0433\u043E \u0432\u0441\u044F\u043A\u0430 \u0444\u043E\u0440\u043C\u0443\u043B\u0430 \u0435\u043A\u0432\u0456\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u0430 \u0431\u0435\u0441\u043A\u0432\u0430\u043D\u0442\u043E\u0440\u043D\u043E\u0439, \u044F\u043A \u043F\u043E\u043A\u0430\u0437\u0443\u0454 \u043D\u0430\u0441\u0442\u0443\u043F\u043D\u0430 \u0442\u0435\u043E\u0440\u0435\u043C\u0430 (\u0437\u0432\u0430\u043D\u0430 \u0442\u0435\u043E\u0440\u0435\u043C\u043E\u044E \u043F\u0440\u043E \u0435\u043B\u0456\u043C\u0456\u043D\u0430\u0446\u0456\u0457 \u043A\u0432\u0430\u043D\u0442\u043E\u0440\u0456\u0432 \u0432 \u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430)."@uk . . . . . . . . . . "is Presburger-definable if and only if:\n* if then all sections of are Presburger-definable and \n* there exists such that, for every , there exists such that for all with is"@en . . . "A Aritm\u00E9tica de Presburger \u00E9 uma teoria de primeira-ordem dos n\u00FAmeros naturais com soma. Tem esse nome em honra de Moj\u017Cesz Presburger, o qual a apresentou em 1929. A assinatura da aritm\u00E9tica de Presburguer cont\u00E9m apenas a opera\u00E7\u00E3o de adi\u00E7\u00E3o e equaliza\u00E7\u00E3o, suprimindo a opera\u00E7\u00E3o de multiplica\u00E7\u00E3o totalmente. Isso inclui o esquema de indu\u00E7\u00E3o. A Aritm\u00E9tica de Presburger \u00E9 muito mais fraca do que a aritm\u00E9tica de Peano, que inclui tanto a opera\u00E7\u00E3o de adi\u00E7\u00E3o quanto a de multiplica\u00E7\u00E3o. Ao contr\u00E1rio da aritm\u00E9tica de Peano, a aritm\u00E9tica de Presburger \u00E9 uma teoria decid\u00EDvel. Isto significa que \u00E9 poss\u00EDvel efetivamente determinar, por qualquer senten\u00E7a na linguagem da aritm\u00E9tica Presburger, se essa frase \u00E9 dedut\u00EDvel dos axiomas da aritm\u00E9tica de Presburger. O tempo de funcionamento assint\u00F3tico complexidade computacional deste problema de decis\u00E3o \u00E9 duplamente exponencial, como mostrado por Fischer e Rabin (1974)."@pt . "\u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430 \u2014 \u044D\u0442\u043E \u0442\u0435\u043E\u0440\u0438\u044F \u043F\u0435\u0440\u0432\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0430, \u043E\u043F\u0438\u0441\u044B\u0432\u0430\u044E\u0449\u0430\u044F \u043D\u0430\u0442\u0443\u0440\u0430\u043B\u044C\u043D\u044B\u0435 \u0447\u0438\u0441\u043B\u0430 \u0441\u043E \u0441\u043B\u043E\u0436\u0435\u043D\u0438\u0435\u043C, \u043D\u043E \u0432 \u043E\u0442\u043B\u0438\u0447\u0438\u0435 \u043E\u0442 \u0430\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0438 \u041F\u0435\u0430\u043D\u043E, \u0438\u0441\u043A\u043B\u044E\u0447\u0430\u044E\u0449\u0430\u044F \u0432\u044B\u0441\u043A\u0430\u0437\u044B\u0432\u0430\u043D\u0438\u044F \u043E\u0442\u043D\u043E\u0441\u0438\u0442\u0435\u043B\u044C\u043D\u043E \u0443\u043C\u043D\u043E\u0436\u0435\u043D\u0438\u044F. \u041D\u0430\u0437\u0432\u0430\u043D\u0430 \u0432 \u0447\u0435\u0441\u0442\u044C \u043F\u043E\u043B\u044C\u0441\u043A\u043E\u0433\u043E \u043C\u0430\u0442\u0435\u043C\u0430\u0442\u0438\u043A\u0430 \u041C\u043E\u0439\u0436\u0435\u0448\u0430 \u041F\u0440\u0435\u0441\u0431\u0443\u0440\u0433\u0435\u0440\u0430, \u043A\u043E\u0442\u043E\u0440\u044B\u0439 \u0432 1929 \u0433\u043E\u0434\u0443 \u043F\u0440\u0435\u0434\u043B\u043E\u0436\u0438\u043B \u0441\u043E\u043E\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044E\u0449\u0443\u044E \u0441\u0438\u0441\u0442\u0435\u043C\u0443 \u0430\u043A\u0441\u0438\u043E\u043C \u0432 \u043B\u043E\u0433\u0438\u043A\u0435 \u043F\u0435\u0440\u0432\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0430, \u0430 \u0442\u0430\u043A\u0436\u0435 \u043F\u043E\u043A\u0430\u0437\u0430\u043B \u0435\u0451 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043C\u043E\u0441\u0442\u044C."@ru . . . . . . "Die Presburger-Arithmetik ist eine in der Pr\u00E4dikatenlogik erster Stufe formulierte mathematische Theorie der nat\u00FCrlichen Zahlen mit Addition.Sie ist benannt nach Moj\u017Cesz Presburger, der sie im Jahre 1929 einf\u00FChrte.Die Signatur der Presburger-Arithmetik enth\u00E4lt nur Addition, nicht jedoch die Multiplikation.Zum Axiomensystem geh\u00F6rt auch ein Axiomenschema der vollst\u00E4ndigen Induktion. Die Presburger-Arithmetik ist erheblich schw\u00E4cher als die Peano-Arithmetik, in der sowohl Addition als auch Multiplikation formalisiert werden.Im Gegensatz zur Peano-Arithmetik ist die Presburger-Arithmetik eine entscheidbare Theorie, d. h., es l\u00E4sst sich f\u00FCr jede in der Sprache der Presburger-Arithmetik formulierte Aussage effektiv entscheiden, ob sie aus den Axiomen der Theorie beweisbar ist oder nicht.Allerdings ist die asymptotische Laufzeit eines entsprechenden Algorithmus laut einer Arbeit von Fischer und Rabin doppelt exponentiell."@de . . "\u0410\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0430 \u041F\u0440\u0435\u0441c\u0431\u0443\u0440\u0433\u0435\u0440\u0430 \u2014 \u0446\u0435 \u0442\u0435\u043E\u0440\u0456\u044F \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u044F\u043A\u0430 \u043E\u043F\u0438\u0441\u0443\u0454 \u043D\u0430\u0442\u0443\u0440\u0430\u043B\u044C\u043D\u0456 \u0447\u0438\u0441\u043B\u0430 \u0437 \u0434\u043E\u0434\u0430\u0432\u0430\u043D\u043D\u044F\u043C, \u0430\u043B\u0435 \u043D\u0430 \u0432\u0456\u0434\u043C\u0456\u043D\u0443 \u0432\u0456\u0434 \u0430\u0440\u0438\u0444\u043C\u0435\u0442\u0438\u043A\u0438 \u041F\u0435\u0430\u043D\u043E, \u0432\u0438\u043A\u043B\u044E\u0447\u0430\u0454 \u0432\u0438\u0441\u043B\u043E\u0432\u043B\u044E\u0432\u0430\u043D\u043D\u044F \u0449\u043E\u0434\u043E \u043C\u043D\u043E\u0436\u0435\u043D\u043D\u044F. \u041D\u0430\u0437\u0432\u0430\u043D\u0430 \u0432 \u0447\u0435\u0441\u0442\u044C \u043F\u043E\u043B\u044C\u0441\u044C\u043A\u043E\u0433\u043E \u043C\u0430\u0442\u0435\u043C\u0430\u0442\u0438\u043A\u0430 , \u043A\u043E\u0442\u0440\u0438\u0439 \u0432 1929 \u0440\u043E\u0446\u0456 \u0437\u0430\u043F\u0440\u043E\u043F\u043E\u043D\u0443\u0432\u0430\u0432 \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u043D\u0443 \u0441\u0438\u0441\u0442\u0435\u043C\u0443 \u0430\u043A\u0441\u0456\u043E\u043C \u0432 \u043B\u043E\u0433\u0456\u0446\u0456 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0430 \u0442\u0430\u043A\u043E\u0436 \u043F\u043E\u043A\u0430\u0437\u0430\u0432 \u0457\u0457 . \u0412\u0430\u0436\u043B\u0438\u0432\u043E \u043C\u0430\u0442\u0438 \u043D\u0430 \u0443\u0432\u0430\u0437\u0456, \u0449\u043E \u0456\u043D\u0434\u0435\u043A\u0441 \u0432 \u043D\u0435 \u0454 \u0437\u043C\u0456\u043D\u043D\u043E\u044E: \u0443 \u043D\u0430\u0441 \u043D\u0435 \u0442\u0440\u0438\u043C\u0456\u0441\u043D\u0438\u0439\u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442, \u0430 \u0440\u0430\u0445\u0443\u043D\u043A\u043E\u0432\u0435 \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u0434\u0432\u043E\u043C\u0456\u0441\u043D\u0438\u0445 \u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442\u0456\u0432."@uk . . .