Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Contributions to the Theory of Finite-State Based Grammars

Show simple item record

dc.contributor Helsingin yliopisto, humanistinen tiedekunta, yleisen kielitieteen laitos fi
dc.contributor University of Helsinki, Faculty of Arts, Department of General Linguistics en
dc.contributor Helsingfors universitet, humanistiska fakulteten, institutionen för allmän språkvetenskap sv
dc.contributor.author Yli-Jyrä, Anssi fi
dc.date.accessioned 2010-11-25T09:37:27Z
dc.date.available 2010-11-25T09:37:27Z
dc.date.issued 2005-06 fi
dc.identifier.uri URN:ISBN:952-10-2510-7 fi
dc.identifier.uri http://hdl.handle.net/10138/19237
dc.description.abstract This dissertation is a theoretical study of finite-state based grammars used in natural language processing. The study is concerned with certain varieties of finite-state intersection grammars (FSIG) 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 performance-motivated 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 logarithmic-time hierarchyand the dot-depth hierarchy of star-free 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 Chomsky-Schützenberger representation of context-free languages are presented in the study, and they include, in particular, representations for mildly context-sensitive non-projective dependency grammars whose performance-motivated approximations are linear time parseable. (iii) Compilation and simplification of linguistic constraints Efficient compilation methods for certain regular operations such as generalized restriction are presented. These include an elegant algorithm that has already been adopted as the approach in a proprietary finite-state tool. In addition to the compilation methods, an approach to on-the-fly 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 finite-state parsing and to develop more efficient parsers for natural language processing. Avainsanat: syntactic parsing, finite-state automata, dependency grammar, first-order logic, linguistic performance, star-free regular approximations, mildly context-sensitive grammars en
dc.language.iso en fi
dc.publisher Helsingin yliopisto fi
dc.publisher University of Helsinki en
dc.publisher Helsingfors universitet sv
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.title Contributions to the Theory of Finite-State Based Grammars en
dc.type.ontasot Väitöskirja fi
dc.type.ontasot Doctoral dissertation en
dc.type.ontasot Doktorsavhandling sv
dc.type.dcmitype Text fi

Files in this item

Files Size Format View/Open
contribu.pdf 702.9Kb PDF View/Open
tiiviste.pdf 95.17Kb PDF View/Open
This item appears in the following Collection(s)

Show simple item record

Search Helda


Advanced Search

Browse

My Account