Browsing by Author "Moroz, Katarzyna"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Zagadnienia algorytmiczne dla gramatyk pregrupowych(2010-06-11T07:57:10Z) Moroz, Katarzyna; Buszkowski, Wojciech. PromotorW 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).