N. A. Bazhenov, “Automatic structures and the theory of lists”, Sib. Èlektron. Mat. Izv., 2015, Volume 12,Pages <nobr>714

This article is cited in 1 paper

Mathematical logic, algebra and number theory

Automatic structures and the theory of lists

N. A. Bazhenov^ab

^a Institute of Mathematics and Mechanics, Kazan Federal University, Kremlevskaya ul., 35, 420008, Kazan, Russia
^b Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: Goncharov constructed the axiomatic theory of linear lists over the elements of a given data type. We study algorithmic complexity for models of this theory. We prove that the enriched list structure over a finite set of atoms is automatically presentable, and the enriched list structure over an infinite set of atoms has no automatic presentations.

Keywords: automatic structure, linear list, theory of lists, decidable model, list superstructure.

UDC: 510.5

MSC: 03D05, 03D45

Received September 30, 2015, published October 16, 2015

Language: English

DOI: 10.17377/semi.2015.12.057