Tehokas lauseenjäsentäminen äärellistilaisen rajoiteongelman kautta

Ää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ä..