Wydział MIM UW - Nguyen Anh Linh

Next: Motywacja

Autoreferat pracy doktorskiej

``Results on Modal Reasoning with Applications to Modal Deductive Databases''

Nguyen Anh Linh

Dedukcyjne bazy danych i programowanie w logice znajduja obszerne i wazne zastosowania. Te dziedziny sa scisle powiazane, gdyz obie uzywaja regu $\l$ logiki klasycznej do reprezentacji wzajemnych zaleznosci pomiedzy relacjami. Programowanie w logice jest g $\l$ ównie uzywane w systemach sztucznej inteligencji, zas dedukcyjne bazy danych sa systemami, w których ilosc danych jest znacznie wieksza niz ilosc regu $\l$ . W klasycznej teorii regu $\l$ y logiczne maja postac uniwersalnie kwantyfikowanych klauzul Horna, zapisanych w jezyku pierwszego rzedu. Dla tak zdefiniowanego jezyka problem spe $\l$ nialnosci jest rozstrzygalny w czasie wielomianowym, a rozmiar generowanego najmniejszego modelu zalezy wielomianowo od d $\l$ ugosci formu $\l$ y.

Rozszerzenie jezyka zapytan do logik modalnych prowadzi do zdefiniowania modalnego jezyka klauzul Horna. W tym przypadku zosta $\l$ o jednak udowodnione przez Chena i Lina [2], ze problem spe $\l$ nialnosci zbiorów klauzul Horna dla kazdego z nastepujacych jezyków K, KD, T, KB, KDB, B, K4, KD4 i S4 jest zupe $\l$ ny w klasie problemów wymagajacych wielomianowej pamieci, tzn. PSPACE-zupe $\l$ ny. Ze wzgledu na te trudnosc, programowanie w logikach modalnych nie zyskiwa $\l$ o dotad pe $\l$ nego uznania, jak równiez teoria modalnych dedukcyjnych baz danych nie by $\l$ a intensywnie rozwijana.

Z drugiej strony, teoria logik modalnych przynios $\l$ a wiele wyników dotyczacych z $\l$ ozonosci problemu spe $\l$ nialnosci formu $\l$ w zdaniowych logikach modalnych. Udowodniono przez Chena i Lina [2] oraz Fariñas del Cerra i Penttonena [3], ze problem spe $\l$ nialnosci zbiorów klauzul Horna dla kazdej logiki, która jest normalnym rozszerzeniem logiki K5, jest rozstrzygalny w wielomianowym czasie. Górne z $\l$ ozonosci pamieciowe dla logik K, KD, T ( $O(n.\log{n})$ ), i K4, KD4, S4 ( $O(n^2.\log{n})$ ) zosta $\l$ y uzyskane przez Hudelmaiera [6] oraz Basina, Matthewsa i Viganò [1,10].

Next: Motywacja

Nguyen Anh Linh
2000-04-01