Approaches to Finite Variable Dependence: Expressiveness and Computational Complexity
Jonni Virtema · Tampere University Institutional Repository (Tampere University) · 2014
Riippuvuuslogiikka on uusi formalismi, jossa tarkastellaan riippuvuuskäsitteeseen liittyviä ilmiöitä muodollisen logiikan viitekehyksessä. Muodollisiin logiikoihin liittyvissä matemaattisissa tarkasteluissa tutkimuksen kohteena on tyypillisesti logiikoiden ilmaisuvoima ja päättelyn laskennallinen vaativuus. Väitöskirjassa tarkastellaan useisiin eri riippuvuuskäsitteisiin perustuvia logiikoita. Työssä tutkitaan riippuvuuslogiikoiden ilmaisuvoimien ja laskennallisten vaativuuksien suhteita. Työn päätuloksena on nk. IF-logiikan ja riippuvuuslogiikan D kahden muuttujan fragmenttien toteutuvuusongelmien erottelu suhteessa ratkeavuuteen. Lisäksi työ sisältää Boolen riippuvuuslogiikan ilmaisuvoiman kattavan luokittelun.