RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1990, том 47, выпуск 5, страницы 31–38 (Mi mzm3234)

Новое доказательство разрешимости элементарной теории линейно упорядоченных множеств

Н. К. Верещагин

Московский государственный университет им. М. В. Ломоносова

Аннотация: Предлагается алгоритм, обладающий двумя свойствами: он не использует сведения к разрешимости другой теории (как алгоритм Рабина) и имеет оптимальную верхнюю оценку времени – в отличие от алгоритма Лёйхли и Леонарда, для которого вообще нет явной верхней оценки времени.
Библиогр. 3 назв.

УДК: 517.1

Поступило: 15.10.1987
Исправленный вариант: 20.06.1989


 Англоязычная версия: Mathematical Notes, 1990, 47:5, 444–449

Реферативные базы данных:


© МИАН, 2024