Wydział Matematyki i Informatyki (WMiI)/Faculty of Mathematics and Computer Science
Permanent URI for this community
Browse
Browsing Wydział Matematyki i Informatyki (WMiI)/Faculty of Mathematics and Computer Science by Author "Buszkowski, Wojciech. Promotor"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Pełny niełączny rachunek Lambeka z modalnościami i jego zastosowania w gramatykach typów(2016-02-08) Lin, Zhe; Buszkowski, Wojciech. PromotorRozprawa jest poświęcona pełnemu niełącznemu rachunkowi Lambeka wzbogaconemu o różne modalności. Te systemy tworzą pewną rodzinę logik substrukturalnych. W rozprawie badamy rachunki NL (niełączny rachunek Lambeka), DFNL (pełny niełączny rachunek Lambeka z prawami dystrybutywności dla operacji kratowych) i BFNL (DFNL z negacją spełniającą prawa algebr Boole’a) oraz ich rozszerzenia o operatory modalne, tworzące parę rezyduacji i spełniające standardowe aksjomaty logik modalnych (T), (4) i (5). Rozważamy też gramatyki typów oparte na tych rachunkach. Główne wyniki: twierdzenie o eliminacji cięć dla modalnych rozszerzeń NL z założeniami, wielomianowa złożoność relacji konsekwencji dla tych systemów, lemat interpolacyjny dla modalnych rozszerzeń DFNL i BFNL z założeniami, silna własność skończonego modelu dla tych systemów, rozstrzygalność relacji konsekwencji dla tyc systemów, PSPACE-zupełność rachunku BFNL, bezkontekstowość języków generowanych przez gramatyki typów oparte na tych rachunkach. Rozprawa kontynuuje wcześniejsze badania W. Buszkowskiego, M. Farulewskiego, M. Moortgata, A.. Plummera, N. Kurtoniny i innych.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).