Projekt per år
Sammanfattning
This dissertation is a theoretical study of finitestate based grammars used in natural language processing. The study is concerned with certain varieties of finitestate intersection grammars (FSIGs) whose parsers define regular relations between surface strings and annotated surface strings. The study focuses on the following three aspects of FSIGs:
(i) Computational complexity of grammars under limiting parameters In the study, the computational complexity in practical natural language processing is approached through performancemotivated parameters on structural complexity. Each parameter splits some grammars in the Chomsky hierarchy into an infinite set of subset approximations. When the approximations are regular, they seem to fall into the logarithmictime hierarchy and the dotdepth hierarchy of starfree regular languages. This theoretical result is important and possibly relevant to grammar induction.
(ii) Linguistically applicable structural representations Related to the linguistically applicable representations of syntactic entities, the study contains new bracketing schemes that cope with dependency links, left and right branching, crossing dependencies and spurious ambiguity. New grammar representations that resemble the ChomskySchutzenberger representation of contextfree languages are presented in the study, and they include, in particular, representations for mildly contextsensitive nonprojective dependency grammars whose performance motivated approximations are lineartime parseable.
(iii) Compilation and simplification of linguistic constraints Efficient compilation methods for certain regular operations such as the generalized restriction are presented. These include an elegant algorithm that has already been adopted as the approach in a proprietary finitestate tool. In addition to the compilation methods, an approach to onthefly simplifications of finite state representations for parse forests is sketched.
These findings are tightly coupled with each other under the theme of locality. I argue that the findings help us to develop better, linguistically oriented formalisms for finitestate parsing and to develop more efficient parsers for natural language processing.
(i) Computational complexity of grammars under limiting parameters In the study, the computational complexity in practical natural language processing is approached through performancemotivated parameters on structural complexity. Each parameter splits some grammars in the Chomsky hierarchy into an infinite set of subset approximations. When the approximations are regular, they seem to fall into the logarithmictime hierarchy and the dotdepth hierarchy of starfree regular languages. This theoretical result is important and possibly relevant to grammar induction.
(ii) Linguistically applicable structural representations Related to the linguistically applicable representations of syntactic entities, the study contains new bracketing schemes that cope with dependency links, left and right branching, crossing dependencies and spurious ambiguity. New grammar representations that resemble the ChomskySchutzenberger representation of contextfree languages are presented in the study, and they include, in particular, representations for mildly contextsensitive nonprojective dependency grammars whose performance motivated approximations are lineartime parseable.
(iii) Compilation and simplification of linguistic constraints Efficient compilation methods for certain regular operations such as the generalized restriction are presented. These include an elegant algorithm that has already been adopted as the approach in a proprietary finitestate tool. In addition to the compilation methods, an approach to onthefly simplifications of finite state representations for parse forests is sketched.
These findings are tightly coupled with each other under the theme of locality. I argue that the findings help us to develop better, linguistically oriented formalisms for finitestate parsing and to develop more efficient parsers for natural language processing.
Bidragets titel på inmatningsspråk  Kontribuutioita äärellistilaisuuteen perustuvien kielioppien teoriaan 

Originalspråk  engelska 
Förlag  
Tryckta ISBN  9521025093 
Elektroniska ISBN  9521025107 
Status  Publicerad  2005 
MoEpublikationstyp  G5 Doktorsavhandling (artikel) 
Tilläggsuppgifter om doktorsavhandling
article dissertation, kokoelmaväitöskirjaVetenskapsgrenar
 6 Humanistiska vetenskaper
 2 Teknik
 612 Språk och litteratur
 113 Data och informationsvetenskap
Projekt

HFST  Helsinki FiniteState Technology
Linden, K., Koskenniemi, K., YliJyrä, A., Hulden, M., Silfverberg, M., Pirinen, T., Axelson, E., Hardwick, S., Niemi, J. & Hurskainen, A.
01/01/2005 → …
Projekt: Forskningsprojekt

CSPFSIGTREES: Efficient Parsing with FiniteState Constraint Satisfaction
YliJyrä, A., Koskenniemi, K. & Carlson, L.
01/01/2002 → 13/09/2005
Projekt: Forskningsprojekt