Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Matematicheskie Zametki, 2003, Volume 74, Issue 1, Pages 69–75
DOI: https://doi.org/10.4213/mzm246
(Mi mzm246)
 

This article is cited in 2 scientific papers (total in 2 papers)

Polynomial Computability of Certain Rudimentary Predicates

S. S. Marchenkov

M. V. Lomonosov Moscow State University
Full-text PDF (161 kB) Citations (2)
References:
Abstract: The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form $\exists\forall$. Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.
Received: 17.01.2001
English version:
Mathematical Notes, 2003, Volume 74, Issue 1, Pages 64–69
DOI: https://doi.org/10.1023/A:1025067132637
Bibliographic databases:
UDC: 519.712
Language: Russian
Citation: S. S. Marchenkov, “Polynomial Computability of Certain Rudimentary Predicates”, Mat. Zametki, 74:1 (2003), 69–75; Math. Notes, 74:1 (2003), 64–69
Citation in format AMSBIB
\Bibitem{Mar03}
\by S.~S.~Marchenkov
\paper Polynomial Computability of Certain Rudimentary Predicates
\jour Mat. Zametki
\yr 2003
\vol 74
\issue 1
\pages 69--75
\mathnet{http://mi.mathnet.ru/mzm246}
\crossref{https://doi.org/10.4213/mzm246}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2010678}
\zmath{https://zbmath.org/?q=an:1077.03023}
\transl
\jour Math. Notes
\yr 2003
\vol 74
\issue 1
\pages 64--69
\crossref{https://doi.org/10.1023/A:1025067132637}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000185172900008}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0345863693}
Linking options:
  • https://www.mathnet.ru/eng/mzm246
  • https://doi.org/10.4213/mzm246
  • https://www.mathnet.ru/eng/mzm/v74/i1/p69
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024