Bisimulation equivalence in description logics and its applications

Ta 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

We 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.