M.Sc. Liliana Cojocarun tietojenkäsittelyopin alaan kuuluva väitöskirja

Advanced Studies on the Complexity of Formal Languages  (Tutkimuksia formaalien kielten laskennallisesta vaativuudesta)

tarkastetaan 24.8.2016 klo 12 Tampereen yliopiston Pinni B-rakennuksen luentosalissa 1096, Kanslerinrinne 1, Tampere.

Vastaväittäjänä on Research Fellow Galina Jirásková (Slovak Academy of Sciences)). Kustoksena toimii professori Erkki Mäkinen.

Väitöstilaisuuden kieli on englanti.


Tutkimuksia formaalien kielten laskennallisesta vaativuudesta


Laskennan monimutkaisuudella tarkoitetaan niiden resurssien määrää, jotka tarvitaan tietyn laskentatehtävän ratkaisemiseen. Laskennassa tarvittavia resursseja ovat aika (laskenta-askelten lukumäärä), muistitila, käytettävän laitteiston monimutkaisuus ja laskentayksikköjen välisen kommunikaation määrä. Laskennan monimutkaisuuden teoriassa (kompleksisuusteoriassa) etsitään minimaalisia resursseja annettujen laskenta-tehtävien ratkaisemiseen. Tietyssä laskentamallissa tarvittavien resurssien määrä jakaa ongelmat vaativuusluokkiin. Samaan vaativuusluokkaan kuuluvat ongelmat voidaan siis ratkaista tarkasteltavassa laskentamallissa kutakuinkin samoilla resursseilla.

Tässä 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ää.

                                               ******

Liliana Cojocaru on kotoisin Romaniasta ja hän on suorittanut aikaisemmat opintonsa Romaniassa (A.I.Cuza Univ., Iasi) ja Espanjassa (Rovira i Virgila Univ., Tarragona).

Cojocarun väitöskirja ilmestyy sarjassa Acta Universitatis Tamperensis; 2192, Tampere University Press, Tampere 2016. ISBN  978-952-03-0183-5, ISSN 1455-1616. Väitöskirja ilmestyy myös sähköisenä sarjassa Acta Electronica Universitatis Tamperensis; 1691, Tampere University Press 2016. ISBN  978-952-03-0184-2, ISSN 1456-954X.
http://tampub.uta.fi.

Väitöskirjan tilausosoite: Verkkokirjakauppa: https://verkkokauppa.juvenes.fi, tai e-mail: verkkokauppa@juvenesprint.fi.

Lisätietoja: Liliana Cojocaru, liliana.cojocaru@uta.fi