Email this article Logical language of description of polynomial computing
- Authors: Goncharov S.S.1, Sviridenko D.I.1
-
Affiliations:
- Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
- Issue: Vol 485, No 1 (2019)
- Pages: 11-14
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/12802
- DOI: https://doi.org/10.31857/S0869-5652485111-14
- ID: 12802
Cite item
Full Text
Abstract
An expansion of the term concept and, accordingly, the formula due to new operators were constructed. These extensions of the language preserve the expressiveness of S-formulas, and at the level of D0-formulas and terms, they ensure the polynomiality of algorithms for calculating the value of a term and the truth of a D0-formula.
About the authors
S. S. Goncharov
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Author for correspondence.
Email: s.s.goncharov@math.nsc.ru
Academician of the RAS
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090D. I. Sviridenko
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Email: dsviridenko47@gmail.com
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090
References
- Гончаров С.С., Свириденко Д.И. // Вычисл. системы.1985. В. 107. С. 3–29.
- Goncharov S.S., Sviridenko D.I. // Lect. Notes in Com- put. Sci. 1986. V. 215. P. 169–179.
- Ershov Yu.L., Goncharov S.S., Sviridenko D.I. Inform. proces., Proc. IFIP 10-th World Comput. Congr. Dub- lin, 1986. V. 10. P. 1113–1120.
- Гончаров С.С., Свириденко Д.И. // ДАН. 1986. Т. 289. № 6. С. 1324–1328.
- Ershov Yu.L., Goncharov S.S., Sviridenko D.I. // Lect.Notes in Comput. Sci. 1987. V. 278. P. 116–122.
- Ершов Ю. Л. // ДАН. 1983. Т. 270. № 4. С. 786–788.
- Ершов Ю. Л. // ДАН. 1983. Т. 273. № 5. С. 1045–1048.
- Ershov Yu.L. Definability and Computability. Siberian School of Algebra and Logic. N.Y.: Consultants Bureau, 1996. 264 p.
- Barwise J. Admissible Sets and Structures. Berlin: Springer, 1975. 394 p.
- Arora S., Barak B. Computational Complexity. A Mod- ern Approach. Cambridge: Cambridge Univ. Press, 2009. 605 p.
- Papadimitriou Ch. Computational Complexity. Reding: Addison-Wesley, 1994. 523 p.
- Ospichev S. S., Ponomarev D. // Siberian Electronic Math. Reps. 2018. V. 15. P. 987–995.
- Гончаров С.С. // Сиб. мат. журн. 2017. Т. 58. № 5. С. 1026–1034.
Supplementary files
