Сборник содержит работы по ряду актуальных направлений математической логики, теории алгоритмов и их приложений. В этих работах исследуются логики доказуемости, уравнения в термах с подстановками, сложность алгоритмов распознавания вхождения одного слова в другое, доказывается разрешимость одного фрагмента элементарной теории свободной группы, изучается взаимосвязь между сложностью булевых функций и свойствами комбинаторных объектов.
Знакомство с изложенными в настоящем сборнике результатами будет полезно как для логиков, так и длш специалистов в смежных областях.
Сборник ВК-134 издается как информационные материалы Научного совета АН СССР по комплексной проблеме «Кибернетика».
Author(s): Адян С.И. (ред)
Series: Вопросы кибернетики, выпуск 134
Publisher: АН СССР
Year: 1988
Language: Russian
Pages: 181
С. Н. Артёмов. О логиках, имеющих доказуемостную интерпретацию 5
Б. Л. Будинас. Разрешимость проблемы достижимости для систем векторного сложения 22
В. А. Варданян. Оценки арифметической сложности предикатных логик доказуемости 46
А. Г. Иванов. Распознавание вхождения слов в реальное время на конечных многоголовочных автоматах 72
Г. С. Маканин. Об одном разрешимом фрагменте элементарной теории свободной группы 103
В. Л. Миронов. Восстановление графов с метками 114
В. П. Оревков. Системы уравнений в термах с подстановками 127
А. А. Разборов. Формулы ограниченной глубины в базисе {&, O} и некоторые комбинаторные задачи 149
Н. Н. Репин. Некоторые просто заданные группы, для которых невозможен алгоритм, распознающий разрешимость уравнений 167
С. Ф. Сопрунов. Разрешимые обогащения структур 175
