Sibirskii Matematicheskii Zhurnal
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


Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find




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

Sibirskii Matematicheskii Zhurnal, 2010, Volume 51, Number 3, Pages 575–583 (Mi smj2108)  
This article is cited in 1 scientific paper (total in 1 paper)

Definability in the structure of words with the inclusion relation

O. V. Kudinova, V. L. Selivanovb, L. V. Yartsevab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b A. P. Ershov Institute of Informatics Systems Sib. Br. RAS, Novosibirsk
Full-text PDF (310 kB) Citations (1)
References:
PDF
HTML
Abstract: We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the $h$-quasiorder of finite $k$-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 or 2 are taken as parameters), the first-order theory of the structure is atomic and computably isomorphic to the first-order arithmetic. We also characterize the automorphism group of the structure and show that every predicate invariant under the automorphisms of the structure is definable in the structure.
Keywords: subword, infix order, definability, automorphism, least fixed point, first-order theory, bi-interpretability.
Received: 01.03.2010
English version:
Siberian Mathematical Journal, 2010, Volume 51, Issue 3, Pages 456–462
DOI: https://doi.org/10.1007/s11202-010-0047-y
Bibliographic databases:
Document Type: Article
UDC: 510.53+512.562
Language: Russian
Citation: O. V. Kudinov, V. L. Selivanov, L. V. Yartseva, “Definability in the structure of words with the inclusion relation”, Sibirsk. Mat. Zh., 51:3 (2010), 575–583; Siberian Math. J., 51:3 (2010), 456–462
Citation in format AMSBIB
\Bibitem{KudSelYar10}
\by O.~V.~Kudinov, V.~L.~Selivanov, L.~V.~Yartseva
\paper Definability in the structure of words with the inclusion relation
\jour Sibirsk. Mat. Zh.
\yr 2010
\vol 51
\issue 3
\pages 575--583
\mathnet{http://mi.mathnet.ru/smj2108}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2683099}
\zmath{https://zbmath.org/?q=an:1209.03027}
\transl
\jour Siberian Math. J.
\yr 2010
\vol 51
\issue 3
\pages 456--462
\crossref{https://doi.org/10.1007/s11202-010-0047-y}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000279087500009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77954001507}
Linking options:
  • https://www.mathnet.ru/eng/smj2108
  • https://www.mathnet.ru/eng/smj/v51/i3/p575
    • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Сибирский математический журнал Siberian Mathematical Journal
    Statistics & downloads:
    Abstract page:235
    Full-text PDF :76
    References:36
    First page:4
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024