Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Väitöskirjat
  • Näytä viite
  •   Etusivu
  • Trepo
  • Väitöskirjat
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Advanced Studies on the Complexity of Formal Languages

Cojocaru, Liliana (2016)

 
Avaa tiedosto
978-952-03-0184-2.pdf (4.973Mt)
Lataukset: 



Cojocaru, Liliana
Tampere University Press
2016

Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Väitöspäivä
2016-08-24
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:ISBN:978-952-03-0184-2
Tiivistelmä
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ää.
 
Kokoelmat
  • Väitöskirjat [5028]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste