Diskretnaya Matematika
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



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






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


Diskretnaya Matematika, 2015, Volume 27, Issue 3, Pages 44–55
DOI: https://doi.org/10.4213/dm1334
(Mi dm1334)
 

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

On elementary word functions obtained by bounded prefix concatenation

Sergey S. Marchenkov

Moscow State University
Full-text PDF (426 kB) Citations (6)
References:
Abstract: The operation of bounded prefix concatenation (BPC) is introduced on the set of word functions in the alphabet $\{1,2\}$. The class BPC of polynomially computable functions is defined on the basis of this operation and the superposition operation. The class BPC is shown to contain a number of word functions and to be closed with respect to certain known operations. A certain type of two-tape nonerasing Turing machines is introduced, functions from the class BPC are shown to be computable on machines of this type in polynomial time.
Keywords: bounded prefix concatenation, polynomially computable function.
Funding agency Grant number
Russian Foundation for Basic Research 13-01-00958
This research was carried out with the financial support of the Russian Foundation for Basic Research (grant no. 13-01-00958).
Received: 14.04.2015
English version:
Discrete Mathematics and Applications, 2016, Volume 26, Issue 3, Pages 155–163
DOI: https://doi.org/10.1515/dma-2016-0013
Bibliographic databases:
Document Type: Article
UDC: 519.716
Language: Russian
Citation: Sergey S. Marchenkov, “On elementary word functions obtained by bounded prefix concatenation”, Diskr. Mat., 27:3 (2015), 44–55; Discrete Math. Appl., 26:3 (2016), 155–163
Citation in format AMSBIB
\Bibitem{Mar15}
\by Sergey S. Marchenkov
\paper On elementary word functions obtained by bounded prefix concatenation
\jour Diskr. Mat.
\yr 2015
\vol 27
\issue 3
\pages 44--55
\mathnet{http://mi.mathnet.ru/dm1334}
\crossref{https://doi.org/10.4213/dm1334}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3468400}
\elib{https://elibrary.ru/item.asp?id=24849928}
\transl
\jour Discrete Math. Appl.
\yr 2016
\vol 26
\issue 3
\pages 155--163
\crossref{https://doi.org/10.1515/dma-2016-0013}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000384440200003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84979885354}
Linking options:
  • https://www.mathnet.ru/eng/dm1334
  • https://doi.org/10.4213/dm1334
  • https://www.mathnet.ru/eng/dm/v27/i3/p44
  • This publication is cited in the following 6 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:431
    Full-text PDF :180
    References:60
    First page:31
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024