Zagadnienia algorytmiczne dla gramatyk pregrupowych
| dc.contributor.advisor | Buszkowski, Wojciech. Promotor | |
| dc.contributor.author | Moroz, Katarzyna | |
| dc.date.accessioned | 2010-06-11T07:57:10Z | |
| dc.date.available | 2010-06-11T07:57:10Z | |
| dc.date.issued | 2010-06-11T07:57:10Z | |
| dc.description | Wydział Matematyki i Informatyki: Zakład Teorii Obliczeń | pl_PL |
| dc.description.abstract | W pracy rozważamy zagadnienia algorytmiczne dla gramatyk pregrupowych w ich podstawowej formie oraz dla pewnych rozszerzeń gramatyk pregrupowych. Gramatyki pregrupowe zostały wprowadzone przez Lambeka w 1999 jako nowe, algebraiczne narzędzie analizy syntaktycznej języków naturalnych. Formalizm pregrup należy do tradycji gramatyk kategorialnych (gramatyk typów). Każdemu słowu przypisuję się jeden lub więcej typów. Typy odpowiadają pewnym własnościom słów. Wszystkie informacje lingwistyczne zawarte są w leksykonie. Reguły są sekwentami dowodliwymi w pewnej logice typów. Gramatyki pregrupowe zostały zastosowane do wielu różnorodnych języków naturalnych. Najpierw rozważamy równoważność gramatyk pregrupowych i bezkontekstowych. Proponujemy bezpośrednią wielomianową konstrukcję gramatyki bezkontekstowej oraz automatu ze stosem równoważnych danej gramatyce pregrupowej. Następnie podajemy wielomianowy dynamiczny algorytm parsingu dla gramatyk pregrupowych i gramatyk pregrupowych z promocjami. Następnie pokazujemy, że problem promocji dla gramatyk pregrupowych z promocjami z 1 jest rozwiązywalny w czasie wielomianowym oraz podajemy algorytm parsingu dla gramatyk pregrupowych z promocjami z 1. Na zakończenie przedstawiamy implementację w języku Java algorytmu parsingu dla gramatyk pregrupowych i prezentujemy leksykon typów dla języka angielskiego (oparty na pracy J. Lambeka). | pl_PL |
| dc.description.abstract | In the thesis we discuss some algorithmic questions for pregroup grammars in their basic form and some extensions of pregroup grammars. Pregroup grammars were introduced in 1999 by Lambek as a new algebraic tool for syntactical analysis of natural languages. The formalism of pregroups belongs to the tradition of categorial grammars (type grammars). The idea is that each word is assigned one or more types. Types reflect some characteristics of words. All linguistic data is encoded in the lexicon. Rules are sequents provable in some type logic. Pregroup grammars have been successfully applied to many diverse natural languages. First we consider the equivalence of pregroup grammars and context-free grammars. We propose a direct polynomial construction of a context-free grammar and a push-down automaton equivalent to the given pregroup grammar. Next, we give a new polynomial, dynamic parsing algorithm for pregroup grammars and for pregroup grammars with letter promotions. Later we discuss pregroup grammars with letter promotions with 1. We show that the letter promotion problem for pregroup grammars with letter promotions with 1 is solvable in polynomial time and we provide a polynomial parsing algorithm for them. Finally, we present an implementation in Java of the parsing algorithm for pregroup grammars and supply a type lexicon for English (based on the work of J. Lambek). | pl_PL |
| dc.identifier.uri | http://hdl.handle.net/10593/442 | |
| dc.language.iso | en | pl_PL |
| dc.subject | Pregrupy | pl_PL |
| dc.subject | Pregroups | pl_PL |
| dc.subject | Gramatyki pregrupowe | pl_PL |
| dc.subject | Pregroup grammars | pl_PL |
| dc.subject | Parsing | pl_PL |
| dc.subject | Parsing | pl_PL |
| dc.title | Zagadnienia algorytmiczne dla gramatyk pregrupowych | pl_PL |
| dc.title.alternative | Algorithmic questions for pregroup grammars | pl_PL |
| dc.type | Dysertacja | pl_PL |