Compiling Simple Context Restrictions with Nondeterministic Automata

Show full item record

Permalink

http://hdl.handle.net/10138/29898

Citation

Yli-Jyrä , A M 2011 , ' Compiling Simple Context Restrictions with Nondeterministic Automata ' in Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing , pp. 30-38 .

Title: Compiling Simple Context Restrictions with Nondeterministic Automata
Author: Yli-Jyrä, Anssi Mikael
Contributor: University of Helsinki, Department of Modern Languages
Belongs to series: Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing
Abstract: 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.
Peer review status: Peer reviewed
URI: http://hdl.handle.net/10138/29898
Date: 2011
Subject: 111 Mathematics
logic
LOGIC
QUANTIFICATION
quantification
first-order logic
implication
rational series
logiikka
kvantifiointi
ensimmäisen kertaluokan logiikka
implikaatiot
rationaaliset potenssisarjat
logik
kvantifiering
första ordingens logik
implikation
rationell potensserier
113 Computer and information sciences
compliers
regular expressions
finite automata
finite-state transducers
string algorithms
regular languages
ohjelmointikielten kääntäjät
äärelliset automaatit
äärellistilaiset transduktorit
merkkijonoalgoritmit
säännölliset lausekkeet
säännölliset kielet
kompilatorer
reguljära uttryck
ändliga automater
finita-statliga transduktorer
strängalgoritmer
reguljära språk
6121 Languages
finite-state methods
finite automata
finite-state morphological analysis
constraints
two-level rules
two-level morphology
grammar formalisms
äärellistilaiset menetelmät
äärelliset automaatit
äärellistilainen morfologinen analyysi
rajoitteet
rajoitesäännöt
constraint grammar
kaksitasosäännöt
kaksitasoinen morfologia
kielioppiformalismit
finita-statliga metoder
ändliga automater
morfologisk analys
begränsningar
two-nivå morfologi
grammatiska formalismer


Files in this item

Total number of downloads: Loading...

Files Size Format View
ylijyra_fsmnlp11_online_slides.pdf 557.3Kb PDF View/Open
W11_4405.pdf 192.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record