Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Compiling Simple Context Restrictions with Nondeterministic Automata

Show simple item record

dc.contributor University of Helsinki, Department of Modern Languages en
dc.contributor.author Yli-Jyrä, Anssi Mikael
dc.date.accessioned 2012-02-22T09:30:24Z
dc.date.available 2012-02-22T09:30:24Z
dc.date.issued 2011
dc.identifier.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 . en
dc.identifier.other PURE: 20255429
dc.identifier.uri http://hdl.handle.net/10138/29898
dc.description.abstract This paper describes a non-conventional method for compiling (phonological or morpho-syntactic) context restriction (CR) constraints into non-deterministic automata in finite-state tools and surface parsing systems. The method reduces any CR into a simple one that constraints the occurrences of the empty string and represents right contexts with co-determististic states. In cases where a fully deterministic representation would be exponentially larger, this kind of inward de- terminism in contexts can bring benefits over various De Morgan approaches where full determinization is necessary. In the method, an accepted word gets a unique path that is a projection of a ladder-shaped structure in the context recognizer. This projection is computed in time that is polynomial to the number of context states. However, it may be difficult to take advantage of the method in a finite-state library that coerces intermediate results into canonical automata and whose intersection operation assumes deterministic automata. en
dc.format.extent 9
dc.language.iso eng
dc.relation.ispartof International Workshop on Finite State Methods and Natural Language Processing
dc.relation.ispartof Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing
dc.relation.uri http://aclweb.org/anthology-new/W/W11/#4400
dc.relation.uri http://aclweb.org/anthology-new/W/W11/W11-4405.pdf
dc.subject 111 Mathematics en
dc.subject logic en
dc.subject LOGIC en
dc.subject QUANTIFICATION en
dc.subject quantification en
dc.subject first-order logic en
dc.subject implication en
dc.subject rational series en
dc.subject logiikka en
dc.subject kvantifiointi en
dc.subject ensimmäisen kertaluokan logiikka en
dc.subject implikaatiot en
dc.subject rationaaliset potenssisarjat en
dc.subject logik en
dc.subject kvantifiering en
dc.subject första ordingens logik en
dc.subject implikation en
dc.subject rationell potensserier en
dc.subject 113 Computer and information sciences en
dc.subject compliers en
dc.subject regular expressions en
dc.subject finite automata en
dc.subject finite-state transducers en
dc.subject string algorithms en
dc.subject regular languages en
dc.subject ohjelmointikielten kääntäjät en
dc.subject äärelliset automaatit en
dc.subject äärellistilaiset transduktorit en
dc.subject merkkijonoalgoritmit en
dc.subject säännölliset lausekkeet en
dc.subject säännölliset kielet en
dc.subject kompilatorer en
dc.subject reguljära uttryck en
dc.subject ändliga automater en
dc.subject finita-statliga transduktorer en
dc.subject strängalgoritmer en
dc.subject reguljära språk en
dc.subject 6121 Languages en
dc.subject finite-state methods en
dc.subject finite automata en
dc.subject finite-state morphological analysis en
dc.subject constraints en
dc.subject two-level rules en
dc.subject two-level morphology en
dc.subject grammar formalisms en
dc.subject äärellistilaiset menetelmät en
dc.subject äärelliset automaatit en
dc.subject äärellistilainen morfologinen analyysi en
dc.subject rajoitteet en
dc.subject rajoitesäännöt en
dc.subject constraint grammar en
dc.subject kaksitasosäännöt en
dc.subject kaksitasoinen morfologia en
dc.subject kielioppiformalismit en
dc.subject finita-statliga metoder en
dc.subject ändliga automater en
dc.subject morfologisk analys en
dc.subject begränsningar en
dc.subject two-nivå morfologi en
dc.subject grammatiska formalismer en
dc.title Compiling Simple Context Restrictions with Nondeterministic Automata en
dc.title.alternative Yksinkertaisten kontekstirajoitusten kääntäminen epädeterminististen automaattien avulla en
dc.type A4 Article in conference publication (refereed)
dc.description.version Peer reviewed
dc.description.version Peer reviewed
dc.type.dcmitype textfile
dc.type.dcmitype textfile
dc.type.uri info:eu-repo/semantics/conferencePaper
dc.type.uri info:eu-repo/semantics/publishedVersion
dc.type.uri info:eu-repo/semantics/acceptedVersion

Files in this item

Files Description Size Format View/Open
W11_4405.pdf 197.5Kb PDF View/Open
ylijyra_fsmnlp11_online_slides.pdf 570.6Kb PDF View/Open
This item appears in the following Collection(s)

Show simple item record

Search Helda


Advanced Search

Browse

My Account