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

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


Sibirsk. Mat. Zh., 2019, Volume 60, Number 3, Pages 489–505 (Mi smj3090)  

This article is cited in 1 scientific paper (total in 1 paper)

On decidability of list structures

S. A. Aleksandrovaa, N. A. Bazhenovba

a Novosibirsk State University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Novosibirsk State University, Novosibirsk, Russia

Abstract: The paper studies computability-theoretic complexity of various structures that are based on the list data type. The list structure over a structure $S$ consists of the two sorts of elements: The first sort is atoms from $S$, and the second sort is finite linear lists of atoms. The signature of the list structure contains the signature of $S$, the empty list $nil$, and the binary operation of appending an atom to a list. The enriched list structure over $S$ is obtained by enriching the signature with additional functions and relations: obtaining a head of a list, getting a tail of a list, “an atom $x$ occurs in a list $Y$,” and “a list $X$ is an initial segment of a list $Y$.” We prove that the first-order theory of the enriched list structure over $(\omega, +)$, i.e. the monoid of naturals under addition, is computably isomorphic to the first-order arithmetic. In particular, this implies that the transformation of a structure $S$ into the enriched list structure over $S$ does not always preserve the decidability of first-order theories. We show that the list structure over $S$ can be presented by a finite word automaton if and only if $S$ is finite.

Keywords: linear list, list structure, decidable structure, automatic structure, tree automatic structure.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-41-543015_р_мол_а
Russian Science Foundation 18-11-00028
S. A. Aleksandrova was supported by the Russian Foundation for Basic Research (Grant 18-41-543015 r_mol_a). N. A. Bazhenov was supported by the Russian Science Foundation (Grant 18-11-00028).


DOI: https://doi.org/10.33048/smzh.2019.60.302

Full text: PDF file (366 kB)
References: PDF file   HTML file

English version:
Siberian Mathematical Journal, 2019, 60:3, 377–388

Bibliographic databases:

UDC: 510.674+519.713
Received: 10.07.2018
Revised: 10.07.2018
Accepted:19.12.2018

Citation: S. A. Aleksandrova, N. A. Bazhenov, “On decidability of list structures”, Sibirsk. Mat. Zh., 60:3 (2019), 489–505; Siberian Math. J., 60:3 (2019), 377–388

Citation in format AMSBIB
\Bibitem{AleBaz19}
\by S.~A.~Aleksandrova, N.~A.~Bazhenov
\paper On decidability of list structures
\jour Sibirsk. Mat. Zh.
\yr 2019
\vol 60
\issue 3
\pages 489--505
\mathnet{http://mi.mathnet.ru/smj3090}
\crossref{https://doi.org/10.33048/smzh.2019.60.302}
\elib{http://elibrary.ru/item.asp?id=41685143}
\transl
\jour Siberian Math. J.
\yr 2019
\vol 60
\issue 3
\pages 377--388
\crossref{https://doi.org/10.1134/S0037446619030029}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000471617300002}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85067383505}


Linking options:
  • http://mi.mathnet.ru/eng/smj3090
  • http://mi.mathnet.ru/eng/smj/v60/i3/p489

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. S. Goncharov, S. Ospichev, D. Ponomaryov, D. Sviridenko, “The expressiveness of looping terms in the semantic programming”, Sib. elektron. matem. izv., 17 (2020), 380–394  mathnet  crossref
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:164
    Full text:4
    References:24
    First page:9

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020