This article is cited in
2 papers
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.
UDC:
510.674+
519.713 Received: 10.07.2018
Revised: 10.07.2018
Accepted: 19.12.2018
DOI:
10.33048/smzh.2019.60.302
Fulltext:
PDF file (366 kB)
