|
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
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
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
Linking options:
https://www.mathnet.ru/eng/smj2108 https://www.mathnet.ru/eng/smj/v51/i3/p575
|
Statistics & downloads: |
Abstract page: | 274 | Full-text PDF : | 95 | References: | 48 | First page: | 4 |
|