Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Первый заказ [ править ]

Показанный граф появляется как подграф графа тогда и только тогда, когда . удовлетворяет формуле .

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

Примеры [ править ]

Например, условие, что граф не имеет изолированных вершин, может быть выражено предложением

где символ указывает на неориентированное отношение смежности между двумя вершинами. Это предложение можно интерпретировать как означающее, что для каждой вершины есть другая вершина, которая смежна . [1]

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

Аксиомы [ править ]

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

(граф не может содержать петель ) и
(края неориентированные). [2]

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

Закон нуля или единицы [ править ]

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

Glebski et al. (1969) и, независимо, Фэгин (1976) доказали закон нуля или единицы для логики графов первого порядка; В доказательстве Феджина использовалась теорема компактности . Согласно этому результату каждое предложение первого порядка либо почти всегда истинно, либо почти всегда ложно для случайных графов в модели Эрдеша – Реньи . То есть, пусть S будет фиксированным предложением первого порядка, и выберите случайный граф G n с n вершинами равномерно случайным образом среди всех графов на множестве n помеченных вершин. Тогда в пределе, когда n стремится к бесконечности, вероятность того, что Gn моделей S будут стремиться либо к нулю, либо к единице:

Более того, существует конкретный бесконечный граф, граф Радо R , такой, что предложения, моделируемые графом Радо, являются именно теми, для которых вероятность моделирования случайным конечным графом стремится к единице:

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

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

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

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

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

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

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

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

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

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

Выполнимость [ править ]

Это неразрешимое ли данный первый порядок предложение может быть реализовано с помощью конечного неориентированного графа. [14]

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

Фиксированная точка [ править ]

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

Здесь фиксированная точка означает, что истинность правой части формулы подразумевает истинность левой части (как предполагает обратная стрелка импликации). Наименьшая фиксация означает, что пары вершин, для которыхистинно - это подмножество пар вершин, для которых истинна любая другая фиксированная точка той же формулы. В логике наименьшей фиксированной точки правая часть определяющей формулы должна использовать предикат только положительно (то есть каждое появление должно быть вложено в четное число отрицаний), чтобы сделать наименьшую фиксированную точку хорошо определенной. В эквивалентном варианте, инфляционной логике фиксированной точки, формула не обязательно должна быть монотонной, но результирующая фиксированная точка определяется как полученная путем многократного применения импликаций, полученных из определяющей формулы, начиная с предиката «все ложные». Другие варианты, допускающие отрицательные импликации или несколько одновременно определенных предикатов, также возможны, но не обеспечивают дополнительной определяющей силы. Предикат, определенный одним из этих способов,затем можно применить к кортежу вершин как часть более крупной логической формулы.[16]

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

Второй порядок [ править ]

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

Примеры [ править ]

В качестве примера, связность неориентированного графа может быть выражена в MSO 1 как утверждение, что для каждого разделения вершин на два непустых подмножества существует ребро от одного подмножества к другому. Разбиение вершин можно описать подмножеством S вершин на одной стороне раздела, и каждое такое подмножество должно либо описывать тривиальное разделение (в котором одна или другая сторона пуста), либо пересекаться ребром. То есть график связан, когда он моделирует формулу MSO 1

Однако связность не может быть выражена ни в логике графа первого порядка, ни в экзистенциальном MSO 1 ( фрагмент MSO 1, в котором все квантификаторы набора являются экзистенциальными и встречаются в начале предложения), ни даже в экзистенциальном MSO 2 . [21]

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

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

Теорема Курселя [ править ]

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

Теорема Сизе [ править ]

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

В качестве частичного обращения Seese (1991) доказал, что всякий раз, когда семейство графов имеет разрешимую проблему выполнимости MSO 2 , семейство должно иметь ограниченную древовидную ширину. Доказательство основано на теореме Робертсона и Сеймура о том, что семейства графов с неограниченной шириной дерева имеют сколь угодно большие сеточные миноры . Зее также предположил, что каждое семейство графов с разрешимой проблемой выполнимости MSO 1 должно иметь ограниченную ширину клики; это не было доказано, но ослабление гипотезы о расширении MSO 1 с помощью модульных предикатов подсчета верно. [27]

Заметки [ править ]

  1. ↑ Spencer (2001) , раздел 1.2, «Что такое теория первого порядка?», Стр. 15–17 .
  2. ^ а б Голдберг (1993) .
  3. ^ Гранджин (1983) .
  4. ^ Шела & Спенсер (1988) ; Спенсер (2001) .
  5. ^ Линч (1992) .
  6. ^ Спенсер (1990) .
  7. Перейти ↑ Downey & Fellows (1995) .
  8. ^ Чен и др. (2006) .
  9. ^ Nešetřil & Ossona де Мендес (2012) , 18,3 подграф Изоморфизм Проблема и Boolean Запросы, стр 400-401. Дворжак, Краень и Томас (2010) ; Grohe, Kreutzer & Siebertz (2014) .
  10. ^ Pikhurko, Спенсер и Вербицкий (2006) .
  11. ^ a b c Пихурко и Вербицкий (2011) .
  12. ↑ Вербицкий (2005) .
  13. ^ Иммерман & Ландер (1990) .
  14. ^ Парис (2014) пишет, что этот результат о неразрешимости хорошо известен, и приписывает его Трахтенброту (1950) о неразрешимости выполнимости первого порядка для более общих классов конечных структур.
  15. ↑ Лавров (1963) .
  16. ^ Grohe (2017) , стр. 23-27.
  17. ^ а б в г Grohe (2017) , стр. 50–51.
  18. ^ Cai, фюрер и Иммерман (1992) .
  19. ^ Hella, Kolaitis и Луосто (1996) .
  20. ^ Laubner (2010) .
  21. ^ Феджин, Stockmeyer & Варди (1995) .
  22. ^ Курсель и Энгельфриет (2012) ; Либкин (2004) , следствие 7.24, стр. 126–127 .
  23. ^ Курсель (1996) .
  24. ^ Courcelle & Engelfriet (2012) .
  25. ^ Elberfeld, Jakoby & Tantau (2010) .
  26. ^ Grohe (2001) ; Каварабаяши и Рид (2007) .
  27. ^ Courcelle & Oum (2007) .

Ссылки [ править ]

  • Цай, Цзинь-И; Фюрер, Мартин; Иммерман, Нил (1992), "оптимальный нижняя граница числа переменных для идентификации графа", Combinatorica , 12 (4): 389-410, DOI : 10.1007 / BF01305232 , МР  1194730.
  • Чен, Цзианэр; Хуанг, Сючжэнь; Kanj, Iyad A .; Ся, Ге (2006), "Сильные нижние оценки вычислений с помощью параметризованной сложности", Журнал компьютерных и системных наук , 72 (8): 1346–1367, DOI : 10.1016 / j.jcss.2006.04.007
  • Курсель, Бруно (1996), "О выражении свойств графа в некоторых фрагментах монадической логики второго порядка" (PDF) , в Иммермане, Нил ; Колайтис, Phokion G. (ред.), Proc. Descr. Сложный. Конечные модели , DIMACS, 31 , Amer. Математика. Soc., Стр. 33–62, MR  1451381.
  • Курсель, Бруно ; Энгельфрит, Джуст (2012), Структура графа и монадическая логика второго порядка: теоретико-языковой подход , Энциклопедия математики и ее приложений, 138 , Cambridge University Press , ISBN 9781139644006, Zbl  1257,68006.
  • Курсель, Бруно ; Oum, Sang-иль (2007), "вершинные несовершеннолетний, монадическая логика второго порядка, а также гипотеза по Seese" (PDF) , Журнал комбинаторной теории , серии B, 97 (1): 91-126, DOI : 10.1016 /j.jctb.2006.04.003 , MR  2278126.
  • Дауни, Р.Г .; Стипендиаты, MR (1995), «Последовательность и полнота с фиксированными параметрами. II. О полноте для W [1]», Теоретическая информатика , 141 (1-2): 109-131, DOI : 10.1016 / 0304-3975 (94 ) 00097-3.
  • Дворжак, Зденек ; Krá, Daniel ; Томас, Робин (2010), "Определение свойств первого порядка для разреженных графов", Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , стр. 133–142, MR  3024787.
  • Эльберфельд, Майкл; Якоби, Андреас; Тантау, Тилль (октябрь 2010 г.), "Логпространственные версии теорем Бодлендера и Курселя" (PDF) , Proc. Пятьдесят первый ежегодный IEEE симпозиум по Основы информатики (FOCS 2010) ., Стр 143-152, DOI : 10,1109 / FOCS.2010.21.
  • Феджин, Рональд (1976), "Вероятность на конечных моделях" (PDF) , журнал символической логики , 41 (1): 50-58, DOI : 10,1017 / s0022481200051756 , MR  0476480.
  • Феджин, Рональд ; Стокмейер, Ларри Дж .; Вардите, Моше Ю. (1995), "О монадическом НП против монадического совместно НП", информация и вычисления , 120 (1): 78-92, DOI : 10,1006 / inco.1995.1100 , МР  1340807.
  • Глебский, Ю. V .; Коган Д.И.; Лёгонький, Мичиган; Таланов В.А. (1969), "Объем и доля выполнимости формул нижнего исчисления предикатов", Отделение математики, Механики и кибернетики Академии Наук Украинской ССР: Кибернетика (2): 17–27, MR  0300882.
  • Голдберг, Лесли Энн (1993), "Алгоритмы полиномиального запаздывания в полиномиальном пространстве для перечисления семейств графов", Труды Двадцать пятого ежегодного симпозиума ACM по теории вычислений (STOC '93) , Нью-Йорк, Нью-Йорк, США: ACM, стр. . 218-225, DOI : 10,1145 / 167088,167160 , ISBN 0-89791-591-7.
  • Grandjean, Этьенны (1983), "Сложность теории первого порядка почти все конечных структур", информация и управление , 57 (2-3): 180-204, DOI : 10.1016 / S0019-9958 (83) 80043-6 , Руководство по ремонту  0742707.
  • Grohe, Martin (2001), «Вычисление чисел пересечения в квадратичном времени», Труды тридцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '01) , стр. 231–236, arXiv : cs / 0009010 , doi : 10.1145 /380752.380805.
  • Grohe, Martin (2017), Описательная сложность, канонизация и теория структур определимых графов , Лекционные заметки по логике, 47 , Cambridge University Press, Кембридж, ISBN 978-1-107-01452-7, Руководство по ремонту  3729479.
  • Grohe, Мартин ; Крейцер, Стефан; Сибертц, Себастьян (2014), «Определение свойств первого порядка нигде не плотных графов», Труды 46-го ежегодного симпозиума ACM по теории вычислений (STOC '14) , Нью-Йорк: ACM, стр. 89–98, arXiv : 1311.3899 , DOI : 10.1145 / 2591796.2591851 , ISBN 978-1-4503-2710-7.
  • Хелла, Лаури; Колайтис, Phokion G .; Луосто, Kerkko (1996), "Почти всюду эквивалентность логики в конечной теории моделей", Бюллетень символической логики , 2 (4): 422-443, DOI : 10,2307 / +421173 , МР  1460316.
  • Иммерман, Нил ; Ландер, Эрик (1990), «Описание графов: подход первого порядка к канонизации графов», в Селман, Алан Л. (ред.), Ретроспектива теории сложности: в честь Юриса Хартманиса по случаю его шестидесятилетия , New Йорк:. Springer-Verlag, стр 59-81, DOI : 10.1007 / 978-1-4612-4478-3_5 , МР  1060782.
  • Лавров И.А. (1963), "Эффективная неразделимость множества тождественно истинных формул и множества конечно опровержимых формул для некоторых элементарных теорий", Алгебра и логика сем. , 2 (1): 5–18, MR  0157904
  • Каварабаяси, Кен-ичи ; Рид, Брюс (2007), «Вычисление числа пересечений в линейном времени», Труды тридцать девятой ежегодной ACM симпозиум по теории вычислений (STOC '07) , С. 382-390,. DOI : 10,1145 / 1250790.1250848.
  • Лаубнер, Бастиан (2010), «Захват полиномиального времени на интервальных графах», 25-й ежегодный симпозиум IEEE по логике в компьютерных науках (LICS 2010) , Лос-Аламитос, Калифорния: Компьютерное общество IEEE, стр. 199–208, arXiv : 0911.3799 , doi : 10.1109 / LICS.2010.42 , Руководство по ремонту  2963094.
  • Либкин, Леонид (2004), Элементы теории конечных моделей , Тексты в теоретической информатике: серия EATCS, Springer-Verlag, Берлин, DOI : 10.1007 / 978-3-662-07003-1 , ISBN 3-540-21202-7, Руководство по ремонту  2102513.
  • Линч, Джеймс Ф. (1992), "Вероятность предложений о весьма скудна случайных графах", Случайные Структуры и алгоритмы , 3 (1): 33-53, DOI : 10.1002 / rsa.3240030105 , MR  1139487.
  • Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графики, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Springer-Verlag, DOI : 10.1007 / 978-3-642-27875-4 , hdl : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR  2920058.
  • Парис, Павел (2014), «Логика первого порядка на графах CPDA», Информатика - теория и приложения , Lecture Notes in Computer Science , 8476 , New York: Springer-Verlag, pp. 300–313, doi : 10.1007 / 978 -3-319-06686-8_23 , Руководство по ремонту  3218557.
  • Пихурко Олег; Спенсер, Джоэл ; Вербицкий, Олег (2006), «Краткие определения в теории графов первого порядка», Анналы чистой и прикладной логики , 139 (1–3): 74–109, arXiv : math / 0401307 , doi : 10.1016 / j.apal .2005.04.003 , MR  2206252.
  • Пихурко Олег; Вербицкий, Олег (2011), «Логическая сложность графов: обзор», в Grohe, Martin ; Маковски, Иоганн А. (ред.), Теоретико-модельные методы в конечной комбинаторике (Совместная специальная сессия AMS-ASL, 5-8 января 2009 г., Вашингтон, округ Колумбия) , Contemporary Mathematics, 558 , American Mathematical Society, pp. 129–180.
  • Seese, D. (1991), "Структура моделей разрешимой монадической теории графов", Анналы чистой и прикладная логика , 53 (2): 169-195, DOI : 10,1016 / 0168-0072 (91) 90054- П , Руководство по ремонту  1114848.
  • Шела, Сахарон ; Spencer, Джоэл (1988), "Ноль-один законы для разреженных случайных графов", журнал Американского математического общества , 1 (1): 97-115, DOI : 10,2307 / 1990968 , MR  0924703.
  • Спенсер, Джоуль (1990), "Бесконечные спектры в теории первого порядка графов", Combinatorica , 10 (1): 95-102, DOI : 10.1007 / BF02122699 , МР  1075070.
  • Спенсер, Джоэл (2001), Странная логика случайных графов , алгоритмов и комбинаторики, 22 , Springer-Verlag, Берлин, DOI : 10.1007 / 978-3-662-04538-1 , ISBN 3-540-41654-4, MR  1847951.
  • Трахтенброт, Б.А. (1950), "Невозможность алгоритма решения проблемы для конечных областей", Доклады Академии Наук СССР (НС) , 70 : 569–572, MR  0033784.
  • Вербицкий, Олег (2005), "Первая формульность графов с разделителями через игру эренфойхтовой", Теоретическая информатика , 343 (1-2): 158-176, DOI : 10.1016 / j.tcs.2005.05.003 , MR  2168849.