Algebra i logika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Algebra Logika:
Year:
Volume:
Issue:
Page:
Find




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

Algebra i logika, 2017, Volume 56, Number 6, Pages 651–670
DOI: https://doi.org/10.17377/alglog.2017.56.601 (Mi al822) 		 
This article is cited in 12 scientific papers (total in 12 papers)

Structures computable in polynomial time. II

P. E. Alaevab

a Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090 Russia
Full-text PDF (223 kB) Citations (12)
References:
PDF
HTML
DOI: https://doi.org/10.17377/alglog.2017.56.601
Abstract: We consider a new approach to investigating categoricity of structures computable in polynomial time. The approach is based on studying polynomially computable stable relations. It is shown that this categoricity is equivalent to the usual computable categoricity for computable Boolean algebras with computable set of atoms, and for computable linear orderings with computable set of adjacent pairs. Examples are constructed which show that this does not always hold. We establish a connection between dimensions based on computable and polynomially computable stable relations.
Keywords: computable stable relations, polynomially computable stable relations, categoricity, computable categoricity.
Funding agency Grant number
Russian Foundation for Basic Research 17-01-00247
Supported by RFBR, project No. 17-01-00247.
Received: 24.02.2016
Revised: 29.11.2017
English version:
Algebra and Logic, 2018, Volume 56, Issue 6, Pages 429–442
DOI: https://doi.org/10.1007/s10469-018-9465-x
Bibliographic databases:
Document Type: Article
UDC: 510.5+512+510.6
Language: Russian
Citation: P. E. Alaev, “Structures computable in polynomial time. II”, Algebra Logika, 56:6 (2017), 651–670; Algebra and Logic, 56:6 (2018), 429–442
Citation in format AMSBIB
\Bibitem{Ala17}
\by P.~E.~Alaev
\paper Structures computable in polynomial time.~II
\jour Algebra Logika
\yr 2017
\vol 56
\issue 6
\pages 651--670
\mathnet{http://mi.mathnet.ru/al822}
\crossref{https://doi.org/10.17377/alglog.2017.56.601}
\transl
\jour Algebra and Logic
\yr 2018
\vol 56
\issue 6
\pages 429--442
\crossref{https://doi.org/10.1007/s10469-018-9465-x}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000426390500001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042406953}
Linking options:
  • https://www.mathnet.ru/eng/al822
  • https://www.mathnet.ru/eng/al/v56/i6/p651
    Cycle of papers
    This publication is cited in the following 12 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Алгебра и логика Algebra and Logic
    Statistics & downloads:
    Abstract page:269
    Full-text PDF :51
    References:54
    First page:19
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024