Modaalilogiikka ja lokaalit algoritmit
Heiman, Damian (2020)
Heiman, Damian
2020
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-05-18
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202005135291
https://urn.fi/URN:NBN:fi:tuni-202005135291
Tiivistelmä
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.