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
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.
linear list, list structure, decidable structure, automatic structure, tree automatic structure.
|Russian Foundation for Basic Research
|Russian Science Foundation
|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).
PDF file (366 kB)
Siberian Mathematical Journal, 2019, 60:3, 377–388
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
\by S.~A.~Aleksandrova, N.~A.~Bazhenov
\paper On decidability of list structures
\jour Sibirsk. Mat. Zh.
\jour Siberian Math. J.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
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
|Number of views:|