|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Математическая логика, алгебра и теория чисел
Automatic structures and the theory of lists
N. A. Bazhenovab 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
Аннотация:
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.
Ключевые слова:
automatic structure, linear list, theory of lists, decidable model, list superstructure.
Поступила 30 сентября 2015 г., опубликована 16 октября 2015 г.
Образец цитирования:
N. A. Bazhenov, “Automatic structures and the theory of lists”, Сиб. электрон. матем. изв., 12 (2015), 714–722
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr620 https://www.mathnet.ru/rus/semr/v12/p714
|
Статистика просмотров: |
Страница аннотации: | 193 | PDF полного текста: | 56 | Список литературы: | 37 |
|