µ-kalkyyli - monadisen toisen kertaluvun predikaattilogiikan bisimilaarisesti invariantti fragmentti
VIRTEMA, JONNI (2007)
VIRTEMA, JONNI
2007
Matematiikka - Mathematics
Informaatiotieteiden tiedekunta - Faculty of Information 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ä
2007-11-09
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-17387
https://urn.fi/urn:nbn:fi:uta-1-17387
Tiivistelmä
Tutkielmassa esitellään µ-kalkyyli ja monadinen toisen kertaluvun predikaattilogiikka MSO. µ-kalkyylille esitetään sekä standardi- että peliteoreettinen semantiikka ja todistetaan näiden yhtäpitävyys. Tutkielmassa todistetaan myös, että jokainen Lµ-lause on bisimilaari-invariantti ja että vastaavaa ominaisuutta ei ole MSO-lauseilla. Lisäksi määritellään standardikäännös µ-kalkyyliltä monadiseen toisen kertaluvun predikaattilogiikkaan, siis näytetään, että jokaista Lµ-kaavaa vastaa ekvivalentti MSO-kaava, itseasiassa ekvivalentti MSO-lause. Tutkielmassa todistetaan myös, että jokaista bisimilaari-invarianttia MSO-lausetta vastaa ekvivalentti Lµ-kaava. Tutkielman päätuloksena onkin, että monadisen toisen kertaluvun predikaattilogiikan bisimilaari-invariantti fragmentti on täsmälleen µ-kalkyylin kaavojen bisimilaari-invariantti fragmentti. Avoimeksi kysymykseksi jää onko olemassa bisimilaari-invarianttia Lµ-kaavaa, jota ei vastaisi jokin ekvivalentti Lµ-lause, siis onko monadisen toisenkertaluvun predikaattilogiikan bisimilaari-invariantti fragmentti täsmälleen µ-kalkyyli, kun tarkastellaan ainoastaan lausemääriteltävyyttä. Walukiewiczin ja Janinin artikkelin [5] perusteella näin on.
Avainsanat: µ-kalkyyli, monadinen toisen kertaluvun predikaattilogiikka, standardikäännös, µ-automaatti, omega-laajennus, modaalilogiikka, transitiosysteemi, bisimilaarisesti invariantti, ilmaisuvoimien vastaavuus.
Avainsanat: µ-kalkyyli, monadinen toisen kertaluvun predikaattilogiikka, standardikäännös, µ-automaatti, omega-laajennus, modaalilogiikka, transitiosysteemi, bisimilaarisesti invariantti, ilmaisuvoimien vastaavuus.