Praca doktorska
Miniatura
Pliki
thesis-ARD.pdf1001.32 KB
autoreferat-ARD.pdf265.06 KB
streszczenie-ARD.pdf62.93 KB
Licencja
FairUseKorzystanie z tego materiału możliwe jest zgodnie z właściwymi przepisami o dozwolonym użytku lub o innych wyjątkach przewidzianych w przepisach prawa. Korzystanie w szerszym zakresie wymaga uzyskania zgody uprawnionego.
 

Bisimulation equivalence in description logics and its applications

Uproszczony widok
dc.abstract.enWe provide results on preservation of semi-positive concepts, the Hennessy-Milner property w.r.t. bisimulation-based comparisons, characterizing bisimulation for tidy interpretations by semi-positive concepts, and minimization of interpretations that preserves semi-positive concepts.We separate the expressiveness of the description logics that extend L, where ALC <= L <= ALCreg, with any combination of the features I, O, Q, U, Self. Our separation results are w.r.t. concepts, positive concepts, TBoxes and ABoxes. We prove that any concept in any description logic that extends ALC with some features amongst I, Self, Qk (qualified number restrictions with numbers bounded by a constant k) can be learned if the training information system (specified as an interpretation) is good enough.
dc.abstract.plTa rozprawa jest poświęcona badaniu bisymulacji i opartych na bisymulacjach porównań interpretacji dla dużej klasy logik deskrypcyjnych rozszerzających logikę ALCreg (będącą wariantem zdaniowej logiki dynamicznej) o dowolną kombinację cech spośród I (odwrotnych ról), O (nominałów), Q (kwalifikowanych ograniczeń numerycznych), U (roli uniwersalnej) i Self (lokalnej zwrotności roli), jak również o aksjomaty o rolach. Rozprawa zawiera wyniki o niezmienności pojęć, TBoxów i ABoxów, o zachowywaniu RBoxów i baz wiedzy, o własności Hennessiego-Milnera względem bisymulacji, o największych relacjach auto-bisymulacyjnych i interpretacjach ilorazowych względem równoważności bisymulacyjnej. Poprzez dostosowanie algorytmu minimalizacji automatu Hopcrofta i algorytmu Paige-Tarjana, opracowane zostały efektywne algorytmy obliczenia podziału dziedziny danej skończonej interpretacji odpowiadającego największej relacji auto-bisymulacyjnej. Rozprawa zawiera również wyniki o zachowywaniu semi-pozytywnych pojęć, o własności Hennessiego-Milnera względem opartych na bisymulacjach porównań interpretacji, o charakteryzacji bisymulacji dla schludnych interpretacji za pomocą semi-pozytywnych pojęć, o minimalizacji interpretacji z zachowywaniem semi-pozytywnych pojęć. Otrzymane zostały również wyniki o oddzieleniu siły wyrażalności logik deskrypcyjnych rozszerzających dowolną logikę L, gdzie ALC <= L <= ALCreg, o dowolną kombinację cech spośród I, O, Q, U, Self. Te wyniki są sformułowane dla pojęć, pozytywnych pojęć, TBoxów i ABoxów. Udowodniono również, że każde pojęcie w każdej logice deskrypcyjnej rozszerzającej ALC o niektóre cechy spośród I, Self, Qk (kwalifikowanych ograniczeń numerycznych używających wartości nieprzekraczającej stałej k) jest wyuczalne jeśli system treningowy (będący interpretacją) jest wystarczając
dc.affiliation.departmentWydział Matematyki, Informatyki i Mechaniki
dc.contributor.authorRezaei-Divroodi, Ali
dc.date.available2024-01-17T15:08:36Z
dc.date.defence2015-10-20
dc.date.issued2015-02-23
dc.description.osid194448
dc.description.promoterNguyen, Anh Linh
dc.identifier.apd16871
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/1168
dc.language.isoen
dc.rightsFairUse
dc.subject.endescription logics
dc.subject.enbisimulation
dc.subject.enminimization
dc.subject.enexpressiveness
dc.subject.enconcept learning
dc.subject.enlearnability
dc.subject.pllogiki deskrypcyjne
dc.subject.plbisymulacja
dc.subject.plminimalizacja
dc.subject.plsiła wyrażania
dc.subject.pluczenie się pojęć
dc.subject.plwyuczalność
dc.titleBisimulation equivalence in description logics and its applications
dc.title.alternativeRównoważność bisymulacyjna w logikach deskrypcyjnych i jej zastosowania
dc.typeDoctoralThesis
dspace.entity.typePublication