Tehokas lauseenjäsentäminen äärellistilaisen rajoiteongelman kautta

Projektin yksityiskohdat

Kuvaus

Äärellistilaiset automaatit ovat tehokkaita ja sen vuoksi laajasti käytössä kieleen liittyvässä teknologiassa. Koskenniemen Äärellistilainen Leikkauskielioppi (FSIG) on kieliriippumaton pintasyntaktinen jäsennysmenetelmä. Yllättävää on, että FSIG:n tilakompleksisuus on niin iso että jopa lineaarinen jäsennyksen vaativuuskaan ei ole tarpeeksi tehokasta.

Antamalla kielioppiesitysmuodon kasvaa yhdessä virkkeen pituuden kanssa ikään kuin jokaiselle virkkeelle valittaisiin uusi kielioppi, määrittelemme Aärellistilaisen Rajoitteongeman (FSCSP), jonka tiedetään olevan sellaisenaan tehoton. FSCSP voidaan kuitenkin palauttaa tavalliseksi rajoiteongelmaksi (CSP), jonka rajoitteet ovat tiettyjen ehtojen vallitessa tehokkaasti ratkaistavissa.

Tutkimuksen hypoteesi on että tehokkasti ratkaistaviin rajoiteongelmiin kuuluu myös kielioppeja (kuten kontekstittomia ja puuliitoskielioppeja) jotka liittävät virkeeseen puurakenteita. Tämä yhteys merkitsee sitä, että viime aikoina löydetyt monien kielioppiformalismien malliteoreettiset esitysmuodot voidaan määritellä FSCSP viitekehyksessä. Hankkeessa kehitetään tätä teoreettista viitekehystä soveltamalla uusia äärellistilainen jäsennysmenetelmä..
AkronyymiCSP-FSIG-TREES
TilaPäättynyt
Todellinen alku/loppupvm01/01/200213/09/2005

Tieteenalat

  • 612 Kielitieteet, kirjallisuus
  • automaattinen lauseenjäsennys
  • kieliopit
  • kielioppiformalismit
  • 113 Tietojenkäsittely- ja informaatiotieteet
  • Constraint Satisfaction Problem
  • äärelliset automaatit
  • äärellistilainen leikkauskielioppi
  • malliteoreettinen syntaksi