Modaalilogiikka ja lokaalit algoritmit

Abstract

Tässä tutkielmassa tutkitaan modaalilogiikan yhteyksiä lokaaleihin algoritmeihin. Modaalilogiikka on lauselogiikan laajennus, jossa kaavojen totuutta tutkitaan mahdollisia maailmoja mallintavissa Kripke-malleissa. Lokaalit algoritmit ovat graafeissa ajettavia algoritmeja, jotka päättyvät vakioajassa. Algoritmeilla ratkaistaan graafiongelmia, joille esitetään luokittelu sen mukaan, voidaanko ne ratkaista vakioajassa ja miten paljon informaatiota algoritmit tarvitsevat niiden ratkaisemiseksi. Vakioaikaiset graafiongelmaluokat karakterisoidaan modaalilogiikoiden avulla samaistamalla syötegraafit sopiviin Kripke-malleihin. Tutkielma keskittyy heikkoihin hajautetun laskennan malleihin, jotka hyödyntävät graafeihin lisättäviä porttinumerointeja, ja laajentaa aiempia niitä koskevia tuloksia tarkastelemalla, miten tulokset yleistyvät yksinkertaisista graafeista suunnattuihin graafeihin. Tuloksien todistamiseen käytetään bisimulaatiota, joka liittää toisiinsa Kripke-mallit, joita modaalilogiikka ei erota toisistaan. Erityisesti osoitetaan, että graafiongelmaluokkien välinen hierarkia on suunnattujen graafien tapauksessa heikompi kuin yksinkertaisten graafien tapauksessa. Osa luokkien välisistä inkluusioista ei päde, kun rajoitus yksinkertaisiin graafeihin poistetaan.