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

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

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

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

Первый заказ

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

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

Примеры

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

Проблема изоморфизма подграфов для фиксированного подграфа $H$ спрашивает, есть ли $H$ появляется как подграф большего графа $G$. Это может быть выражено предложением, в котором утверждается существование вершин (по одной на каждую вершину множества). $H$) такой, что для каждого ребра $H$соответствующая пара переменных представляет смежные вершины и такие, что для каждой оставшейся пары вершин $H$соответствующая пара переменных представляет разные вершины; см. иллюстрацию. В качестве частного случая проблема клики (для фиксированного размера клики) может быть выражена предложением, в котором утверждается существование ряда вершин, равных размеру клики, все из которых являются смежными.

Аксиомы

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

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

$\forall u\forall v(u\sim v\Rightarrow v\sim u)$ (края ненаправлены).

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

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

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

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

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

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

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

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

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

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

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

Несколько различных инвариантов графа можно определить из простейших предложений (с разными мерами простоты), определяющих данный граф. В частности, логическая глубина графа определяется как минимальный уровень вложенности кванторов ( ранг квантора ) в предложении, определяющем граф. В предложении, обрисованном выше, квантификаторы для всех его переменных вложены друг в друга, поэтому оно имеет логическую глубину. $n+1$. Логическая ширина графа — это минимальное количество переменных в предложении, которое его определяет. В предложении, изложенном выше, это число переменных снова равно $n+1$. И логическая глубина, и логическая ширина могут быть ограничены шириной дерева данного графа. Логическая длина аналогично определяется как длина кратчайшего предложения, описывающего граф. Описанное выше предложение имеет длину, пропорциональную квадрату числа вершин, но любой граф можно определить с помощью предложения, длина которого пропорциональна числу его ребер.

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

Удовлетворенность

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

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

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

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

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

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

Было изучено несколько вариантов логики с фиксированной точкой. В логике наименьшей фиксированной точки правая часть $\leftarrow$ Оператор в определяющей формуле должен использовать предикат только положительно (то есть каждое появление должно быть вложено в четное число отрицаний), чтобы четко определить наименьшую фиксированную точку.В другом варианте с эквивалентной логической силой, инфляционной логикой фиксированной точки, формула не обязательно должна быть монотонной, но результирующая фиксированная точка определяется как полученная путем многократного применения импликаций, выведенных из определяющей формулы, начиная с предиката «все ложно».Другие варианты, допускающие отрицательные последствия или несколько одновременно определенных предикатов, также возможны, но не обеспечивают дополнительной дефиниционной силы.Предикат, определенный одним из этих способов, затем может быть применен к кортежу вершин как части более крупного логического предложения.

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

Второй заказ

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

Примеры

Например, связность неориентированного графа может быть выражена в MSO ₁ как утверждение, что для каждого разделения вершин на два непустых подмножества существует ребро, ведущее из одного подмножества в другое. Разбиение вершин можно описать подмножеством $S$ вершин на одной стороне разбиения, и каждое такое подмножество должно либо описывать тривиальное разбиение (тот, в котором одна или другая сторона пуста), либо пересекаться ребром. То есть граф связен, когда он моделирует _{MSO 1} предложение . $$\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 ₁ ( фрагмент MSO _1, в котором все кванторы множества являются экзистенциальными и встречаются в начале предложения), ни даже в экзистенциальном MSO ₂ .

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

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

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

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

Теорема Зезе

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

Ссылки

• Бруггинк, Х. Дж. Сандер; Кениг, Барбара (2018), «Узнаваемые языки стрелок и коспанов», Mathematical Structures in Computer Science , 28 (8): 1290–1332, doi : 10.1017/S096012951800018X , MR   3849613 , S2CID   52275704
• Цай, Джин-И; Фюрер, Мартин; Иммерман, Нил (1992), «Оптимальная нижняя граница количества переменных для идентификации графов», Combinatorica , 12 (4): 389–410, doi : 10.1007/BF01305232 , MR   1194730
• Чен, Цзянер; Хуан, Сючжэнь; Кандж, Ияд А.; Ся, Ге (2006), «Сильные вычислительные нижние границы посредством параметризованной сложности», Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
• Курсель, Бруно (1996), «О выражении свойств графа в некоторых фрагментах монадической логики второго порядка» (PDF) , Иммерман, Нил ; Колайтис, Фокион Г. (ред.), Proc. Описание Сложный. Конечные модели , DIMACS, вып. 31, амер. Математика. Soc., стр. 33–62, CiteSeerX   10.1.1.55.5184 , MR   1451381.
• Курсель, Бруно ; Энгельфриет, Йост (2012), Структура графа и монадическая логика второго порядка: теоретико-языковой подход , Энциклопедия математики и ее приложений, том. 138, Издательство Кембриджского университета , ISBN  9781139644006 , Збл   1257.68006
• Курсель, Бруно (2018), «Муха-автоматы для проверки _{MSO 2} свойств графа », Discrete Applied Mathematics , 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 , МР   2278126
• Дауни, РД ; Fellows, MR (1995), «Управляемость и полнота с фиксированными параметрами. II. О полноте для W[1]», Theoretical Computer Science , 141 (1–2): 109–131, doi : 10.1016/0304-3975 (94 )00097-3
• Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , стр. 133–142, CiteSeerX   10.1.1.170.9781 , doi : 10.1109/FOCS.2010.20 , ISBN  978-0-7695-4244-7 , МР   3024787 , S2CID   15264036
• Эббингауз, Хайнц-Дитер; Флум, Йорг (1995), Теория конечных моделей , Монографии Спрингера по математике (2-е изд.), Springer, стр. 129, номер телефона : 10.1007/3-540-28788-4
• Эльберфельд, Майкл; Якоби, Андреас; Тантау, Тилль (октябрь 2010 г.), «Версии в логическом пространстве теорем Бодлендера и Курселя» (PDF) , Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , стр. 143–152, doi : 10.1109/FOCS.2010.21 , S2CID   1820251
• Феджин, Рональд (1976), «Вероятности в конечных моделях» , Journal of Символическая логика , 41 (1): 50–58, doi : 10.1017/s0022481200051756 , JSTOR   2272945 , MR   0476480 , S2CID   2563318
• Феджин, Рональд ; Стокмейер, Ларри Дж .; Варди, Моше Ю. (1995), «О монадическом NP против монадического со-NP», Information and Computation , 120 (1): 78–92, doi : 10.1006/inco.1995.1100 , MR   1340807
• Glebskiĭ, Ju. V.; Kogan, D. I.; Liogon'kiĭ, M. I.; Talanov, V. A. (1969), "Volume and fraction of satisfiability of formulas of the lower predicate calculus", Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskoĭ SSR: Kibernetika (2): 17–27, MR  0300882
• Голдберг, Лесли Энн (1993), «Алгоритмы полиномиальной задержки с полиномиальным пространством для составления списков семейств графов», Труды двадцать пятого ежегодного симпозиума ACM по теории вычислений (STOC '93) , Нью-Йорк, Нью-Йорк, США: ACM, стр. . 218–225, номер домена : 10.1145/167088.167160 , ISBN.  0-89791-591-7 , S2CID   6305108
• Гранжан, Этьен (1983), «Сложность теории первого порядка почти всех конечных структур», Information and Control , 57 (2–3): 180–204, doi : 10.1016/S0019-9958(83)80043-6 , МР   0742707
• Гроэ, Мартин (2001), «Вычисление чисел пересечений в квадратичное время», Труды тридцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '01) , стр. 231–236, arXiv : cs/0009010 , doi : 10.1145 /380752.380805 , S2CID   724544
• Гроэ, Мартин (2017), Описательная сложность, канонизация и определимая теория структуры графов , Конспекты лекций по логике, том. 47, Издательство Кембриджского университета, Кембридж, 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), «Счетные однородные реляционные структуры и $\aleph _{0}$-категориальные теории», Журнал символической логики , 37 : 494–500, doi : 10.2307/2272734 , JSTOR   2272734 , MR   0321727 , S2CID   40662635
• Иммерман, Нил ; Ландер, Эрик (1990), «Описание графов: подход первого порядка к канонизации графов», в Селман, Алан Л. (редактор), Ретроспектива теории сложности: В честь Юриса Хартманиса по случаю его шестидесятилетия , Новый Йорк: Springer-Verlag, стр. 59–81, номер документа : 10.1007/978-1-4612-4478-3_5 , MR   1060782.
• Лавров И.А. (1963), "Эффективная неразделимость множества тождественно истинных формул и множества конечно опровержимых формул для некоторых элементарных теорий", Алгебра и логика сем. , 2 (1): 5–18, МР   0157904
• Каварабаяси, Кеничи ; Рид, Брюс (2007), «Вычисление числа пересечений в линейном времени», Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений (STOC '07) , стр. 382–390, doi : 10.1145/1250790.1250848 , S2CID   13000831
• Концевич, Лешек (1973), «Определимость классов графов в исчислении предикатов первого порядка с единицей», Польская академия наук , 32 : 159–190, doi : 10.1007/BF02123839 , JSTOR   20014678 , MR   0351796 , S2CID   189786935
• Лаубнер, Бастиан (2010), «Захват полиномиального времени на интервальных графиках», 25-й ежегодный симпозиум IEEE по логике в информатике (LICS 2010) , Лос-Аламитос, Калифорния: Компьютерное общество IEEE, стр. 199–208, arXiv : 0911.3799 , doi : 10.1109/LICS.2010.42 , MR   2963094 , S2CID   1450409
• Либкин, Леонид (2004), Элементы теории конечных моделей , Тексты по теоретической информатике: серия EATCS, Springer-Verlag, Берлин, doi : 10.1007/978-3-662-07003-1 , ISBN  3-540-21202-7 , МР   2102513 , S2CID   30176939
• Линч, Джеймс Ф. (1992), «Вероятности предложений об очень разреженных случайных графах», Случайные структуры и алгоритмы , 3 (1): 33–53, doi : 10.1002/rsa.3240030105 , MR   1139487
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Спрингер-Верлаг, номер домена : 10.1007/978-3-642-27875-4 , ISBN.  978-3-642-27874-7 , МР   2920058
• Парис, Павел (2014), «Логика первого порядка на графах CPDA», Информатика - теория и приложения , Конспекты лекций по информатике , том. 8476, Нью-Йорк: Springer-Verlag, стр. 300–313, doi : 10.1007/978-3-319-06686-8_23 , MR   3218557 , S2CID   31640587
• Пихурко Олег; Спенсер, Джоэл ; Вербицкий, Олег (2006), «Краткие определения в теории графов первого порядка», Анналы чистой и прикладной логики , 139 (1–3): 74–109, arXiv : math/0401307 , doi : 10.1016/j.apal .2005.04.003 , МР   2206252 , S2CID   3041191
• Пихурко Олег; Вербицкий, Олег (2011), «Логическая сложность графов: обзор» , Гроэ, Мартин ; Маковски, Иоганн А. (ред.), Теоретико-модельные методы в конечной комбинаторике (совместная специальная сессия AMS-ASL, 5-8 января 2009 г., Вашингтон, округ Колумбия) , Contemporary Mathematics, vol. 558, Американское математическое общество, стр. 129–180, arXiv : 1003.4865 , ISBN.  978-0-8218-8322-8
• Сиз, Д. (1991), «Структура моделей разрешимых монадических теорий графов», Annals of Pure and Applied Logic , 53 (2): 169–195, doi : 10.1016/0168-0072(91)90054- П , МР   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, Шпрингер-Верлаг, Берлин, номер номера : 10.1007/978-3-662-04538-1 , ISBN  3-540-41654-4 , МР   1847951
• Трахтенброт, Б. А. (1950), "Невозможность алгоритма решения проблемы для конечных областей", Доклады Академии наук СССР , Новая серия, 70 : 569–572, MR   0033784
• Вербицкий, Олег (2005), «Определимость графов с разделителями в первом порядке с помощью игры Эренфойхта», Theoretical Computer Science , 343 (1–2): 158–176, arXiv : math/0401361 , doi : 10.1016/j.tcs .2005.05.003 , МР   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
• Зейме, Томас (2017), «Динамическая описательная сложность k -клики» (PDF) , Information and Computation , 256 : 9–22, doi : 10.1016/j.ic.2017.04.005 , MR   3705411 , S2CID   1412001