Compiling Simple Context Restrictions with Nondeterministic Automata
Anssi Yli-Jyrä · Työväentutkimus Vuosikirja · 2011
Paperi kuvaa epäkonventionaalisen menetelmän (fonologisten ja morfo-syntaktisten) kontekstirajoitesääntöjen kääntämiseksi epädeterministisiksi automaateiksi äärellistilaisissa työkaluissa ja pintajäsennysjärjestelmissä. Metodi redusoi minkä tahansa kontekstirajoitteen yksinkertaiseksi rajoitteeksi, joka rajoittaa tyhjän merkkijonon esiintymisiä ja esittää oikean puolen kontekstit takaperindeterminististen tilojen avulla. Tapauksissa, joissa täysin deterministinen esitysmuoto olisi eksponentiaalisesti isompi, tällainen sisäänpäin deterministinen kontekstien esitysmuoto voi olla edullisempi kuin erilaiset De Morgan -lähestymistavat, joissa täysi determinisointi on välttämätöntä. Menetelmän yhteydessä jokainen hyväksytty merkkijono saa yksiselitteisen polun, joka on kontekstien tunnistaja-automaatissa olevan tikapuumaisen rakenteen projektio. Tämä projektio voidaan laskea (koko rajoitteelle) ajassa, joka on polynomisessa suhteessa kontekstitilojen määrään. Menetelmästä voi kuitenkin olla vaikea saada hyötyä, jos sitä käytetään äärellistilaisessa kirjastossa, joka pakottaa välitulokset kanonisiksi automaateiksi ja jonka leikkaus-operaatio edellyttää deterministisiä automaatteja operandeinaan.