Выразительная сила языков первого порядка для конечных алгебраических систем над бесконечными универсумами тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Дудаков, Сергей Михайлович

• Дудаков, Сергей Михайлович
• доктор физико-математических наук
• 2006

Оглавление диссертации доктор физико-математических наук Дудаков, Сергей Михайлович

Введение

Актуальность.

Обзор литературы.

Цели работы.

Апробация работы.

Структура диссертации.

1 Определения

1.1 Основные обозначения.

1.2 Теории и алгебраические системы.

1.3 Арифметические теории.

1.4 Автоматные системы.

1.5 Свойство коллапса к сигнатуре.

2 Термально изолированные множества

2.1 Определения

2.2 Существование термально изолированных множеств.

2.3 Коллапс к порядку для арифметики Семёнова.

2.4 Свойства предикатных обогащений начального фрагмента нестандартных моделей арифметики Пресбургера.

2.5 Коллапс к порядку для обогащений начального фрагмента нестандартных моделей арифметики Пресбургера.

3 Случайный граф

3.1 Определения.

3.2 Состояния над случайным графом.

3.3 Разрешимое упорядочение случайного графа.

3.4 Монадические сигнатуры.

4 Сводимые теории

4.1 Основные определения.

4.2 Свойства сводимых алгебраических систем.

4.3 (к, /)-формулы

4.4 Тотальная сводимость систем.

4.5 Достаточные условия сводимости.

4.6 Сводимость, изолированность и псевдоконечная однородность

5 Автоматные системы и их обобщения

5.1 Сложное обогащение арифметики Пресбургера.

5.2 Элиминация кванторов в теории Tr.

5.3 Начальные фрагменты системы

5.4 Состояния £>() над системой £Е.

5.5 Обобщения теории ТЕ.

6 Эффективная трансляция

6.1 Достаточные условия эффективной трансляции.

Введение диссертации (часть автореферата) на тему «Выразительная сила языков первого порядка для конечных алгебраических систем над бесконечными универсумами»

Актуальность

В настоящее время средства и методы математической логики находят всё более широкое применение при проектировании и анализе программного обеспечения ЭВМ. Одним из наиболее тесно связанных с информатикой разделом математической логики является теория языков первого порядка. Особенно интенсивно развивается теория языков для конечных алгебраических систем. Это обусловлено тем, что такие языки широко используются в системах управления базами данных, где служат средством извлечения информации из баз данных.

Сейчас типичной моделью базы данных является предложенная Э.Коддом реляционная модель, в которой база данных мыслится как собрание конечного числа конечных таблиц (см. [27, 28]). Количество строк в этих таблицах и сами строки могут меняться, но количество столбцов постоянно. Таким образом, база данных может рассматриваться как некоторая конечная сигнатура, а состояние базы данных — как конечная алгебраическая система этой сигнатуры.

Для извлечения информации используются языки запросов. В качестве такого языка обычно используются различные версии языка SQL1, который, по сути дела, является стилизацией языка логики предикатов первого порядка. Эта традиция тоже восходит к Э.Кодду, который в качестве языка

SQL — сокращение Structured Query Language (язык структурированных запросов). Язык разработан фирмой IBM в 1970 году. В настоящее время является стандартным языком для взаимодействия с системами управления базами данных. запросов предложил использовать язык реляционных выражений, практически эквивалентный языку логики предикатов первого порядка.

Хорошо известно, что не всякое свойство конечных алгебраических систем может быть выражено формулами логики предикатов, то есть не всякая информация может быть получена из базы данных при помощи языков первого порядка. Например, если сигнатура базы данных содержит только один одноместный предикатный символ Р, то невозможно записать в этой сигнатуре формулу первого порядка, выделяющую среди конечных алгебраических систем этой сигнатуры в точности те, в которых количество элементов Р является чётным. Другой пример: для двухместного предиката Е, задающего конечный граф, невозможно записать формулу, которая будет истинной тогда и только тогда, когда этот граф является связным (см. [18]).

Обычно, элементы отношений базы данных выбираются из фиксированного множества, называемого универсумом. Например, в конечном итоге, вся информация в компьютерах хранится в виде натуральных чисел, поэтому в качестве универсума можно рассматривать множество натуральных чисел. Другие примеры — множество всех слов некоторого алфавита или множество действительных чисел. Поскольку размер самих таблиц хоть и конечен в каждый момент времени, но не ограничен, то универсум должен быть бесконечным.

Так как не всякое свойство конечных алгебраической системы может быть выражено формулой языка первого порядка сигнатуры этой системы, то активно ведётся поиск методов увеличения выразительной силы этих языков. Один из путей состоит в следующем (см. [37]). Обычно, на универсуме, элементы которого хранятся в таблицах, определены какие-либо стандартные отношения. Например, для множеств натуральных или действительных чисел такими отношениями являются операции сложения и умножения, отношение порядка и т.д. Рассматривая множество слов, можно использовать операцию конкатенации или отношение лексикографического порядка. Таким образом, универсум тоже является алгебраической системой, но, в отличие от базы данных, бесконечной. Другое отличие — если состояние базы данных меняется, то универсум является фиксированным.

Можно предполагать, что если при построении формул первого порядка использовать не только отношения базы данных, но и отношения универсума (такие формулы называются расширенными), то в этом расширенном языке можно будет выразить какие-то свойства базы данных, которые невозможно выразить, используя только отношения базы данных (такие формулы называют ограниченными). Разумеется, для сравнения имеет смысл рассматривать только такие формулы, истинность которых определяется исключительно отношениями базы данных, а не способом связи между этими отношениями и отношениями универсума. Говоря другими словами, истинность формул, которые используются для сравнения выразительной силы, не должна зависеть от способа вложения базы данных в универсум. Формулы, обладающими этим свойством, называются локально =-генерическими или =-инвариантными. Если для некоторого универсума любая ^-инвариантная расширенная формула эквивалентна ограниченной, то говорят, что имеет место коллапс к равенству. Таким образом, коллапс к равенству означает, что используемые в расширенных формулах отношения универсума не позволяют выразить никаких новых свойств базы данных по сравнению с ограниченными формулами.

В результате возникло новое направление исследований в теории моделей — теория конечных алгебраических систем, вложенных в бесконечные. Одним из главных вопросов этого направления является задача сравнения выразительной силы ограниченных и расширенных языков.

Некоторые отношения универсума действительно увеличивают выразительную силу языка первого порядка. Так Ю.Ш.Гуревич продемонстрировал, что примером такого отношения является обычное отношение линейного порядка. Он предложил свойство базы данных, которое нельзя выразить, используя только отношения базы данных, но можно, если добавить к ним произвольный линейный порядок. Иначе говоря, для упорядоченных универсумов не выполняется коллапс к равенству.

Естественно рассматривать следующую задачу:

Какие отношения можно добавить к отношению линейного порядка, чтобы ещё увеличить выразительную силу языка?»

Поскольку теперь мы будем сравнивать выразительную силу расширенного языка с выразительной силой языка, включающего порядок, то нужно рассматривать не только ^-инвариантные формулы, но и те, истинность которых зависит от отношений базы данных и способа упорядочения её элементов. Такие формулы называют локально с-генерическими или <инвариантными.

Оказывается, что ряд универсумов обладает следующим свойством:

Всякая расширенная <-ипвариантная формула эквивалентна некоторой <-ограничешюй (то есть формуле с использованием только отношений базы данных и порядка).»

Такое свойство универсума называют коллапсом к порядку (или трансляционной теоремой для универсума). Известно, например, что эта теорема верна для арифметики Пресбургера, теории действительных чисел, коммутативных групп и других разрешимых теорий (см. [21, 20, 43]).

С другой стороны, имеются неразрешимые системы, в которых эта теорема не выполняется, например, арифметика натуральных чисел со сложением и умножением или теория множеств.

Диссертация посвящена изучению свойств коллапса и его связи с другими свойствами алгебраических систем, например, сводимостью (см. [19]). Мы изучаем различные универсумы на предмет наличия коллапса. Мы находим примеры систем с разрешимой теорией, в которых коллапс к порядку отсутствует. Так же нами получен метод, который позволяет в некоторых случаях получить эффективное доказательство трансляционной теоремы, то есть построение С-ограниченной формулы эквивалентной С-инвариантной расширенной можно выполнить алгоритмически. Таким образом, мы отвечаем на ряд открытых вопросов, сформулированных и опубликованных разными авторами.

Обзор литературы

Реляционная модель базы данных предложена Э.Коддом в [27, 28]. Там же высказана мысль о том, что для извлечения информации можно использовать алгебру отношений (реляционную алгебру). В своей статье [28] он доказал, что выразительная сила реляционной алгебры не меньше, чем у логики первого порядка. В статье [18] показано обратное: логика предикатов позволяет извлечь любую информацию, которую можно извлечь с помощью операций реляционной алгебры. Таким образом, предложенная Э.Коддом модель языка для извлечения информации из баз данных эквивалентна логике первого порядка.

В [18] показано, что существуют простые свойства алгебраических систем, которые с помощью логики предикатов выразить невозможно. Классическими примерами таких свойств являются чётность количества элементов конечного множества и связность графа. П.Канеллакис с соавторами в [37] высказали идею об использовании в формулах кроме отношений базы данных также отношений универсума, в который база данных вложена. Предполагалось, что использование внешних, «универсальных», не зависящих от базы данных знаний может увеличить выразительную силу языка запросов. Естественно, для сравнения выразительной силы необходимо рассматривать только формулы, истинность которых не зависит от способа вложения базы данных в универсум. Они должны сохранять свое истинностное значение при произвольных изоморфизмах базы данных внутри универсума. Впервые такой класс формул был выделен в статье [26].

В некоторых случаях увеличение выразительной силы действительно возможно. Один из самых замечательных результатов получен Ю.Ш.Гуревичем в 1990 году. Он доказал (см.[20, 9]),2 что наличие среди отношений универсума линейного порядка действительно расширяет множество свойств базы данных, выразимых формулами логики предикатов. Этот результат совершенно не зависит от типа линейного порядка и от того, как при вложении упорядочиваются элементы базы данных.

После получения этого результата стали рассматривать формулы, инвариантные относительно сохраняющих порядок изоморфизмов (см. [39, 21]), и изучать, в каких случаях эти формулы эквивалентны формулам с использованием лишь отношений базы данных и порядка. Сам термин «коллапс к порядку» появился в предварительных вариантах работ [20] и [19]

В работах [33, 34, 21] приведены примеры, когда использование отношений универсума приводит к дальнейшему увеличению выразительной силы языка. В [22] показано, что коллапса к порядку нет в арифметике натуральных чисел со сложением и умножением. Аналогичная этой структура — натуральные числа со сложением и возведением в квадрат, в ней выразимо умножение (см. [24, 43]). Каждая из этих теорий неразрешима. Другой приведённый в [22] пример — упорядоченный универсальный случайный граф, теория которого, как показано там же, неразрешима, если порядок дискретный.

С другой стороны, для многих разрешимых теорий было установлено, что они обладают свойством коллапса к порядку. Так, например, в [21] показано, что коллапс к порядку имеет место для всех о-минимальных теорий (которые были введены в [40, 38, 41]), в частности, для теории действи

2Сам Ю.Ш.Гуревич свои результаты не опубликовал. тельных чисел. Там же продемонстрировано, что коллапс к порядку имеет место в любой системе вида (С/, Pi, Р2,.), где ^ — линейный порядок, a Pi, Р2,. — произвольные одноместные предикаты.

В работе [39] доказано, что трансляция расширенных <-инвариантных формул в <-ограниченные может выполняться эффективно в системе действительных чисел со сложением (К, В [45] этот результат обобщён на произвольные упорядоченные абелевы группы с делением.

В работе [20] О.В.Белеградека, А.П.Столбоушкина и М.А.Тайцлина приведены необходимые и достаточные условия для того, чтобы заданная С-инвариантная формула была эквивалентна <-ограниченной. Далее там приводится несколько достаточных признаков, позволяющих установить для теории свойство коллапса к порядку, в частности, в этой работе введены понятия псевдоконечной однородности и изолированности (позже, в работе [17], эти свойства будут уточнены и названы первыми свойствами псевдоконечной однородности и изолированности соответственно). Доказательства используют теоретико-модельные построения и теорему компактности, из них невозможно получить алгоритм, который выполнял бы построение такой <-ограничеипой формулы. Показано, что первое свойство псевдоконечной однородности является более широким, чем первое свойство изолированности. В качестве открытых проблем в этой работе, в частности, указаны:

Задача 1. Поиск эффективного алгоритма трансляции расширенных <инвариантных формул в <-ограниченные для арифметики Пресбургера (проблема 1).

Задача 2. Верно ли, что для любой разрешимой теории, для которой имеет место коллапс к порядку, существует эффективный алгоритм трансляции (проблема 2)?

Задача 3. Верно ли, что для любого разрешимого обогащения системы натуральных чисел с порядком (ш, имеет место коллапс к порядку (проблема 3)? Высказано предположение, что это верно.

Задача 4. Усиление предыдущего, Верно ли, что если для некоторого обогащения системы (и>, коллапса к порядку нет, то в этом обогащении существует формула ip(x,y), которая способна из любого мноэюества векторов длины выделить произвольное конечное подмножество (проблема 4)? Точнее, для любого мноэюества А = {ai,., а^} наборов натуральных чисел существует вектор Ьа такой, что

Va) (ip (а, Б а) & а е А).

Авторы предполагали, что это имеет место.

Дальнейшие результаты связаны с использованием этих необходимых и достаточных признаков. Например, введённые в [20] первые свойства псевдоконечной однородности и изолированности гарантируют наличие коллапса к порядку для универсума. В [46] предложены более общие условия (21, /)-псевдоконечной однородности и (21, /)-изолировашюсти, из которых следует то же самое. Используя этот метод, в [20] удалось доказать коллапс к порядку для введённых авторами квази-о-минимальных теорий, которые являются обобщениями о-минимальных теорий. В частности, коллапс к порядку был установлен для коммутативных упорядоченных групп и вещественно замкнутых полей.

В работе [16] коллапс к порядку установлен для обогащений арифметики Пресбургера слабо монотонными согласованными со сложением функциями (см. [13]). Там же сформулированы более слабые варианты гипотез из [20]:

Задача 5. Для любого разрешимого обогащения арифметики Пресбургера (о;, 0,1, +) имеет место коллапс к порядку (гипотеза 1).

Задача 6. Если для некоторого обогащения арифметики Пресбургера коллапса к порядку нет, то в этом обогащении существует формула ip (х, у), которая способна из любого множества векторов длины \х\ выделить произвольное конечное подмножество (гипотеза 2). Точнее, для любого множества А = {ai,. наборов натуральных чисел существует вектор bа такой, что

Va) (<р (а, Вд) <=> а Е А).

В [17] кроме первых свойств псевдоконечной однородности и изолированности были введены их аналоги — вторые свойства псевдоконечной однородности и изолированности. Подобно первым свойствам, вторые тоже влекут коллапс к порядку.

Другой подход, который, однако, всё ещё использует неэффективные теоретико-модельные построения, предложен в работе [19] Дж.Болдвина и М.Бенедикта и усовершенствован в [46]. В [19] рассматриваются теории без независимой формулы (о самом понятии независимой формулы можно прочитать в [44]). В этой работе введены /-сводимые алгебраические системы, которые используются как техническое средство для доказательства коллапса к порядку в теориях без независимой формулы, / является неразличимой последовательностью в алгебраической системе. В [19] показано, что каждая теория, в которой отсутствует независимая формула, имеет /-сводимые модели. В работе в виде открытого вопроса высказана следующая задача:

Задача 7. Верно ли, что кол/ianc к порядку для универсума имеет место тогда и только тогда, когда в нём существует бесконечное определимое множество без независимой формулы?

Основной целью работ [46] и [17] было доказательство того, что определённый класс теорий (имеющих /-сводимые модели, в которых каждая формула эквивалентна Р-ограниченной формуле) обладает свойством коллапса к порядку. Однако для доказательства этого в [46] и [17] использовано не только свойство /-сводимости моделей, но и ещё одно условие: каждая формула должна быть эквивалентна Р-ограниченной формуле. В работе [19] показано, что существование таких моделей также следует из отсутствия в теории независимой формулы. Но связи между этим свойством и /-сводимостью в [19] так и не было найдено. Осталась не установленной и связь между псевдоконечной однородностью, сводимостью и отсутствием независимой формулы, что было отмечено в [20].

В работах А.Л.Семёнова [14, 15] доказано, что обогащение арифметики Пресбургера согласованными со сложением предикатами и функциями разрешимы, если «согласование» осуществляется эффективно. К таким функциям относятся, найример, показательная функция по натуральному основанию или факториал числа.

Понятие (универсального) случайного графа введено в работе [42]. В [23, 22] показано, что для упорядоченного универсального случайного графа свойство коллапса к порядку отсутствует. Если база данных содержит одноместный предикат, то возможно записать чётность количества его элементов. Хорошо известно (см., например, [24]), что дискретное упорядочение случайного графа не разрешимо, он не может служить опровержением гипотез о коллапсе к порядку для разрешимых теорий (задачи 3, 4). После опубликования работы автора [7] О.В.Белеградек (в устной форме) сформулировал следующую задачу.

Задача 8. Имеет ли место коллапс к равенству для неупорядоченного случайного графа?

В [43] приводится прямой метод установления коллапса к порядку. Н.Швайкардт демонстрирует использование непосредственно игр Эрен-фойхта. Метод этот, к сожалению, не обладает никакой универсальностью, в каждом конкретном случае приходится определять стратегию повторителя. Не указано никаких признаков для теории, но которым можно было бы распознать, применим ли этот метод.

Одним из интереснейших достижений последнего времени в области арифметических теорий явилось оригинальное обогащение арифметики Пресбургера, предложенное в [25] А.Блюменсатом и Э.Гределем. Это обогащение разрешимо и, в то же время, имеет независимую формулу (чем была опровергнута гипотеза из [19], что таких обогащений не существует). В построенной системе каждая формула эквивалентна (в определённом смысле) некоторому конечному автомату и наоборот, поэтому введённые в [25] системы названы автоматными. В [17] предложено аналогичное обогащение при помощи предиката Е (см. определение в главе 1) и показано, что такое обогащение не обладает свойствами изолированности. Далее, в [17] ставится следующий вопрос.

Задача 9. Обладает ли теория системы (и>, Е) свойством коллапса к порядку?

Цели работы

1) Установить, имеет ли место коллапс к порядку в семёновских обогащениях арифметики Пресбургера.

2) Установить, существуют ли разрешимые теории в которых коллапса к порядку нет (задачи 3, 4),

3) в частности, установить, есть ли такие системы среди обогащений арифметики Пресбургера (задачи 5, 6),

4) в частности, установись, имеет ли место коллапс к порядку для системы (ш, Е) (задача 9).

5) Детально исследовать случайный граф на предмет свойства коллапса (задача 8).

6) Установить связь между сводимостью, изолированностью, псевдоконечной однородностью и коллапсом к порядку.

7) Установить, имеются ли сводимые обогащения арифметики Пресбургера с независимой формулой (задача 7).

8) Разработать механизмы эффективной трансляции для расширенных <инвариантных формул в <-ограниченные (задачи 1, 2).

Апробация работы

Содержание диссертации опубликовано в журналах: «Математические заметки» (см.[3, 4]), «Известия РАН. Серия математическая» (см.[6]), «Фундаментальная и прикладная математика» (см.[10]), «Успехи математических наук» (см.[9]), «Вестник Тверского государственного университета» (см.[7, 11]), «Вестник Новгородского государственного университета» (см. [8]), других изданиях (см. [5]).

Содержание диссертации многократно излагалось в 2001-2006 годах на семинаре «Теоретические основы информатики», проходящем в Тверском государственном университете, семинаре по математической логике Московского университета, семинаре по математической логике Санкт-Петербургского отделения математического института РАН.

Доклад, посвящённый одному из разрабатываемых в диссертации вопросов, был сделан на международной конференции по теоретической информатике CSR-2006 (Санкт-Петербург, июнь 2006, см. [29]).

Структура диссертации

Диссертация состоит из введения, шести глав основной части, заключения, списка литературы и предметного указателя.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Дудаков, Сергей Михайлович

Основные результаты

В работе доказаны следующие основные утверждения.

1) В обогащениях арифметики Пресбургера одноместной согласованной со сложением функцией или предикатом имеет место коллапс к порядку.

2) Коллапс к порядку имеет место в предикатных обогащениях начального фрагмента нестандартных моделей арифметики Пресбургера.

3) Для случайного графа, на котором коллапса к порядку нет, существуют разрешимые упорядочения.

4) Для неупорядоченного случайного графа коллапс к равенству имеет место тогда и только тогда, когда сигнатура базы данных является мона-дической. Это даёт исчерпывающий ответ к задаче 8.

5) Свойство сводимости, второе свойство псевдоконечной однородности и второе свойство изолированности эквивалентны. Каждое из них влечёт свойство коллапса к порядку.

6) Первое свойство изолированности является менее общим чем второе. Первое свойство псевдоконечной однородности является менее общим чем второе или эквивалентно ему.

7) Если теория имеет эффективно сводимые модели, то она имеет эффективно тотально сводимые модели.

8) Если теория имеет эффективно /-сводимую модель, и тип неразличимого множества / рекурсивен, то возможно выполнение эффективной трансляции расширенных <-инвариантных формул в <-ограничеиные. Таким образом получен частичный ответ на открытый вопрос 2 из работы [20] (задача 2).

9) Эффективная трансляция расширенных С-инвариантных формул в <ограниченные возможна для арифметики Пресбургера, её эффективных семёновских обогащений, для теории действительных чисел. Это даёт утвердительный ответ на открытый вопрос 1 из работы [20] (задача 1).

10) Существуют разрешимые обогащения арифметики Пресбургера, в которых нет коллапса к порядку. Таким образом получен отрицательный ответ на открытые вопросы 3 и 4 из работы [20] (задачи 3, 4), опровергнуты гипотезы 1 и 2 из [16] (задачи 5, 6), и дай отрицательный ответ на вопрос из [17] (задача 9).

11) Существуют обогащения арифметики Пресбургера, в которых есть коллапс к порядку, но всякое бесконечное множество имеет независимую формулу. Таким образом получен отрицательный ответ на открытый вопрос из [19] (задача 7).

Направления дальнейших исследований

Мы опровергли несколько предположения из работ [20] и [16]. Однако видим, что при построении контрпримера (свойство (5.9)) получается формула с использованием многоместных отношений, и это существенно используется в доказательствах. Поэтому представляет интерес исследование выразительной силы языка первого порядка в системе £Е, когда база данных содержит лишь одноместные предикаты, в частности, один одноместный предикат. В главе 3 мы показали, что такое ограничение может играть решающую роль.

В связи с этим мы можем переформулировать предположения 3 и 4 из работы [20] и гипотезы 1 и 2 из [16] в виде следующего вопроса.

Вопрос 1. В любом ли разрешимом обогащении арифметики Пресбургера невозможно выразить чётность количества элементов произвольного одноместного конечного предиката?

Верно ли, что если в обогащении арифметики Пресбургера возможно выразить чётность количества элементов произвольного одноместного конечного предиката, то в таком расширении существует формула (р(х, у), способная выделить из произвольного конечного множества любое подмножество?

Еще один вопрос заключается в следующем.

Вопрос 2. Существуют ли разрешимые обогащения арифметики Семёнова, в которых пет коллапса к порядку? В частности, существуют ли такие обогащения для системы (и, 0,1, +, 2х) ?

Мы показали, что в самих семёновских обогащениях коллапс к порядку есть. С другой стороны, одновременное обогащение арифметики Пресбургера экспонентой 2х и отношением Е приводит к неразрешимой теории, эквивалентной арифметике со сложением и умножением.

Следующий вопрос снова связан с системой £Е. Мы показали, что отношение Е действительно расширяет множество выражаемых формулами первого порядка свойств. Естественная задача — поиск обогащений системы £е, в которых выразительная сила языков первого порядка ещё бы возросла.

Вопрос 3. Существуют ли разрешимые обогащения системы £Е, в которых нет коллапса к ?

Мы установили, что для проверки наличия свойства коллапса к порядку мы можем эквивалентно использовать свойства псевдоконечной однородности, изолированности и сводимости. Стоит отметить, что изначально первые два свойства были сформулированы независимо от третьего.

Вопрос 4. Существуют ли теории, которые обладают свойством коллапса к порядку, но не имеют при этом сводимых моделей? Другими словами, являются ли свойства псевдоконечной однородности, изолированности и сводимости необходимыми для коллапса к порядку?

Заключение

Список литературы диссертационного исследования доктор физико-математических наук Дудаков, Сергей Михайлович, 2006 год

1. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.

2. Верещагин Н.К., Шень А. Языки и исчисления. М.: МЦНМО, 2000.

3. Дудаков С.М. Трансляционный результат для расширений арифметики Пресбургера одноместной функцией, согласованной со сложением // Матем. заметки, №76(3), 2004, С.362-371.

4. Дудаков С.М. Псевдоконечная однородность, изолированность и сводимость // Матем. заметки, №81(4), 2007, С.515-527.

5. Дудаков С.М. Трансляционная теорема в предикатных обогащениях начального фрагмента нестандартных моделей арифметики Пресбургера. // Сложные системы: обработка информации, моделирование и оптимизация, ТвГУ, Тверь, 2002. С.24-37.

6. Дудаков С.М. Трансляционная теорема для теорий /-сводимых алгебраических систем // Изв. РАН. Серия матем., №68(5), 2004. С.67-90.

7. Дудаков С.М. Выразительная сила языков запросов первого порядка для баз данных на неупорядоченном случайном графе. // Вестник НовГУ. №34, 2005. С.51-57.

8. Дудаков С.М. Разрешимая теория без трансляционной теоремы. // Вестник ТвГУ, серия «Прикладная математика», №6(12), 2005. С.23-26.

9. Дудаков С.М., Тайцлин М.А. Трансляционный результат для языков запросов в теории баз данных. // Успехи математических наук, №61:2(368), 2006. С.2-65.

10. Дудаков С.М. Достаточные условия эффективной трансляции локально генерических запросов // Фундаментальная и прикладная математика (принято к публикации)

11. Дудаков С.М. Трансляционная теорема и автоматные структуры // Вестник ТвГУ, серия «Прикладная математика», №4(21), 2006. С.5-35.

12. Кейслер Г., Чен Ч.Ч. Теория моделей. М.: Мир, 1997.

13. Попов И.В. Элиминация кванторов в некоторых обогащениях арифметики Пресбургера. // Сложные системы: обработка информации, моделирование и оптимизация, ТвГУ, Тверь, 2002, С.38-47.

14. Семёнов A.JI. О некоторых расширениях арифметики сложения натуральных чисел. // Изв. АН СССР, 43(5), 1979. С.1175-1195.

15. Семёнов A.JI. Логические теории одноместных функций на натуральном ряде. // Изв. АН СССР, 47(3), 1983. С.623-658.

16. Тайцлин М.А. Трансляционные результаты в теории баз данных. // Сложные системы: обработка информации, моделирование и оптимизация, Тверь: Тверской государственный университет, 2002. С.5-23.

17. Тайцлин М.А. Ограниченные псевдоконечная однородность и изолированность. // Вестник Тверского государственного университета, серия «Прикладная математика», Тверь: Тверской государственный университет, 2003. 2(1). С.5-15.

18. Aho A.V., Ullman J.D. Universality of data retrieval languages. // Proc. of 6th Symp. on Principles of Programming Languages, 1979. P. 110-120.

19. Baldwin J., Benedikt M. Stability theory, permutations of indiscernibles, and embedded finite models. // AMS Trans., 352(11), 2000. C.4937-4969.

20. Belegradek O.V., Stolboushkin A.P., Taitslin M.A. Extended order-generic queries. // Annals of Pure and Applied Logic 97, 1999. P.85-125.

21. Benedict M., Dong G., Libkin L., Wong L. Relational expressive power of constraint query languages. // Proc. 15th ACM Symp. on Principles of Database Systems, 1996. P.5-16.

22. Benedict M., Libkin L. Expressive power: the finite case. // Constraint databases, Berlin: Springer-Verlag, 1996. P.55-87.

23. Benedict M., Libkin L. Languages for relational databases over interpreted structures. // Proc. 16th ACM Symp. on Principles of Database Systems, 1996. P.25-39.

24. Bes A. A survey of arithmetical definability. //A tribute to Maurice Boffa, Soc. math, belgique, 2002. P. 1-54.

25. Blumensath A., Graedel E. Automatic structures. // Proc. 15th IEEE Symp. on Logic in Computer Science, 2000. P.51-62.

26. Chandra A., Harel D. Computable queries for relational databases. // Journal of compuer and system sciences, V.21(2), 1980. P. 156-178.

27. Codd E.F. A relational model for large shared data banks. // Communications of the ACM, V.13, 1970. P.377-387.

28. Codd E.F. Relational completeness of data base sublanguages. // Database Systems (ed. Rustin R.), Prentice-Hall, 1972. P.33-64.

29. Dudakov S.M. Isolation and reducibility properties and the collapse result. // Proc. of intern, conf. CSR-2006 (Computer Sciences in Russia, Санкт-Петербург, июнь 2006). LNCS 3967, Springer, 2006. P.171-177.

30. Ehrenfeucht A. An application of games to the completeness problem for formalized theories. // Fundarnenta Matematicae, № 49, 1961. P.129-141.

31. Erdos P., Spencer J. Probabilistic methods in combinatorics. // New York: Academic Press, 1974.

32. Frai'sse R. Sur quelques classifications des systemes de relations. // Universite d'Alger, Publications Scientifiques, Serie A, № 1, 1954. P.35-182.

33. Grumbach S., Su J. Dense order constraint databases. // Journal of computer and sysem sciences, 55(2), 1997. P.273-298.

34. Grumbach S., Su J., Tollu C. Linear constraint databases. // Proc. of intern, conf. LCC-94 (Logic and computational complexity), LNCS 960, Springer, 2006. P.426-446.

35. Hodges W. Model theory. Cambridge: Cambridge university press, 1993.

36. Hull R., Yap C.K. The format model, a theory of database organization. // Journal of the ACM, № 31, 1984. P.518-537.

37. Kanellakis P., Kuper G. Revesz P. Constraint query languages. // Journal of compuer and system sciences, V.51, 1995. P.26-52.

38. Knight J.F., Pillay A., Steinhorn C. Definable sets in ordered structures II. // AMS Trans, №295(2), 1986. P.593-605.

39. Paradaens J, Van den Bussche J, Van Gucht D. First-order queries on finite structures over real. // Proc. 10th IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1995. P.79-87.

40. Pillay A, Steinhorn C. Definable sets in ordered structures I. // AMS Trans, №295(2), 1986. P.565-592.

41. Pillay A., Steinhorn C. Definable sets in ordered structures III. // AMS Trans., №309(2), 1988. P.469-476.

42. Rado R. Universal graphs and universal functions. // Acta Arith., jV 9, 1964. P.331-340.

43. Schweikardt N. On the expressive power of first-order logic with built-in predicates. Berlin: Logos-Verlag, 2002.

44. Shelah S. Classification theory and the number of non-isomorphic models (2nd ed. revised). Amsterdam: North Holland, 1990.

45. Stolboushkin A.P., Taitslin M.A. Linear vs. order constraint queries over relational databases. // Proc. 15th ACM Symp. on Principles of Database Systems, 1996. P.17-27.

46. И7 б, 55 £, 25 £Е, 30 £д, 105 £sf, 27 £sp, 27автоматная, 28 малая, 68 насыщенная, 23специальная, 23 тотально /-сводимая, 69 эффективно, 69 арифметика

47. С-ограниченпая, 32 Щ, 117 £л, 25 30 EG, 55 Еп, 10526 26