Tuotetiedot
Väitöskirjassa tutkitaan formaalien kielten vaativuusluokkia. Erityisesti tarkastellaan sellaisia kieliperheitä, jotka voidaan tunnistaa alilineaarisilla resursseilla. Kieliperheen tunnistaminen alilineaarisilla resursseilla edellyttää yleensä rinnakkaislaskentaa, ja tämän vuoksi tutkimuksessa käytetään pääasiallisena laskennan mallina ns. alternoivaa Turingin konetta, jonka määräämiä vaativuusluokkia kutsutaan nimellä ALOGTIME. Muina malleina käytetään tavallista Turingin konetta, monilaskurikonetta ja branching programs -mallia. Generoivina malleina tarkastellaan Chomskyn kielioppeja, ohjattuja uudelleenkirjoitusjärjestelmiä (regulated rewriting systems) ja kielioppijärjestelmiä (grammar systems). Näihin kaikkiin liitetään ns. Szilardin kieli, joka kuvaa johtojen muotoa määräämällä kielen, jonka lauseet muodostuvat generoivan järjestelmän sääntöjen yksikäsitteisistä nimistä. Chomskyn kielten osalta todistetaan yläraja NC1 rajoittamattomien johtojen ja vasempien johtojen Szilardin kielille. Lisäksi annetaan uusi todistus Chomskyn-Schützenbergin lauseelle. Tähän liittyen esitellään myös uusi normaalimuoto kontekstittomille kieliopeille; tästä käytetään nimitystä Dyckin normaalimuoto. Ohjattuihin kielioppijärjestelmiin liittyen tutkitaan matriisikielioppeja, satunnaisen kontekstin kielioppeja (random context grammars) ja ohjelmoituja kielioppeja (programmed grammars). Kaikkein näiden kohdalla todistetaan uusia tuloksia rajoittamattomiin ja vasempiin johtoihin liittyvien Szilardin kielten tunnistamiseen kuluville resursseille. Kielioppijärjestelmiin liittyen tarkastellaan resurssivaatimuksia, jotka kuvaavat tarvittavaa kommunikaation ja yhteistyön määrää.
Arviot
Tuotearvioita ei vielä ole.