Логика графиков

Логическая формулировка свойств графа

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

Предложение может быть истинным для некоторых графов и ложным для других; говорят, что граф моделирует , пишется , если истинно для вершин и отношения смежности . Алгоритмическая проблема проверки модели касается проверки того, моделирует ли данный граф данное предложение. Алгоритмическая проблема выполнимости касается проверки того, существует ли граф, моделирующий данное предложение. Хотя и проверка модели, и выполнимость в целом сложны, несколько основных алгоритмических метатеорем показывают, что свойства, выраженные таким образом, могут быть эффективно проверены для важных классов графов. ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G\models S}$ ${\displaystyle S}$ ${\displaystyle G}$

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

Первый заказ

Показанный здесь граф выглядит как подграф неориентированного графа тогда и только тогда, когда моделирует предложение . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \exists x_{1},x_{2},x_{3},x_{4}.}$ ${\displaystyle x_{1}\sim x_{2}}$ ${\displaystyle \land }$ ${\displaystyle x_{2}\sim x_{3}}$ ${\displaystyle \land }$ ${\displaystyle x_{3}\sim x_{1}}$ ${\displaystyle \land }$ ${\displaystyle x_{3}\sim x_{4}}$ ${\displaystyle \land }$ ${\displaystyle x_{1}\neq x_{4}}$ ${\displaystyle \land }$ ${\displaystyle x_{2}\neq x_{4}}$

В логике первого порядка графов свойство графа выражается как квантифицированное логическое предложение, переменные которого представляют вершины графа , с предикатами для проверки равенства и смежности. ^[1]

Примеры

Например, условие, что граф не имеет изолированных вершин, может быть выражено предложением , где символ указывает на ненаправленное отношение смежности между двумя вершинами. Это предложение можно интерпретировать как означающее, что для каждой вершины существует другая вершина , которая смежна с . ^[1] $${\displaystyle \forall u\exists v(u\sim v)}$$ ${\displaystyle \sim }$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$

Проблема изоморфизма подграфов для фиксированного подграфа спрашивает, появляется ли как подграф большего графа . Она может быть выражена предложением, которое утверждает существование вершин (по одной для каждой вершины ) таких, что для каждого ребра , соответствующая пара переменных представляет смежные вершины и таких, что для каждой оставшейся пары вершин , соответствующая пара переменных представляет различные вершины; ^[2] см. иллюстрацию. В качестве особого случая проблема клики (для фиксированного размера клики) может быть выражена предложением, которое утверждает существование числа вершин, равного размеру клики, все из которых смежны. ^[3] ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle H}$

Аксиомы

Для простых неориентированных графов теория графов первого порядка включает аксиомы

${\displaystyle \forall u{\bigl (}\lnot (u\sim u){\bigr )}}$(граф не может содержать никаких петель ), и

${\displaystyle \forall u\forall v(u\sim v\Rightarrow v\sim u)}$(ребра ненаправленные). ^[4]

Другие типы графов, такие как ориентированные графы , могут включать в себя другие аксиомы ^[5] , а логические формулировки свойств мультиграфа требуют специальной обработки, например, наличия множественных рёберных отношений ^[6] или отдельных переменных для вершин и рёбер ^{[7] .}

Закон нуля-единицы

Граф Радо — бесконечный граф, который точно моделирует предложения первого порядка, которые почти всегда верны для конечных графов.

Глебский и др. (1969) и, независимо, Фейгин (1976) доказали закон нуля-единицы для логики графов первого порядка; доказательство Фейгина использовало теорему компактности . Согласно этому результату, каждое предложение первого порядка либо почти всегда истинно, либо почти всегда ложно для случайных графов в модели Эрдёша–Реньи . То есть, пусть будет фиксированным предложением первого порядка, и выберем случайный граф -вершин равномерно случайным образом среди всех графов на множестве помеченных вершин. Тогда в пределе, когда стремится к бесконечности, вероятность того, что модели будут стремиться либо к нулю, либо к единице: Более того, существует определенный бесконечный граф, граф Радо , такой, что предложения, моделируемые графом Радо, являются в точности теми, для которых вероятность быть смоделированными случайным конечным графом стремится к единице: Для случайных графов, в которых каждое ребро включено независимо от других с фиксированной вероятностью, тот же результат верен, причем те же предложения имеют вероятности, стремящиеся к нулю или к единице. ^[8] ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle G_{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle G_{n}}$ ${\displaystyle S}$ $${\displaystyle \lim _{n\to \infty }\operatorname {Pr} [G_{n}\models S]\in \{0,1\}.}$$ ${\displaystyle R}$ $${\displaystyle R\models S\quad \Longleftrightarrow \quad \lim _{n\to \infty }\operatorname {Pr} [G_{n}\models S]=1.}$$

Вычислительная сложность определения того, имеет ли данное предложение вероятность, стремящуюся к нулю или к единице, высока: задача является PSPACE-полной . ^[9] Если свойство графа первого порядка имеет вероятность, стремящуюся к единице на случайных графах, то можно перечислить все графы с вершинами, которые моделируют это свойство, с полиномиальной задержкой (как функцией ) на граф. ^[4] ${\displaystyle n}$ ${\displaystyle n}$

Аналогичный анализ можно выполнить для неравномерных случайных графов, где вероятность включения ребра является функцией числа вершин, и где решение о включении или исключении ребра принимается независимо с равной вероятностью для всех ребер. Однако для этих графов ситуация более сложная. В этом случае свойство первого порядка может иметь один или несколько порогов, так что когда вероятность включения ребра ограничена порогом, то вероятность наличия данного свойства стремится к нулю или единице. Эти пороги никогда не могут быть иррациональной степенью , поэтому случайные графы, где вероятность включения ребра является иррациональной степенью, подчиняются закону нуля-единицы, аналогичному закону для равномерно случайных графов. Похожий закон нуля-единицы справедлив для очень разреженных случайных графов, которые имеют вероятность включения ребра с , пока не является суперчастным отношением . ^[10] Если является суперчастным, вероятность наличия данного свойства может стремиться к пределу, который не равен нулю или единице, но этот предел можно эффективно вычислить. ^[11] Существуют предложения первого порядка, которые имеют бесконечно много порогов. ^[12] ${\displaystyle n}$ ${\displaystyle n^{-c}}$ ${\displaystyle c>1}$ ${\displaystyle c}$ ${\displaystyle c}$

Параметризованная сложность

Если предложение первого порядка включает в себя различные переменные, то описываемое им свойство может быть проверено в графах вершин путем проверки всех -кортежей вершин; однако этот алгоритм поиска методом грубой силы не особенно эффективен, занимая время . Проблема проверки того, моделирует ли граф данное предложение первого порядка, включает в себя в качестве особых случаев проблему изоморфизма подграфов (в которой предложение описывает графы, содержащие фиксированный подграф) и проблему клики (в которой предложение описывает графы, содержащие полные подграфы фиксированного размера). Проблема клики сложна для W(1) , первого уровня иерархии сложных задач с точки зрения параметризованной сложности . Поэтому маловероятно, что будет существовать алгоритм с фиксированными параметрами, время выполнения которого принимает вид для функции и константы , которые не зависят от и . ^[13] Более того, если гипотеза экспоненциального времени верна, то поиск клики и проверка модели первого порядка обязательно потребуют времени, пропорционального степени, показатель которой пропорционален . ^[14] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle O(n^{k})}$ ${\displaystyle O(f(k)n^{c})}$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k}$

На ограниченных классах графов проверка моделей предложений первого порядка может быть намного более эффективной. В частности, каждое свойство графа, выражаемое как предложение первого порядка, может быть проверено за линейное время для графов ограниченного расширения . Это графы, в которых все неглубокие миноры являются разреженными графами , с отношением ребер к вершинам, ограниченным функцией глубины минора. Еще более обще, проверка моделей первого порядка может быть выполнена за почти линейное время для нигде не плотных графов, классов графов, для которых на каждой возможной глубине существует по крайней мере один запрещенный неглубокий минор. И наоборот, если проверка моделей является фиксированно-параметрически выполнимой для любого монотонного семейства графов, это семейство должно быть нигде не плотным. ^[15]

Сжатие данных и изоморфизм графов

Говорят, что предложение первого порядка в логике графов определяет граф , если является единственным графом, который моделирует . Каждый граф может быть определен по крайней мере одним предложением; например, можно определить любой -вершинный граф предложением с переменными, по одной для каждой вершины графа, и еще одним, чтобы сформулировать условие, что нет вершин, отличных от вершин графа. Дополнительные предложения предложения могут использоваться для обеспечения того, чтобы никакие две вершинные переменные не были равны, чтобы присутствовало каждое ребро , и чтобы не существовало ребра между парой несмежных вершин . Однако для некоторых графов существуют значительно более короткие предложения, которые определяют граф. ^[16] ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle G}$

Несколько различных инвариантов графа могут быть определены из простейших предложений (с различными мерами простоты), которые определяют данный граф. В частности, логическая глубина графа определяется как минимальный уровень вложенности квантификаторов ( ранг квантификатора ) в предложении, определяющем граф. ^[17] Предложение, описанное выше, вкладывает квантификаторы для всех своих переменных, поэтому оно имеет логическую глубину . Логическая ширина графа - это минимальное количество переменных в предложении, которое его определяет. ^[17] В предложении, описанном выше, это количество переменных снова равно . И логическая глубина, и логическая ширина могут быть ограничены в терминах ширины дерева данного графа. ^[18] Логическая длина, аналогично, определяется как длина кратчайшего предложения, описывающего граф. Предложение, описанное выше, имеет длину, пропорциональную квадрату числа вершин, но можно определить любой граф предложением с длиной, пропорциональной его числу ребер. ^[17] ${\displaystyle n+1}$ ${\displaystyle n+1}$

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

Выполнимость

Как частный случай теоремы Трахтенброта , неразрешимо , может ли данное предложение первого порядка быть реализовано конечным неориентированным графом. Это означает, что ни один алгоритм не может правильно ответить на этот вопрос для всех предложений. ^[20]

Некоторые предложения первого порядка моделируются бесконечными графами, но не любым конечным графом. Например, свойство иметь ровно одну вершину степени один, при этом все остальные вершины имеют степень ровно два, может быть выражено предложением первого порядка. Оно моделируется бесконечным лучом , но нарушает лемму Эйлера о рукопожатии для конечных графов. Однако из отрицательного решения Entscheidungsproblem ( Алонзо Чёрча и Алана Тьюринга в 1930-х годах) следует, что выполнимость предложений первого порядка для графов, которые не ограничены конечностью, остаётся неразрешимой. Также неразрешимо различать предложения первого порядка, которые истинны для всех графов, и те, которые истинны для конечных графов, но ложны для некоторых бесконечных графов. ^[21]

Фиксированная точка

Определим вершину как слабую (выделенную красным), если, за исключением не более одного , каждый из ее соседей является слабым, согласно формуле неподвижной точки . Остальные синие вершины образуют 2-ядро графа. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle W(x)\leftarrow \exists y\forall z{\bigl (}x\sim z\Rightarrow (y=z\vee W(z)){\bigr )}}$

Логики графов, основанные на наименьшей неподвижной точке, расширяют логику графов первого порядка, допуская предикаты (свойства вершин или кортежей вершин), определяемые специальными операторами с фиксированной точкой. Этот тип определения начинается с импликации, формулы, утверждающей, что когда определенные значения предиката истинны, то и другие значения также истинны. «Неподвижная точка» — это любой предикат, для которого это является допустимой импликацией. Может быть много неподвижных точек, включая предикат always-true; «наименьшая неподвижная точка» — это неподвижная точка, которая имеет как можно меньше истинных значений. Точнее, ее истинные значения должны быть подмножеством истинных значений любой другой неподвижной точки. ^[22]

Например, определите быть истинным, когда две вершины и соединены путем в данном графе, и ложным в противном случае. Тогда каждая вершина соединена сама с собой, а когда соединена с соседом , она также соединена еще одним шагом с . Выражая это рассуждение в логических терминах, является наименьшей неподвижной точкой формулы Здесь, быть неподвижной точкой означает, что истинность правой части формулы подразумевает истинность левой части, как предполагает обратная стрелка импликации. Быть наименьшей неподвижной точкой, в этом случае, подразумевает, что никакие две вершины не будут определены как соединенные, если их связность не возникает из повторного использования этой импликации. ^[22] ${\displaystyle C(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle C}$ $${\displaystyle C(u,v)\leftarrow {\Bigl (}(u=v)\vee \exists w{\bigl (}C(u,w)\wedge w\sim v{\bigr )}{\Bigr )}.}$$

Было изучено несколько вариаций логик с фиксированной точкой. В логике с наименьшей фиксированной точкой правая часть оператора в определяющей формуле должна использовать предикат только положительно (то есть каждое появление должно быть вложено в четное число отрицаний), чтобы сделать наименьшую фиксированную точку хорошо определенной. В другом варианте с эквивалентной логической мощностью, инфляционной логике с фиксированной точкой, формула не обязательно должна быть монотонной, но результирующая фиксированная точка определяется как та, которая получена путем многократного применения импликаций, выведенных из определяющей формулы, начиная с предиката all-false. Другие варианты, допускающие отрицательные импликации или несколько одновременно определенных предикатов, также возможны, но не обеспечивают дополнительной дефиниционной мощности. Предикат, определенный одним из этих способов, затем может быть применен к кортежу вершин как часть большего логического предложения. ^[22] ${\displaystyle \leftarrow }$

Логики с фиксированной точкой и расширения этих логик, которые также позволяют целочисленные переменные подсчета, значения которых варьируются от 0 до числа вершин, использовались в дескриптивной сложности в попытке предоставить логическое описание задач принятия решений в теории графов, которые могут быть решены за полиномиальное время . Фиксированная точка логической формулы может быть построена за полиномиальное время с помощью алгоритма, который многократно добавляет кортежи к набору значений, для которых предикат истинен, до достижения фиксированной точки, поэтому решение о том, моделирует ли граф предложение в этой логике, всегда можно решить за полиномиальное время. Не каждое свойство графа с полиномиальным временем может быть смоделировано предложением в логике, которая использует только фиксированные точки и подсчет. ^{[23] [24]} Однако для некоторых специальных классов графов свойства полиномиального времени совпадают со свойствами, выражаемыми в логике с фиксированной точкой с подсчетом. К ним относятся случайные графы, ^{[23] [25]} интервальные графы , ^{[23] [26]} и (через логическое выражение теоремы о структуре графа ) каждый класс графов, характеризующихся запрещенными минорами . ^[23]

Второго порядка

В монадической логике второго порядка графов переменные представляют объекты до четырех типов: вершины, ребра, наборы вершин и наборы ребер. Существует две основные вариации монадической логики второго порядка графа: MSO ₁ , в которой разрешены только переменные вершин и наборов вершин, и MSO _2, в которой разрешены все четыре типа переменных. Предикаты для этих переменных включают проверку равенства, проверку членства и либо инцидентность вершины-ребра (если разрешены как переменные вершины, так и ребра), либо смежность между парами вершин (если разрешены только переменные вершины). Дополнительные вариации в определении допускают дополнительные предикаты, такие как предикаты модульного подсчета. ^[27]

Примеры

Например, связность неориентированного графа может быть выражена в MSO ₁ как утверждение, что для каждого разбиения вершин на два непустых подмножества существует ребро из одного подмножества в другое. Разбиение вершин может быть описано подмножеством вершин на одной стороне разбиения, и каждое такое подмножество должно либо описывать тривиальное разбиение (такое, в котором одна или другая сторона пуста), либо пересекаться ребром. То есть граф связен, когда он моделирует предложение MSO _1. Однако связность не может быть выражена в логике графа первого порядка, и не может быть выражена в экзистенциальном MSO ₁ ( фрагмент MSO ₁ , в котором все квантификаторы множеств являются экзистенциальными и встречаются в начале предложения), ни даже в экзистенциальном MSO _2. ^[28 ] ${\displaystyle S}$ $${\displaystyle \forall S{\Bigl (}\forall x(x\in S)\vee \forall y{\bigl (}\lnot (y\in S){\bigr )}\vee \exists x\exists y{\bigl (}x\in S\wedge \lnot (y\in S)\wedge x\sim y{\bigr )}{\Bigr )}.}$$

Гамильтоновость может быть выражена в MSO ₂ существованием набора ребер, который образует связный 2-регулярный граф на всех вершинах, со связностью, выраженной как выше, и 2-регулярностью, выраженной как инцидентность двух, но не трех различных ребер в каждой вершине. Однако гамильтоновость невыразима в MSO ₁ , поскольку MSO ₁ не способен различать полные двудольные графы с равным числом вершин на каждой стороне двудольного графа (которые являются гамильтоновыми) от несбалансированных полных двудольных графов (которые таковыми не являются). ^[29]

Хотя это и не является частью определения MSO ₂ , ориентации неориентированных графов могут быть представлены с помощью техники, включающей деревья Тремо . Это позволяет также выразить другие свойства графа, включающие ориентации. ^[30]

Теорема Курселя

Согласно теореме Курселя , каждое фиксированное свойство MSO ₂ может быть проверено за линейное время на графах ограниченной древовидной ширины , и каждое фиксированное свойство MSO ₁ может быть проверено за линейное время на графах ограниченной кликовой ширины . ^[31] Версия этого результата для графов ограниченной древовидной ширины также может быть реализована в логарифмическом пространстве . ^[32] Приложения этого результата включают в себя алгоритм с фиксированными параметрами для вычисления числа пересечений графа. ^[33]

Теорема Зееса

Проблема выполнимости для предложения монадической логики второго порядка — это проблема определения, существует ли хотя бы один граф (возможно, в пределах ограниченного семейства графов), для которого предложение истинно. Для произвольных семейств графов и произвольных предложений эта проблема неразрешима. Однако выполнимость предложений MSO ₂ разрешима для графов ограниченной древесной ширины, а выполнимость предложений MSO ₁ разрешима для графов ограниченной кликовой ширины. Доказательство включает использование теоремы Курселя для построения автомата, который может проверить свойство, а затем проверку автомата для определения, существует ли какой-либо граф, который он может принять. В качестве частичного обратного утверждения ^[34] Зезе (1991) доказал, что всякий раз, когда семейство графов имеет разрешимую проблему выполнимости MSO ₂ , семейство должно иметь ограниченную древесную ширину. Доказательство основано на теореме Робертсона и Сеймура о том, что семейства графов с неограниченной древовидной шириной имеют произвольно большие миноры сетки . Сизе также предположил, что каждое семейство графов с разрешимой проблемой выполнимости MSO ₁ должно иметь ограниченную кликовую ширину. ^[35] Это не было доказано, но ослабление гипотезы, которая расширяет MSO ₁ с помощью предикатов модульного подсчета, верно. ^[34]

Примечания

1. Spencer (2001), Раздел 1.2, «Что такое теория первого порядка?», стр. 15–17.
2. Вербицкий и Жуковский (2019).
3. Цейме (2017).
4. Goldberg (1993).
5. Например, Хенсон (1972) требует, чтобы ориентированные графы описывались асимметричным отношением , что означает, что петли и 2-циклы запрещены, что дает ориентированные графы .
6. Концевич (1973).
7. Bruggink & König (2018).
8. Глебский и др. (1969); Фейгин (1976)
9. Гранжан (1983).
10. Шелах и Спенсер (1988); Спенсер (2001).
11. Линч (1992).
12. Спенсер (1990).
13. Дауни и Феллоуз (1995).
14. Чен и др. (2006).
15. Нешетржил и Оссона де Мендес (2012), 18.3 Проблема изоморфизма подграфов и логические запросы, стр. 400–401; Дворжак, Краль и Томас (2010); Гроэ, Крейцер и Зибертц (2014).
16. Пихурко, Спенсер и Вербицкий (2006).
17. Пихурко и Вербицкий (2011).
18. Вербицкий (2005).
19. Иммерман и Ландер (1990).
20. Эббингауз и Флум (1995). Парис (2014) пишет, что этот результат о неразрешимости хорошо известен, и приписывает его Трахтенброту (1950) о неразрешимости выполнимости первого порядка для более общих классов конечных структур.
21. Лавров (1963).
22. Grohe (2017), стр. 23–27.
23. Grohe (2017), стр. 50–51.
24. Кай, Фюрер и Иммерман (1992).
25. Хелла, Колайтис и Луосто (1996).
26. Лобнер (2010).
27. Эти определения можно найти, например, в Courcelle & Engelfriet (2012), стр. 69, под немного отличающимися обозначениями MS ₁ и MS _2. Другие авторы использовали обозначения MSO ₁ и MSO ₂ , и Курсель также стал использовать их позже; см., например, Courcelle (2018).
28. Феджин, Стокмейер и Варди (1995).
29. Курсель и Энгельфрит (2012); Либкин (2004), Следствие 7.24, стр. 126–127.
30. Курсель (1996).
31. Курсель и Энгельфрит (2012).
32. Эльберфельд, Якоби и Тантау (2010).
33. Гроэ (2001); Каварабаяши и Рид (2007).
34. Курсель и Оум (2007).
35. Зеесе (1991).

Ссылки

• Bruggink, HJ Sander; König, Barbara (2018), «Распознаваемые языки стрелок и коспанов», Mathematical Structures in Computer Science , 28 (8): 1290–1332, doi :10.1017/S096012951800018X, MR  3849613, S2CID  52275704
• Cai, Jin-Yi; Fürer, Martin; Immerman, Neil (1992), «Оптимальная нижняя граница числа переменных для идентификации графа», Combinatorica , 12 (4): 389–410, doi :10.1007/BF01305232, MR  1194730
• Чэнь, Цзяньэр; Хуан, Сючжэнь; Кань, Ияд А.; Ся, Ге (2006), «Сильные нижние вычислительные границы с помощью параметризованной сложности», Журнал компьютерных и системных наук , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
• Курсель, Бруно (1996), «О выражении свойств графа в некоторых фрагментах монадической логики второго порядка» (PDF) , в Immerman, Neil ; Kolaitis, Phokion G. (ред.), Proc. Descr. Complex. Finite Models , DIMACS, т. 31, Amer. Math. Soc., стр. 33–62, CiteSeerX  10.1.1.55.5184 , MR  1451381
• Курсель, Бруно ; Энгельфрит, Йост (2012), Структура графа и монадическая логика второго порядка: подход с точки зрения теории языка , Энциклопедия математики и ее приложений, т. 138, Cambridge University Press , ISBN 9781139644006, ЗБЛ  1257.68006
• Курсель, Бруно (2018), «Fly-автоматы для проверки свойств графа MSO _{2 »,} Дискретная прикладная математика , 245 : 236–252, arXiv : 1511.08605 , doi : 10.1016/j.dam.2016.10.018, MR  3804787
• Курсель, Бруно ; Ум, Санг-ил (2007), «Вершинные миноры, монадическая логика второго порядка и гипотеза Сиза» (PDF) , Журнал комбинаторной теории , Серия B, 97 (1): 91–126, doi : 10.1016/j.jctb.2006.04.003 , MR  2278126
• Дауни, Р. Г.; Феллоуз , М. Р. (1995), «Распознаваемость и полнота с фиксированными параметрами. II. О полноте для W[1]», Теоретическая информатика , 141 (1–2): 109–131, doi : 10.1016/0304-3975(94)00097-3
• Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Труды 51-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS 2010) , стр. 133–142, CiteSeerX  10.1.1.170.9781 , doi :10.1109/FOCS.2010.20, ISBN 978-0-7695-4244-7, MR  3024787, S2CID  15264036
• Эббингауз, Хайнц-Дитер; Флум, Йорг (1995), Теория конечных моделей , Springer Monographs in Mathematics (2-е изд.), Springer, стр. 129, doi :10.1007/3-540-28788-4, ISBN 978-3-540-28787-2
• Эльберфельд, Михаэль; Якоби, Андреас; Тантау, Тилл (октябрь 2010 г.), «Версии теорем Бодлендера и Курселя в логпространстве» (PDF) , Труды 51-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS 2010) , стр. 143–152, doi :10.1109/FOCS.2010.21, ISBN 978-1-4244-8525-3, S2CID  1820251
• Фагин, Рональд (1976), «Вероятности конечных моделей», Журнал символической логики , 41 (1): 50–58, doi :10.1017/s0022481200051756, JSTOR  2272945, MR  0476480, S2CID  2563318
• Фагин, Рональд ; Стокмейер, Ларри Дж .; Варди, Моше Й. (1995), «О монадическом NP против монадического co-NP», Информация и вычисления , 120 (1): 78–92, doi : 10.1006/inco.1995.1100 , MR  1340807
• Глебский, Ю. В.; Коган, Д.И.; Лиогонький, М.И.; Таланов В. А. (1969), "Объем и доля выполнимости формул низшего исчисления предикатов", Отделение математики, механики и кибернетики Академии наук Украинской ССР: Кибернетика (2): 17–27, MR  0300882
• Голдберг, Лесли Энн (1993), «Алгоритмы полиномиальной задержки в полиномиальном пространстве для перечисления семейств графов», Труды Двадцать пятого ежегодного симпозиума ACM по теории вычислений (STOC '93) , Нью-Йорк, США: ACM, стр. 218–225, doi :10.1145/167088.167160, ISBN 0-89791-591-7, S2CID  6305108
• Гранжан, Этьен (1983), «Сложность теории первого порядка почти всех конечных структур», Информация и управление , 57 (2–3): 180–204, doi : 10.1016/S0019-9958(83)80043-6 , MR  0742707
• Гроэ, Мартин (2001), «Вычисление чисел пересечений за квадратичное время», Труды тридцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '01) , стр. 231–236, arXiv : cs/0009010 , doi :10.1145/380752.380805, ISBN 1-58113-349-9, S2CID  724544
• Гроэ, Мартин (2017), Описательная сложность, канонизация и теория определяемой структуры графа , Lecture Notes in Logic, т. 47, Cambridge University Press, Кембридж, ISBN 978-1-107-01452-7, г-н  3729479
• Гроэ, Мартин ; Крейцер, Стефан; Зибертц, Себастьян (2014), «Определение свойств первого порядка нигде не плотных графов», Труды 46-го ежегодного симпозиума ACM по теории вычислений (STOC '14) , Нью-Йорк: ACM, стр. 89–98, arXiv : 1311.3899 , doi : 10.1145/2591796.2591851, ISBN 978-1-4503-2710-7, S2CID  13297133
• Хелла, Лаури; Колайтис, Фокион Г.; Луосто, Керкко (1996), «Почти всюду эквивалентность логик в теории конечных моделей», Бюллетень символической логики , 2 (4): 422–443, doi :10.2307/421173, JSTOR  421173, MR  1460316, S2CID  16411368
• Хенсон, К. Уорд (1972), «Счетные однородные реляционные структуры и -категориальные теории», Журнал символической логики , 37 : 494–500, doi : 10.2307/2272734, JSTOR  2272734, MR  0321727, S2CID  40662635 ${\displaystyle \aleph _{0}}$
• Иммерман, Нил ; Ландер, Эрик (1990), «Описание графов: подход первого порядка к канонизации графов», в Selman, Alan L. (ред.), Complexity Theory Retrospective: In honor of Juris Hartmanis on the case his sixteenth birthday , New York: Springer-Verlag, стр. 59–81, doi :10.1007/978-1-4612-4478-3_5, ISBN 978-1-4612-8793-3, МР  1060782
• Лавров, И.А. (1963), «Эффективная неразделимость множества тождественно истинных формул и множества конечно опровержимых формул некоторых элементарных теорий», Алгебра и логика, сем. , 2 (1): 5–18, MR  0157904
• Каварабаяси, Кен-ичи ; Рид, Брюс (2007), «Вычисление числа пересечений за линейное время», Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений (STOC '07) , стр. 382–390, doi :10.1145/1250790.1250848, ISBN 978-1-59593-631-8, S2CID  13000831
• Концевич, Лешек (1973), «Определимость классов графов в исчислении предикатов первого порядка с тождеством», Польская академия наук , 32 : 159–190, doi :10.1007/BF02123839, JSTOR  20014678, MR  0351796, S2CID  189786935
• Лаубнер, Бастиан (2010), «Определение полиномиального времени на интервальных графах», 25-й ежегодный симпозиум IEEE по логике в компьютерных науках (LICS 2010) , Лос-Аламитос, Калифорния: IEEE Computer Society, стр. 199–208, arXiv : 0911.3799 , doi : 10.1109/LICS.2010.42, ISBN 978-1-4244-7588-9, MR  2963094, S2CID  1450409
• Либкин, Леонид (2004), Элементы теории конечных моделей , Тексты по теоретической информатике: Серия EATCS, Springer-Verlag, Берлин, doi : 10.1007/978-3-662-07003-1, ISBN 3-540-21202-7, MR  2102513, S2CID  30176939
• Линч, Джеймс Ф. (1992), «Вероятности предложений о очень разреженных случайных графах», Случайные структуры и алгоритмы , 3 (1): 33–53, doi :10.1002/rsa.3240030105, MR  1139487
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Springer-Verlag, doi : 10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058
• Парис, Павел (2014), «Логика первого порядка на графах CPDA», Информатика — теория и приложения , Lecture Notes in Computer Science , т. 8476, Нью-Йорк: Springer-Verlag, стр. 300–313, doi :10.1007/978-3-319-06686-8_23, ISBN 978-3-319-06685-1, MR  3218557, S2CID  31640587
• Пихурко, Олег; Спенсер, Джоэл ; Вербицкий, Олег (2006), «Краткие определения в теории графов первого порядка», Annals of Pure and Applied Logic , 139 (1–3): 74–109, arXiv : math/0401307 , doi : 10.1016/j.apal.2005.04.003, MR  2206252, S2CID  3041191
• Пихурко, Олег; Вербицкий, Олег (2011), «Логическая сложность графов: обзор», в Grohe, Martin ; Makowsky, Johann A. (ред.), Model Theoretic Methods in Finite Combinatorics (Совместная специальная сессия AMS-ASL, 5-8 января 2009 г., Вашингтон, округ Колумбия) , Contemporary Mathematics, т. 558, Американское математическое общество, стр. 129–180, arXiv : 1003.4865 , ISBN 978-0-8218-8322-8
• Seese, D. (1991), «Структура моделей разрешимых монадических теорий графов», Annals of Pure and Applied Logic , 53 (2): 169–195, doi : 10.1016/0168-0072(91)90054-P , MR  1114848
• Шелах, Сахарон ; Спенсер, Джоэл (1988), «Законы нуля и единицы для разреженных случайных графов», Журнал Американского математического общества , 1 (1): 97–115, doi : 10.2307/1990968 , JSTOR  1990968, MR  0924703
• Спенсер, Джоэл (1990), «Бесконечные спектры в теории графов первого порядка», Combinatorica , 10 (1): 95–102, doi :10.1007/BF02122699, MR  1075070, S2CID  27770505
• Спенсер, Джоэл (2001), Странная логика случайных графов , Алгоритмы и комбинаторика, т. 22, Springer-Verlag, Берлин, doi :10.1007/978-3-662-04538-1, ISBN 3-540-41654-4, г-н  1847951
• Трахтенброт, Б.А. (1950), «Невозможность алгоритма для задачи разрешения для конечных областей», Доклады Академии наук СССР , Новая серия, 70 : 569–572, MR  0033784
• Вербицкий, Олег (2005), «Определимость графов с сепараторами первого порядка с помощью игры Эренфойхта», Теоретическая информатика , 343 (1–2): 158–176, arXiv : math/0401361 , doi : 10.1016/j.tcs.2005.05.003, MR  2168849, S2CID  17886484
• Вербицкий, Олег; Жуковский, Максим (2019), «Жесткие оценки асимптотической описательной сложности изоморфизма подграфов», ACM Transactions on Computational Logic , 20 (2): A9:1–A9:18, arXiv : 1802.02143 , doi : 10.1145/3303881, MR  3942556, S2CID  3603039
• Zeume, Thomas (2017), «Динамическая описательная сложность k-клики» (PDF) , Информация и вычисления , 256 : 9–22, arXiv : 1610.09089 , doi : 10.1016/j.ic.2017.04.005, MR  3705411, S2CID  1412001