Logika grafów

W matematycznych dziedzinach teorii grafów i teorii modeli skończonych logika grafów zajmuje się formalną specyfikacją właściwości grafów za pomocą zdań logiki matematycznej . Istnieje kilka odmian typów operacji logicznych, których można użyć w tych zdaniach. Logika grafów pierwszego rzędu dotyczy zdań, w których zmienne i predykaty dotyczą poszczególnych wierzchołków i krawędzi grafu, podczas gdy monadyczna logika grafów drugiego rzędu umożliwia kwantyfikację na zbiorach wierzchołków lub krawędzi. Logika oparta na najmniejszego punktu stałego dopuszczają bardziej ogólne predykaty na krotkach wierzchołków, ale te predykaty można konstruować tylko za pomocą operatorów punktu stałego, co ogranicza ich moc.

Zdanie może być $niektórych$ wykresów, a fałszywe dla innych; mówi się, że $wykres$ modeluje $,$ napisany , jeśli $jest prawdziwy w$$displaystyle$ i relacji $}$$\displaystyle G}$ . Algorytmiczny problem sprawdzania modeli dotyczy sprawdzania, czy dany graf modeluje dane zdanie. Problem algorytmiczny spełnialność dotyczy sprawdzenia, czy istnieje graf modelujący dane zdanie. Chociaż zarówno sprawdzanie modelu, jak i spełnialność są ogólnie trudne, kilka głównych meta-twierdzeń algorytmicznych pokazuje, że właściwości wyrażone w ten sposób można skutecznie przetestować dla ważnych klas grafów.

Inne tematy badań w logice grafów obejmują badanie prawdopodobieństwa, że ​​graf losowy ma właściwość określoną w ramach określonego typu logiki oraz metody kompresji danych oparte na znajdowaniu zdań logicznych, które są modelowane przez unikalny graf.

Pierwsze zamówienie

$się$ jako podgraf wykresu nieskierowanego $wtedy$ i tylko wtedy, gdy ${\ Displaystyle \ istnieje x_ {1}, x_ {2}, x_ {3}, x_ {4}.}$ zdanie sol ${\ Displaystyle x_ {1} \ sim x_ {2}}$${\ Displaystyle \ ląd }$ ${\ Displaystyle x_ {2} \ sim x_ {3}}$${\ Displaystyle \ ziemia}$${\ Displaystyle x_ {3} \ sim x_ {1}}$${\ Displaystyle \ ziemia}$${\ Displaystyle x_ {3} \ sim x_ {4}}$${\ Displaystyle \ ziemia}$${\ Displaystyle x_ {1} \ neq x_ {4}}$${\ Displaystyle \ ziemia}$${\ Displaystyle x_ {2} \ neq x_ {4}}$ .

W logice grafów pierwszego rzędu właściwość grafu jest wyrażana jako skwantyfikowane zdanie logiczne, którego zmienne reprezentują wierzchołki grafu , z predykatami do testowania równości i sąsiedztwa.

Przykłady

Na przykład warunek, że graf nie ma izolowanych wierzchołków, można wyrazić zdaniem

$${\ Displaystyle \ forall u \ istnieje v (u \ sim v)}$$

gdzie symbol wskazuje na $. To$ relację sąsiedztwa między dwoma wierzchołkami $displaystyle$ można interpretować w ten sposób, że dla każdego wierzchołka $istnieje$ inny wierzchołek , który sąsiaduje z $u}$ .

Problem izomorfizmu podgrafu $. Można$$ustalonego$ podgrafu , czy $pojawia się$ jako większego wykresu $)$ wyrazić zdaniem, które stwierdza istnienie wierzchołków (po jednym dla każdego wierzchołka $tak$ , że dla każdej krawędzi para zmiennych reprezentuje sąsiednie wierzchołki i takie że dla każdej pozostałej pary wierzchołków ${\ displaystyle H}$ odpowiednia para zmiennych reprezentuje różne wierzchołki; patrz ilustracja. W szczególnym przypadku problem kliki (dla ustalonej wielkości kliki) można wyrazić zdaniem, które stwierdza istnienie liczby wierzchołków równej wielkości kliki, z których wszystkie są sąsiadujące.

Aksjomaty

W przypadku prostych grafów nieskierowanych teoria grafów pierwszego rzędu obejmuje aksjomaty

${\ Displaystyle \ forall u {\ bigl (} \ lnot (u \ sim u) {\ bigr)}}$ (wykres nie może zawierać żadnych pętli ) i

${\ Displaystyle \ forall u \ forall v (u \ sim v \ Strzałka w prawo v \ sim u)}$ (krawędzie są nieukierunkowane).

Inne typy grafów, takie jak grafy skierowane , mogą obejmować różne aksjomaty, a logiczne sformułowania właściwości multigrafów wymagają specjalnej obsługi, takiej jak posiadanie wielu relacji krawędzi lub oddzielnych zmiennych dla wierzchołków i krawędzi.

Prawo zero-jedynkowe

Wykres Rado , nieskończony graf, który dokładnie modeluje zdania pierwszego rzędu, które prawie zawsze są prawdziwe w przypadku grafów skończonych

Glebskii i in. (1969) i niezależnie Fagin (1976) udowodnili zero-jedynkowe prawo dla logiki grafów pierwszego rzędu; Dowód Fagina wykorzystywał twierdzenie o zwartości . Zgodnie z tym wynikiem każde zdanie pierwszego rzędu jest albo prawie zawsze prawdziwe, albo prawie zawsze fałszywe dla losowych grafów w modelu Erdősa – Rényiego . To znaczy, niech $rzędu$ i wybierz losowy wykres wierzchołków ${\ displaystyle n$${\ displaystyle G_ {n}} równomiernie$$wierzchołków$ spośród wszystkich wykresów na zbiorze oznaczonych . Następnie w granicy, gdy $nieskończoności,$ prawdopodobieństwo, że modele będą dążyć do zera lub do jednego: $}$${n}$

$${\ Displaystyle \ lim _ {n \ do \ infty} \ nazwa operatora {Pr} [G_ {n} \ modele S] \ w \ {0,1 \}.}$$

Co więcej, istnieje określony wykres nieskończony, wykres Rado , taki że zdania modelowane przez wykres Rado są dokładnie tymi, dla których prawdopodobieństwo modelowania przez losowy wykres skończony dąży do jedności: R {\ displaystyle $}$

$${\ Displaystyle R \ modele S \ quad \ Longleftrightarrow \ quad \ lim _ {n \ do \ infty} \ operatorname {Pr} [G_ { n}\modele S]=1.}$$

W przypadku grafów losowych, w których każda krawędź jest zawarta niezależnie od innych z ustalonym prawdopodobieństwem, ten sam wynik jest prawdziwy, z tymi samymi zdaniami, których prawdopodobieństwa dążą do zera lub do jednego.

Złożoność obliczeniowa określania, czy dane zdanie ma prawdopodobieństwo dążące do zera, czy do jednego, jest wysoka: problem jest PSPACE-complete . Jeśli właściwość wykresu pierwszego rzędu ma prawdopodobieństwo dążące do jedności na $wykresach$ losowych, to możliwe jest wypisanie wszystkich wykresów wierzchołków, które modelują tę właściwość, z wielomianowym (jako funkcja ${\ displaystyle n} n}$ ) na wykres.

Podobną analizę można przeprowadzić dla niejednorodnych grafów losowych, w których prawdopodobieństwo włączenia krawędzi jest funkcją liczby wierzchołków, a decyzja o włączeniu lub wykluczeniu krawędzi jest podejmowana niezależnie z równym prawdopodobieństwem dla wszystkich krawędzi. Jednak w przypadku tych wykresów sytuacja jest bardziej skomplikowana. W tym przypadku właściwość pierwszego rzędu może mieć jeden lub więcej progów, tak że gdy prawdopodobieństwo włączenia krawędzi jest ograniczone od progu, wówczas prawdopodobieństwo posiadania danej właściwości dąży do zera lub jednego. Te progi nigdy nie mogą być irracjonalną potęgą ${\ displaystyle n}$ , więc losowe wykresy, w których prawdopodobieństwo włączenia krawędzi jest niewymierną potęgą, podlegają prawu zero-jedynkowemu analogicznemu do tego dla grafów jednostajnie losowych. Podobne prawo zero-jedynkowe obowiązuje dla bardzo rzadkich grafów losowych, których prawdopodobieństwo włączenia krawędzi wynosi ${\ displaystyle n ^ {-c}}$ z ${\ displaystyle c> 1}$ , o ile do {\ displaystyle $} displaystyle c}$ nie jest stosunkiem nadrzędnym . jeśli do $\ displaystyle c}$ jest nadrzędny, prawdopodobieństwo posiadania danej właściwości może dążyć do granicy, która nie jest równa zeru ani jedynki, ale granicę tę można skutecznie obliczyć. Istnieją zdania pierwszego rzędu, które mają nieskończenie wiele progów.

Złożoność parametryczna

Jeśli zdanie pierwszego rzędu zawiera $różne$ zmienne, to opisaną przez nie właściwość można przetestować na wykresach $displaystyle$ , badając wszystkie krotki wierzchołków; $k}$ jednak ten algorytm wyszukiwania brutalną siłą nie jest szczególnie wydajny i zajmuje dużo czasu. ${\ Displaystyle O (n ^ {k})}$ . Problem sprawdzenia, czy graf modeluje dane zdanie pierwszego rzędu, obejmuje jako przypadki szczególne problem izomorfizmu podgrafu (w którym zdanie opisuje grafy zawierające ustalony podgraf) oraz problem kliki (w którym zdanie opisuje grafy zawierające pełne podgrafy o ustalonej wielkości). Problem kliki jest trudny dla W(1) , pierwszego poziomu hierarchii problemów trudnych z punktu widzenia złożoności parametrycznej . Dlatego jest mało prawdopodobne, aby istniał algorytm o stałych parametrach, którego czas działania przyjmuje postać ${\ Displaystyle O (f (k) n ^ {c})}$ dla funkcji i stałej ${\ displaystyle$$}$ , które są niezależne od ${\ displaystyle k}$ i ${\ displaystyle n}$ . Co więcej, jeśli hipoteza czasu wykładniczego jest prawdziwa, to znajdowanie klik i sprawdzanie modeli pierwszego rzędu wymagałoby czasu proporcjonalnego do potęgi, której wykładnik jest proporcjonalny do $}$$\ displaystyle k$ .

W ograniczonych klasach grafów sprawdzanie modeli zdań pierwszego rzędu może być znacznie wydajniejsze. W szczególności każdą właściwość grafu, którą można wyrazić jako zdanie pierwszego rzędu, można przetestować w czasie liniowym dla wykresów o ograniczonej ekspansji . Są to grafy, w których wszystkie płytkie drugorzędne są grafami rzadkimi , ze stosunkiem krawędzi do wierzchołków ograniczonym funkcją głębokości mniejszej. Jeszcze bardziej ogólnie, sprawdzanie modelu pierwszego rzędu można przeprowadzić w czasie prawie liniowym dla grafów nigdzie niegęstych, klas grafów, dla których na każdej możliwej głębokości istnieje co najmniej jeden zabroniony płytki mniejszy. I odwrotnie, jeśli sprawdzanie modelu jest wykonalne dla dowolnej monotonicznej rodziny grafów, rodzina ta musi być nigdzie gęsta.

Kompresja danych i izomorfizm grafu

$modeluje$$, że$$wykresów$ pierwszego rzędu w definiuje wykres, $jeśli$ jest jedynym wykresem, który Każdy wykres może być zdefiniowany przez co najmniej jedno zdanie; na przykład można zdefiniować dowolny wykres -vertex ${ \ displaystyle$$}$ za pomocą zdania z ${\ displaystyle n + 1}$ zmienne, po jednej dla każdego wierzchołka wykresu i jeszcze jedna, aby określić warunek, że nie ma innego wierzchołka niż $wykresu$ . Można zastosować dodatkowe klauzule zdania, aby upewnić się, że żadne dwie zmienne wierzchołków nie są równe, że każda krawędź $G}$ obecna i nie istnieje żadna krawędź między parą niesąsiadujących wierzchołków $displaystyle$ . Jednak dla niektórych grafów istnieją znacznie krótsze zdania definiujące graf.

Z najprostszych zdań (o różnych miarach prostoty) definiujących dany graf można zdefiniować kilka różnych niezmienników grafu. W szczególności głębokość logiczna grafu jest definiowana jako minimalny poziom zagnieżdżenia kwantyfikatorów ( ranga kwantyfikatora ) w zdaniu definiującym graf. Zdanie przedstawione powyżej zagnieżdża kwantyfikatory dla wszystkich swoich zmiennych, więc ma logiczną głębię. ${\ displaystyle n + 1}$ . Logiczna szerokość wykresu to minimalna liczba zmiennych w zdaniu, które go definiuje. W zdaniu przedstawionym powyżej ta liczba zmiennych wynosi ponownie ${\ displaystyle n + 1}$ . Zarówno głębokość logiczna, jak i szerokość logiczna mogą być ograniczone pod względem szerokości drzewa danego grafu. Długość logiczna, analogicznie, definiowana jest jako długość najkrótszego zdania opisującego graf. Opisane powyżej zdanie ma długość proporcjonalną do kwadratu liczby wierzchołków, ale można zdefiniować dowolny wykres za pomocą zdania o długości proporcjonalnej do liczby jego krawędzi.

Wszystkie drzewa i większość grafów można opisać za pomocą zdań pierwszego rzędu zawierających tylko dwie zmienne, ale rozszerzonych o zliczanie predykatów. Dla grafów, które w tej logice można opisać zdaniami o ustalonej stałej liczbie zmiennych, można znaleźć kanonizację grafu w czasie wielomianowym (z wykładnikiem wielomianu równym liczbie zmiennych). Porównując kanonizacje, możliwe jest rozwiązanie problemu izomorfizmu grafów dla tych grafów w czasie wielomianowym.

Satysfakcja

Nie można rozstrzygnąć , czy dane zdanie pierwszego rzędu może być zrealizowane przez skończony graf nieskierowany. Oznacza to, że żaden algorytm nie może poprawnie odpowiedzieć na to pytanie dla wszystkich zdań.

Niektóre zdania pierwszego rzędu są modelowane przez grafy nieskończone, ale nie przez dowolny graf skończony. Na przykład właściwość posiadania dokładnie jednego wierzchołka stopnia pierwszego, przy czym wszystkie inne wierzchołki mają stopień dokładnie drugiego stopnia, można wyrazić w zdaniu pierwszego rzędu. Jest modelowany przez nieskończony promień , ale narusza lemat Eulera dotyczący uzgadniania dla grafów skończonych. Wynika to jednak z negatywnego rozwiązania problemu Entscheidungsproblem (autorstwa Alonzo Churcha i Alana Turinga w latach trzydziestych XX wieku), że spełnialność zdań pierwszego rzędu dla grafów, które nie są ograniczone do skończoności, pozostaje nierozstrzygalna. Nierozstrzygalne jest również rozróżnienie między zdaniami pierwszego rzędu, które są prawdziwe dla wszystkich grafów, a tymi, które są prawdziwe dla grafów skończonych, ale fałszywe dla niektórych grafów nieskończonych.

Punkt stały

Zdefiniuj wierzchołek $.$$czerwono$ ), jeśli z co najwyżej jednym wyjątkiem $z$ jego sąsiadów słaby, zgodnie z punktem stałym formuła ${\ Displaystyle W (x) \ leftarrow \ istnieje y \ forall z {\ bigl (} x \ sim z \ Rightarrow (y = z \ vee W (z)) {\ bigr)}}$ . Pozostałe niebieskie wierzchołki tworzą 2-rdzeniowy wykres.

Logiki grafów oparte na najmniejszych punktach stałych rozszerzają logikę grafów pierwszego rzędu, dopuszczając predykaty (właściwości wierzchołków lub krotki wierzchołków) zdefiniowane przez specjalne operatory punktów stałych. Ten rodzaj definicji zaczyna się od implikacji, formuły stwierdzającej, że gdy pewne wartości predykatu są prawdziwe, to inne wartości również są prawdziwe. „Stały punkt” to dowolny predykat, dla którego jest to ważna implikacja. Może istnieć wiele stałych punktów, w tym predykat zawsze prawdziwy; „najmniejszy stały punkt” to stały punkt, który ma jak najmniej prawdziwych wartości. Dokładniej, jego prawdziwe wartości powinny być podzbiorem prawdziwych wartości dowolnego innego punktu stałego.

Na przykład zdefiniuj, ${\ Displaystyle C (u,$$, v$ , gdy dwa wierzchołki $u$ są połączone ścieżką na danym wykresie, do i fałszywe w przeciwnym razie. Następnie każdy wierzchołek jest połączony ze sobą, a kiedy $,$ połączony z sąsiadem jest również połączony jeszcze jednym krokiem do $displaystyle$$v}$ . Wyrażając to rozumowanie w kategoriach logicznych, jest najmniej stałym $wzoru$

$${\ Displaystyle C (u, v) \ leftarrow {\ Bigl (} (u = v) \ vee \ istnieje w {\ bigl (} C (u, w) \ klin w \ sim v {\ bigr)}} większy )}.}$$

Tutaj bycie punktem stałym oznacza, że ​​prawdziwość prawej strony formuły implikuje prawdziwość lewej strony, jak sugeruje strzałka odwróconej implikacji. Bycie najmniej stałym punktem w tym przypadku oznacza, że ​​żadne dwa wierzchołki nie zostaną zdefiniowane jako połączone, chyba że ich łączność wynika z wielokrotnego użycia tej implikacji.

Zbadano kilka odmian logiki punktu stałego. W logice najmniejszego punktu stałego, prawa strona ${\ displaystyle \ leftarrow}$ operator we wzorze definiującym musi używać predykatu tylko dodatnio (to znaczy, każdy wygląd powinien być zagnieżdżony w parzystej liczbie negacji), aby dobrze zdefiniować najmniej stały punkt. W innym wariancie o równoważnej mocy logicznej, inflacyjnej logice punktu stałego, formuła nie musi być monotoniczna, ale wynikowy punkt stały jest definiowany jako uzyskany przez wielokrotne stosowanie implikacji wyprowadzonych z formuły definiującej, zaczynając od całkowicie fałszywego predykatu. Możliwe są również inne warianty, dopuszczające negatywne implikacje lub wiele jednocześnie zdefiniowanych predykatów, ale nie zapewniają one dodatkowej mocy definicyjnej. Predykat zdefiniowany w jeden z tych sposobów można następnie zastosować do krotki wierzchołków jako część większego zdania logicznego.

Logiki punktu stałego i rozszerzenia tych logik, które umożliwiają również zliczanie liczb całkowitych zmiennych, których wartości wahają się od 0 do liczby wierzchołków, zostały użyte w złożoności opisowej , próbując zapewnić logiczny opis problemów decyzyjnych w teorii grafów, które można rozstrzygnąć w czasie wielomianowym . Stały punkt formuły logicznej można zbudować w czasie wielomianowym za pomocą algorytmu, który wielokrotnie dodaje krotki do zbioru wartości, dla których predykat jest prawdziwy, aż do osiągnięcia stałego punktu, więc podjęcie decyzji, czy wykres modeluje zdanie w tej logice, może zawsze rozstrzygane w czasie wielomianowym. Nie każdą właściwość wykresu czasowego wielomianu można modelować za pomocą zdania w logice, która wykorzystuje tylko stałe punkty i liczenie. Jednak dla niektórych specjalnych klas grafów właściwości czasu wielomianowego są takie same, jak właściwości wyrażalne w logice stałoprzecinkowej z liczeniem. Należą do nich wykresy losowe, wykresy interwałowe oraz (poprzez logiczne wyrażenie twierdzenia o strukturze grafów ) każdą klasę grafów charakteryzującą się zabronionymi drugorzędnymi .

Drugie zamówienie

W monadycznej logice grafów drugiego rzędu zmienne reprezentują obiekty maksymalnie czterech typów: wierzchołki, krawędzie, zbiory wierzchołków i zbiory krawędzi. Istnieją dwie główne odmiany logiki grafów monadycznych drugiego rzędu: MSO ₁ , w której dozwolone są tylko zmienne wierzchołków i zbiorów wierzchołków, oraz MSO ₂ , w której dozwolone są wszystkie cztery typy zmiennych. Predykaty dotyczące tych zmiennych obejmują testowanie równości, testowanie członkostwa i występowanie wierzchołków-krawędzi (jeśli dozwolone są zarówno zmienne wierzchołków, jak i krawędzi) lub przyleganie między parami wierzchołków (jeśli dozwolone są tylko zmienne wierzchołków). Dodatkowe odmiany definicji pozwalają na dodatkowe predykaty, takie jak modułowe predykaty liczenia.

Przykłady

Na przykład łączność grafu nieskierowanego można wyrazić w MSO ₁ jako stwierdzenie, że dla każdego podziału wierzchołków na dwa niepuste podzbiory istnieje krawędź z jednego podzbioru do drugiego. Podział wierzchołków można opisać podzbiorem $być$ po jednej stronie podziału, a każdy taki podzbiór powinien albo opisywać podział trywialny (taki, w którym jedna lub druga strona jest pusta), albo przecięty krawędzią. Oznacza to, że graf jest spójny, gdy modeluje zdanie MSO ₁

$${\ Displaystyle \ forall S {\ Bigl (} \ forall x (x \ in S) \ vee \ forall y {\ bigl (} \ lnot (y \ in S) {\ bigr)} \ vee \ istnieje x \ istnieje y{\bigl (}x\in S\klin \lnot (y\in S)\klin x\sim y{\bigr )}{\Bigr )}.}$$

Jednak łączność nie może być wyrażona w logice grafu pierwszego rzędu, ani w egzystencjalnym MSO ₁ ( fragmencie MSO ₁ , w którym wszystkie kwantyfikatory zestawu są egzystencjalne i występują na początku zdania), ani nawet egzystencjalnym MSO ₂ .

Hamiltonowość można wyrazić w MSO ₂ przez istnienie zestawu krawędzi, który tworzy spójny graf 2-regularny na wszystkich wierzchołkach, z łącznością wyrażoną jak powyżej i 2-regularnością wyrażoną jako występowanie dwóch, ale nie trzech różnych krawędzi na każdym wierzchołek. Jednak hamiltoniczność nie jest wyrażalna w MSO ₁ , ponieważ MSO ₁ nie jest w stanie odróżnić kompletnych grafów dwudzielnych z równą liczbą wierzchołków po każdej stronie bipartycji (które są hamiltonowskie) od niezrównoważonych kompletnych grafów dwudzielnych (które nie są).

Chociaż nie jest to częścią definicji MSO ₂ , orientacje grafów nieskierowanych można przedstawić techniką obejmującą drzewa Trémaux . Pozwala to również na wyrażenie innych właściwości wykresu obejmujących orientacje.

Twierdzenie Courcelle'a

Zgodnie z twierdzeniem Courcelle'a każdą ustaloną właściwość MSO ₂ można przetestować w czasie liniowym na wykresach o ograniczonej szerokości drzewa , a każdą ustaloną właściwość MSO ₁ można przetestować w czasie liniowym na wykresach o ograniczonej szerokości kliki . Wersję tego wyniku dla grafów o ograniczonej szerokości drzewa można również zaimplementować w przestrzeni logarytmicznej . Zastosowania tego wyniku obejmują wykonalny algorytm o stałych parametrach do obliczania liczby przecięć wykresu.

Twierdzenie Seese'a

Problem spełnialności dla zdania monadycznej logiki drugiego rzędu to problem ustalenia, czy istnieje co najmniej jeden wykres (prawdopodobnie w ograniczonej rodzinie grafów), dla którego zdanie jest prawdziwe. Dla dowolnych rodzin grafów i dowolnych zdań problem ten jest nierozstrzygalny . Jednak spełnialność zdań MSO ₂ jest rozstrzygalna dla grafów o ograniczonej szerokości drzewa, a spełnialność zdań MSO ₁ zdania są rozstrzygalne dla grafów o ograniczonej szerokości kliki. Dowód obejmuje użycie twierdzenia Courcelle'a do zbudowania automatu, który może przetestować tę właściwość, a następnie zbadanie automatu w celu ustalenia, czy istnieje jakikolwiek wykres, który może zaakceptować. Jako częściowa odwrotność, Seese (1991) udowodnił, że ilekroć rodzina grafów ma rozstrzygalny problem spełnialności MSO ₂ , rodzina musi mieć ograniczoną szerokość drzewa. Dowód opiera się na twierdzeniu Robertsona i Seymoura, że ​​rodziny grafów o nieograniczonej szerokości drzewa mają dowolnie duże drugorzędne siatki . Seese przypuszczał również, że każda rodzina grafów z rozstrzygalnym problemem spełnialności MSO ₁ musi mieć ograniczoną szerokość kliki. Nie zostało to udowodnione, ale osłabienie hipotezy, która rozszerza MSO ₁ o modułowe predykaty liczenia, jest prawdziwe.

Notatki

•    Bruggink, HJ Sander; König, Barbara (2018), „Rozpoznawalne języki strzałek i cospanów”, Struktury matematyczne w informatyce , 28 (8): 1290–1332, doi : 10.1017 / S096012951800018X , MR 3849613 , S2CID 52275704
•   Cai, Jin-Yi; Furer, Martin; Immerman, Neil (1992), „Optymalna dolna granica liczby zmiennych do identyfikacji wykresów”, Combinatorica , 12 (4): 389–410, doi : 10.1007 / BF01305232 , MR 1194730
• Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), „Silne dolne granice obliczeniowe poprzez parametryzowaną złożoność”, Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
•    Courcelle, Bruno (1996), „O wyrażaniu właściwości wykresu w niektórych fragmentach monadycznej logiki drugiego rzędu” (PDF) , w: Immerman, Neil ; Kolaitis, Phokion G. (red.), Proc. opis Złożony. Modele skończone , DIMACS, tom. 31, ameryk. Matematyka Soc., s. 33–62, CiteSeerX 10.1.1.55.5184 , MR 1451381
•    Courcelle, Bruno ; Engelfriet, Joost (2012), Struktura grafów i logika monadyczna drugiego rzędu: podejście teoretyczne do języka , Encyklopedia matematyki i jej zastosowań, tom. 138, Cambridge University Press , ISBN 9781139644006 , Zbl 1257.68006
•   Courcelle, Bruno (2018), „Fly-automaty do sprawdzania właściwości wykresu MSO _{2 ”,} Discrete Applied Mathematics , 245 : 236–252, doi : 10.1016/j.dam.2016.10.018 , MR 3804787
•   Courcelle, Bruno ; Oum, Sang-il (2007), „Vertex-minors, monadyczna logika drugiego rzędu i przypuszczenie Seese” (PDF) , Journal of Combinatorial Theory , Seria B, 97 (1): 91–126, doi : 10.1016 /j.jctb.2006.04.003 , MR 2278126
• Downey, RG ; Stypendyści, MR (1995), „Ustalalność parametrów i kompletność. II. O kompletności dla W [1]”, Teoretyczna informatyka , 141 (1–2): 109–131, doi : 10,1016 / 0304-3975 (94 )00097-3
•      Dvořák, Zdeněk ; Kraľ, Daniel ; Thomas, Robin (2010), „Decydowanie o właściwościach pierwszego rzędu dla rzadkich grafów”, Proc. 51. doroczne sympozjum IEEE na temat podstaw informatyki (FOCS 2010) , s. 133–142, CiteSeerX 10.1.1.170.9781 , doi : 10.1109/FOCS.2010.20 , ISBN 978-0-7695-4244-7 , MR 3024787 , S2CID 15264036
•   Elberfeld, Michael; Jakub, Andreas; Tantau, Till (październik 2010), „Wersje logarytmiczne twierdzeń Bodlaendera i Courcelle” (PDF) , Proc. 51. doroczne sympozjum IEEE na temat podstaw informatyki (FOCS 2010) , s. 143–152, doi : 10.1109/FOCS.2010.21 , S2CID 1820251
•     Fagin, Ronald (1976), „Prawdopodobieństwa modeli skończonych” , Journal of Symbolic Logic , 41 (1): 50–58, doi : 10.1017 / s0022481200051756 , JSTOR 2272945 , MR 0476480 , S2CID 2563318
•   Fagin, Ronald ; Stockmeyer, Larry J .; Vardi, Moshe Y. (1995), „O monadycznej NP vs monadycznej współ-NP”, Information and Computation , 120 (1): 78–92, doi : 10.1006 / inco.1995.1100 , MR 1340807
•   Glebski, Ju. W.; Kogan, DI; Liogon'kiĭ, MI; Talanov, VA (1969), „Objętość i ułamek spełnialności formuł dolnego rachunku predykatów”, Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskoĭ SSR: Kibernetika (2): 17–27, MR 0300882
•    Goldberg, Leslie Ann (1993), „Algorytmy opóźnień wielomianowych w przestrzeni wielomianowej do wyświetlania rodzin grafów”, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC '93) , Nowy Jork, NY, USA: ACM, s. 218–225, doi : 10.1145/167088.167160 , ISBN 0-89791-591-7 , S2CID 6305108
•   Grandjean, Étienne (1983), „Złożoność teorii pierwszego rzędu prawie wszystkich skończonych struktur”, Information and Control , 57 (2–3): 180–204, doi : 10.1016 / S0019-9958 (83) 80043-6 , MR 0742707
•   Grohe, Martin (2001), „Obliczanie liczb przecinających się w czasie kwadratowym”, Proceedings of the Thirty-thhird Annual ACM Symposium on Theory of Computing (STOC '01) , s. 231–236, arXiv : cs / 0009010 , doi : 10,1145 /380752.380805 , S2CID 724544
•    Grohe, Martin (2017), Opisowa złożoność, kanonizacja i definiowalna teoria struktury grafów , Lecture Notes in Logic, tom. 47, Cambridge University Press, Cambridge, ISBN 978-1-107-01452-7 , MR 3729479
•    Grohe, Marcin ; Kreutzer, Stephan; Siebertz, Sebastian (2014), „Decydowanie o właściwościach pierwszego rzędu grafów nigdzie gęstych”, Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14) , Nowy Jork: ACM, s. 89–98, arXiv : 1311,3899 , doi : 10.1145/2591796.2591851 , ISBN 978-1-4503-2710-7 , S2CID 13297133
•     Cześć, Lauri; Kolaitis, Phokion G.; Luosto, Kerkko (1996), „Prawie wszędzie równoważność logiki w teorii modeli skończonych”, The Bulletin of Symbolic Logic , 2 (4): 422–443, doi : 10,2307/421173 , JSTOR 421173 , MR 1460316 , S2CID 16411368
•     Henson, C. Ward (1972), „Policzalne jednorodne struktury relacyjne i $-kategoryczne$ teorie”, The Journal of Symbolic Logic , 37 : 494–500, doi 10.2307/2272734 , JSTOR 2272734 , MR 0321727 , S2CID 40662635
•   Immerman, Neil ; Lander, Eric (1990), „Opisywanie grafów: podejście pierwszego rzędu do kanonizacji grafów”, w: Selman, Alan L. (red.), Retrospektywa teorii złożoności: na cześć Jurisa Hartmanisa z okazji jego sześćdziesiątych urodzin , Nowy York: Springer-Verlag, s. 59–81, doi : 10.1007/978-1-4612-4478-3_5 , MR 1060782
•   Ławrow, IA (1963), „Efektywna nierozdzielność zbioru identycznie prawdziwych formuł i zbioru formuł skończenie obalanych dla niektórych teorii elementarnych”, Algebra i Logika Sem. , 2 (1): 5–18, MR 0157904
•   Kawarabayashi, Ken-ichi ; Reed, Bruce (2007), „Obliczanie liczby skrzyżowań w czasie liniowym”, Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC '07), s. 382–390, doi : 10.1145/1250790.1250848 , S2CID 13000831
•     Koncewicz, Leszek (1973), "Definiowalność klas grafów w rachunku predykatów pierwszego rzędu z tożsamością", Polska Akademia Nauk , 32 : 159–190, doi : 10.1007/BF02123839 , JSTOR 20014678 , MR 0351796 , S2CID 189786935
•    Laubner, Bastian (2010), „Przechwytywanie czasu wielomianowego na wykresach interwałowych”, 25. doroczne sympozjum IEEE na temat logiki w informatyce (LICS 2010) , Los Alamitos, Kalifornia: IEEE Computer Society, s. 199–208, arXiv : 0911.3799 , doi : 10.1109/LICS.2010.42 , MR 2963094 , S2CID 1450409
•     Libkin, Leonid (2004), Elementy teorii modeli skończonych , Teksty z informatyki teoretycznej: seria EATCS , Springer-Verlag, Berlin, doi : 10.1007/978-3-662-07003-1 , ISBN 3-540-21202- 7 , MR 2102513 , S2CID 30176939
•   Lynch, James F. (1992), „Prawdopodobieństwa zdań o bardzo rzadkich grafach losowych”, Random Structures & Algorithms , 3 (1): 33–53, doi : 10,1002 / rsa.3240030105 , MR 1139487
•    Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Rzadkość: wykresy, struktury i algorytmy , algorytmy i kombinatoryka, tom. 28, Springer-Verlag, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7 , MR 2920058
•    Parys, Paweł (2014), „Logika pierwszego rzędu na grafach CPDA”, Informatyka — teoria i zastosowania , Notatki z wykładów z informatyki , tom. 8476, Nowy Jork: Springer-Verlag, s. 300–313, doi : 10.1007/978-3-319-06686-8_23 , MR 3218557 , S2CID 31640587
•    Pichurko, Oleg; Spencer, Joel ; Verbitsky, Oleg (2006), „Zwięzłe definicje w teorii grafów pierwszego rzędu”, 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
•   Pichurko, Oleg; Verbitsky, Oleg (2011), „Logiczna złożoność grafów: ankieta” , w: Grohe, Martin ; Makowsky, Johann A. (red.), Model Theoretic Methods in Finite Combinatoryics (AMS-ASL Joint Special Session, 5-8 stycznia 2009, Washington, DC) , Contemporary Mathematics, tom. 558, Amerykańskie Towarzystwo Matematyczne, s. 129–180, arXiv : 1003.4865 , ISBN 978-0-8218-8322-8
•   Seese, D. (1991), „Struktura modeli rozstrzygalnych monadycznych teorii grafów”, Annals of Pure and Applied Logic , 53 (2): 169–195, doi : 10.1016 / 0168-0072 (91) 90054- P , MR 1114848
•    Szela, Saharon ; Spencer, Joel (1988), „Prawa zero-jedynkowe dla rzadkich grafów losowych”, Journal of the American Mathematical Society , 1 (1): 97–115, doi : 10,2307/1990968 , JSTOR 1990968 , MR 0924703
•    Spencer, Joel (1990), „Nieskończone widma w teorii grafów pierwszego rzędu”, Combinatorica , 10 (1): 95–102, doi : 10.1007/BF02122699 , MR 1075070 , S2CID 27770505
•    Spencer, Joel (2001), Dziwna logika grafów losowych , algorytmy i kombinatoryka, tom. 22, Springer-Verlag, Berlin, doi : 10.1007/978-3-662-04538-1 , ISBN 3-540-41654-4 , MR 1847951
•   Trahtenbrot, BA (1950), „Niemożliwość algorytmu dla problemu decyzyjnego dla dziedzin skończonych”, Doklady Akademii Nauk SSSR , New Series, 70 : 569–572, MR 0033784
•    Verbitsky, Oleg (2005), „Definiowalność pierwszego rzędu grafów z separatorami za pomocą gry Ehrenfeuchta”, Theoretical Computer Science , 343 (1–2): 158–176, arXiv : math/0401361 , doi : 10.1016/j.tcs .2005.05.003 , MR 2168849 , S2CID 17886484
•    Wierbicki, Oleg; Zhukovskii, Maksim (2019), „Wąskie granice asymptotycznej złożoności opisowej izomorfizmu podgrafu”, 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), „Dynamiczna złożoność opisowa k -kliki” (PDF) , Information and Computation , 256 : 9–22, doi : 10.1016 / j.ic.2017.04.005 , MR 3705411 , S2CID 1412001