close

Вход

Забыли?

вход по аккаунту

?

Модификация табличного алгоритма на основе проверки непересекаемости сложных концептов.

код для вставкиСкачать
??????????? ?????????? ????????? ...
143
© ?.?. ??????, ?.?. ?????????, ?.?. ?????????
ivashco@mail.ru, 107th@mail.ru, m_grigoriev@mail.ru
??? 510.5:510.22:519-6
??????????? ?????????? ????????? ?? ??????
???????? ???????????????? ??????? ?????????*
?????????. ?????? ????????? ???????????? ????????????? ?????????
?????????? ????????? ? ????? ?????????? ??????? ?????? ??? ??????????? ??????????? ??? ????????????? ??? ???????? ??? ?????? ??????? ???????.
SUMMARY. The article considers researching the necessity of tableau algorithm
changing with aim to reduce algorithm work time, for providing an opportunity of its
using for checking large knowledge bases.
???????? ?????. ???????????? ?????????????, ?????????????? ??????,
???????, ????, ????????? ????????.
KEYWORDS. Simulation modeling, description logic, concept, role, tableau
algorithm.
????? ?? ?????? ???????????? ???????????? ????????????? ?????? ???????? ???? ?????????????? ?????? ALC [1-3]. ????????????? ??????? ?? ?????????????????? ???????? ????????? ? ?? ??????? ????????? (TBox) ? ????????
??????, ??????? ????? ? ?????????? ??????? (ABox). ?????????? ?????????????? ?????? ???? ??????????? ???????????? ????? ??????, ?????? ???????????? ? ???????? ???????????? ? ???? GCI-????????? [1], ? ????? ????????????
???????? ?????????????????? ?????? ???????? ?????????? ??????? ? ???????
?????????? ?????????. ????????? ???????? ???????? ???????????? ??????????
?????????? ???????????????? ????????????? ?????????? ??????? ?? ?????? ?????????????????? ???????? ????????? ? ?? ?????, ?????????????? ? TBox.
??? ?????????????? ?????????? ????? ???????? ?????????? ??????? (????? ????
??????????? ???????), ?????? ??? ????????, ????????? ? TBox, ?????? ????
???????????? ???? ?? ????? ???????? [4-5]. ????? ????? ????????? ???????????? ???????? ??????????? ?????????. ????????????? ???????? ????????????????, ???? ?? ?????????? ?? ?????? ???????, ??????? ??????????? ???????? ? ???
??????????. ????????????? ?????? ???????? ??????????, ???? ?????????? ????
?? ???? ???????????????? ????????????? ?????????? ???????. ????????? ???????? ????? ???????????????? ?????????, ??? ??? ??? ????????? ??????? ? ????????, ?????????? ??????????? ?????? ?????????, ?? ?????? ???? ??????? ?
?????? ?? ?????????, ?????????????? ????? ????????? 2n ??????, ??? n ? ?????????? ????????????? ?????????. ?????????? ??????????????? ??????? [6],
??????? ????????? ?????????? ??????????? ????????, ?????? ????????? ???????? ??? ?? ???????? ???????? ??? ???????? ??? ?????? ??????? ???????.
* ?????? ????????? ?? ??????? «??????????? ?????????? ??????????? ??????????? ??????????? ?? ?????? ??????????????? ????????????? ?????????????? ??????» ? ????????????
? ???????? ???????????? ??????????? ? ????? ?????????? ????????? ?? 2012 ???.
??????-?????????????? ?????. ???????????
© ?.?. ??????, ?.?.
?????????, ?.?. ?????????
144
© ?.?. ??????, ?.?. ?????????, ?.?. ?????????
????? ?????? ?????? ???????? ??????????? ?????????? ?????????, ???????
???????? ???????? ?????????? ???????????????? ????????????? ??? ???????
?????????, ????????? ?? ??????????? ???????.
?????? ??????? ??????? ? ?????????????? ?????? ????? ???? ??????????? ? ???? ??????, ??? ?????? ????????? ????? ???????????? ????? ?????????
???????, ?????? ?????? ???? ????? ???????????? ??????? ??????? ??? ??? ??????????, ? ?????? ?????????? ???? ?????? ????? ???????????? ???????????:
?? ?????????? ????????? ? xi ????? ???????????? ??????? ? ??????,
i
??????? ????? ? ? ?????????, ?????? ?? ??????? ????? ???????????? ??????? xi;
?? ?????????? ????????? ? xi ????? ???????????? ??????? ? ??????,
i
??????? ????? ? ? ?????????, ?????? ?? ??????? ????? ???????????? ??????? xi;
?? ??????? ?r.C, ????? ??????????? ??????? ? ??????, ??????? ????? ?r
(??? r ? ????) ? ???????????? ????????, ?????????????? ??????? C;
?? ??????? ?r.C, ????? ??????????? ??????? ? ??????, ??????? ????? ?r
(??? r ? ????) ? ???????????? ????????, ?????????????? ??????? C;
?? ??????? ??????? C (¬C) ????? ??????????? ???????????? ????? ? ??????
C (¬C).
?????? ???????? ????????, ?????????? ????????????? ???? ???????????,
??????????? ?? ??????? 1. ??? ????????????? ????? ????? ???????????? ??
?????????.
??????????? ?????????? ????????? ??????????? ? ???, ????? ??????????
????? ?? ???????????? ???????????????? ????????????? ??? ?? ??????? ????????? ???? ??????. ??????? ??? ?????? ??????????? ?????????.
???. 1. ??????, ?????????????? ??????? ???????:
(?r.¬B??r.B?C?D)?(?r.¬B??(¬C??r.¬B?(¬D?C)))
Вестник Тюменского государственного университета.? 2012.? №? 4
??????????? ?????????? ????????? ...
145
??????? 1. ???? ? ???????????????? ????????????? I ?????????? ??????
x, ??????? ??????????? ????????? ????????? {C1,C2,?,Cn}, ?????, ???? ?????????? ????? ??????? D, ??? ?Ci ?¬D, ?? ??? ?????????? ????? ???????? ?
????????? {C1,C2,?,CnD}, ?? ?C?{C1,C2,?,Cn,D} : x?C, x??i/Ci.
??????????????.
???????????, ???
?i : ?x : x ? CiI , ??? ??? x?DI, ?? x??I / DI, ? ??? ???
x?i?: C
СiiII ?¬ D , ?? x ? C iI ??? ???, ??? x ? CiI , ? ?????? ????????????? ??????-
?? ??????????????. ?
????? R(x) ???????? ?????????, ?????????????? ?????????? ? ???????? x.
????????? ???? ?????? ???????? ??????? x, ??? P(x), ?????????????? i-?? ??????? ??????? ????????? ??? Pi(x). ????? ??? ??????????? ????, ???????????? ??
???????? R(x) ? ??????? R(y) ????? ???? ???????? ????????? ????????.
???????????????? ???????? ?????????? ????????????? DJ(x,y):
1. if R(x) ?D(R(y)) or R(y) ?D(R(xy)) then return true;
2. if x ????? ????? ? and y ????? ????? ? then
3. if ?p1 ? P(x)?p2 ? P(y) : DJ(R(p1), R(p2)) then
4. R(y) ? D(R(x))
5. return true;
6. if x ????? ????? ? and y ????? ????? ? then
7. if ?p1 ? P(x), ?p2 ? P(y), DJ(R(p1), R(p1)) then
8. R(y) ? D(R(x))
9.
return true;
10. if x ????? ????? ? and y ???????????? ??????? ??????? or ??????????
???????? ???????? or ????? ????? ?r, ?r then
11. if ?p ? P(x): DJ(R(p), R(y)) then R ( y ) ? D ( R ( x) , return true;
12. if x ????? ????? ? and y ????? ????? ? then
13. if ?p1 ? P(x)?p2 ? P(y) : DJ(R(p1), R(p2)) then
14. R(y) ? D(R(x))
15. return true;
16. if x ????? ????? ? and y ????? ????? ? then
17. if ?p2 ? P(y)?p1?P(x) : DJ(R(p1), R(p2)) then
18. R(y) ? D(R(x))
19. return true;
20. if x ????? ????? ? and if y ???????????? ??????? ??????? or ??????????
???????? ???????? or ????? ????? ?r, ?r then
21. if ?p?P(x) : DJ(R(p), R(y)) then
22. R(y) ? D(R(x))
23. return true;
24. if x ????? ????? ?r and y ????? ????? ?r and ???? ?????? ?????????
then
25. if DJ(P1(p), P1(y)) then
26. R(y) ? D(R(x))
27. return true;
28. if x ????? ????? ?r and y ????? ????? ?r and ???? ?????? ?????????
then
??????-?????????????? ?????. ???????????
© ?.?. ??????, ?.?.
?????????, ?.?. ?????????
146
© ?.?. ??????, ?.?. ?????????, ?.?. ?????????
29. if DJ(P1(x), P1(y)) then
30. R(y) ? D(R(x))
31. return true;
32. if x ???????????? ??????? ??????? and y ???????????? ??????? ???????
then
33. if R(x)?¬ R(y) then
34. R(y) ? D(R(x))
35. return true;
36. return false;
Check(C,E)
1. ????????? ???????? C ? E ? ??????????? ?????????;
2. x ? ?????? ??????, ??????????????? ??????? C;
3. y ? ?????? ??????, ??????????????? ??????? E;
4. if DJ (x,y) then
5. return C ?? ???????????? ? E;
???????, ??? ?????? ???????? ??????????? ?????????.
????? 1. ???? ??????? C ???????? ??????????? ????????? c1? c2?...? ck
? ??????? D ???????? ??????????? ????????? d1? d2?...? dh ? ?i,j : c1?¬ dj ???
i = i..k, j = 1..h, ?? C ?¬D ? ????? ???????????????? ????????????? I.
??????????????.
???????????, ??? ? ????????? ????????????? J ?x : x?CJ ? x?DJ, ?????
?i : x?ciJ ??? i=1..k ? ?j : x?diJ ??? j=1..h, ?? x??I / djI, ?? ??? ??? ?? ???????
????? ?i,j:ci?¬ cj, ?? x?ciJ, ? ?????? ????????????? J ???????? ??????????????,
?????? C?¬D ? ????? ???????????????? ?????????????. ?
????? 2. ???? ??????? C ???????? ??????????? ????????? c1? c2?...? ck
? ??????? D ???????? ??????????? ????????? d1? d2?...? dh ? ?i,?j : ci?¬ dj
??? i = i..k, j = 1..h, ?? C?¬D ? ????? ???????????????? ????????????? I.
??????????????.
???????????, ??? ? ????????? ????????????? J ?x : x?CJ ? x?DJ, ?????
?i : x?ciJ ??? i=1..k ? ?j:x?djJ ??? j=1..h, ?? x??J / djJ, ?? ??? ??? ?? ???????
????? ?i,?j : ci?¬ dj, ?? x?ciJ, ? ?????? ????????????? J ???????? ??????????????, ?????? C ?¬D ? ????? ???????????????? ?????????????. ?
????? 3. ???? ??????? C ???????? ??????????? ????????? c1? c2?...? ck
? ??????? D ???????? ??????????? ????????? d1? d2?...? dh ? ?i,?j : ci?¬ dj
??? i = i..k, j = 1..h, ?? C ?¬ D ? ????? ???????????????? ????????????? I.
??????????????.
???????????, ??? ? ????????? ????????????? J ?x : x?CJ ? x?DJ, ?????
?i:x?cjJ ??? i=1..k ? ?j:x?djJ ??? j=1..h, ?? x??J / djJ, ?? ??? ??? ?? ???????
????? ?i,?j : ci?¬ dj, ?? x?cjJ, ? ?????? ????????????? J ???????? ??????????????, ?????? C ?¬D ? ????? ???????????????? ?????????????. ?
????? 4. ???? C ?¬D, ?? x?CI ? x?DI ? ????? ???????????????? ????????????? I.
??????????????.
?????????? ???????????? ????????????? J. ???????????, ??? ??????????
J
J
J
J
J
J
????? ?????? x?C ? x?D , ????? x?? / D , ?????? x??C , ?? ?.?. x?C , ?? ??????????????? ????????????? ???????? ??????????????. ?
Вестник Тюменского государственного университета.? 2012.? №? 4
??????????? ?????????? ????????? ...
147
????? 5. ???? ??????? C ???????? ?????????? ? ??????????? ???????????? ?R.F ? ??????? D ?????????? ? ??????????? ???????????? ?P.E ? R=P ?
E?¬ F, ????? C?¬D.
??????????????.
???????????, ??? ? ????????? ????????????? J ?x : x?CJ ? x?DJ, ?????
?????? x ????? R-????????????? ?, ??????, ??? y?EJ, y?FJ, ?????? ?? ????? 4,
????????????? J ???????? ??????????????. ?
??????? 2.
???? ??? ?????????? ????????? 1, ???????? Check(C,E) ???????, ?????
EI??I/CI ? ????? ????????????? I.
??????????????.
??????? ?? ???????? ?? ?????? h ??????, ??????????????? ??????? C ?
?????? ?????? t, ??????????????? ??????? E:
??? h=1, t=1, C ? E ???????? ???????? ??????????, ????? ??????? DJ ?????? ???????? ???????? ?????? ??? E ?¬ C ? ?? ????? 4 EI??I/CI;
1. ???????????, ??? ??????? Check(C,E) ???????? ????????? ??? ????
h=h1, ? t=t1. ???????, ??? ??????? ???????? ????????? ??? h=h1+1 ? t=t1+1, ????? ??????? C ????? ?????? h1+1, ? ??????? E ????? ?????? t1+1.
?????????? 4 ??????:
?) ???? ??????? C ???????? ??????????? ?????? ?????????, ? ??????? E
???????? ???????????, ??? ??????? C ???????? ??????????? ?????? ?????????,
? ??????? E ???????? ??????????? ?????????, ????? ?? ????? 2 ???????????
EI??I/CI;
?) ???? ??????? C ???????? ??????????? ?????? ?????????, ? ??????? E
???????? ??????????? ?????????, ????? ?? ????? 3 ??????????? EI??I/CI;
?) ???? ??????? C ???????? ??????????? ?????? ?????????, ? ??????? E
???????? ??????????? ?????????, ????? ?? ????? 1 ??????????? EI??I/CI;
?) ???? ??????? C ?????????? ? ??????????? ???????????? ?R.F, ? ???????
E ?????????? ? ??????????? ???????????? ?P.D ? R=P, ????? ?? ????? 5 ??????????? EI??I/CI;
2. ???????????, ??? ??????? Check(C,E) ???????? ????????? ??? ????
h = h1 ? t = t1 . ??????? ??? ??????? ???????? ????????? ??? h=h1 ? t=t1+1,
????? ??????? C ????? ?????? h1, ? ??????? E ????? ?????? t1+1.
?????????? 2 ??????:
?) ???? ??????? C ?????????? ? ??????????? ???????????? ?R.F ???
???????????? ?R.F ? ??????? E ???????? ???????????, ????? ?? ????? 1 ???
???, ??? ??????? C ???????? ??????????? ?????? ?????????, ???????????
EI??I/CI;
?) ???? ??????? C ?????????? ? ??????????? ???????????? ?R.F ??? ???????????? ?R.F, ? ??????? E ???????? ???????????, ????? ?? ????? 2 ???
???, ??? ??????? C ???????? ??????????? ?????? ?????????, ???????????
EI??I/CI. ?
?????????? ?????? ?????? ?????????? ????????? ? ??????????? ??????
???????????.
??????-?????????????? ?????. ???????????
© ?.?. ??????, ?.?.
?????????, ?.?. ?????????
148
© ?.?. ??????, ?.?. ?????????, ?.?. ?????????
????? ????????? ?????? TBox ??????? ?? ????????? ??????:
1. ??????? ? ???????? ? ??????????.??????????? ??????;
2. ???????? ? ??????????.??????????? ?????? ? ¬????????????? ? ????????;
3. ??????? ? ¬??????????? ??????;
4. ????????????? ? ¬??????????? ??????;
5. ????????????? ? ????????;
? ?????? ?????? ?????????? ????????? ?????? ??????? ????? ??????????
? ??? ???????? ????????:
1. ¬??????? ? ???????? ? ??????????.??????????? ??????;
2. ¬???????? ? ??????????.¬??????????? ?????? ? ¬????????????? ?
????????;
3. ¬??????? ? ¬??????????? ??????;
4. ¬????????????? ? ¬??????????? ??????;
5. ¬????????????? ? ????????;
????? ???? ????? ?????? ?????? ????????????? x, ?????????? ? ????????????? ???????? ???????? (? ?????? ?????? ? ???????? ???????), ? ?? ????
???????????? ????????. ????? ?????? ?? ??????? ????????? ????? ???????
? ???????????? ? ????????? ?????????? ????????? [1], [3]. ??? ?????????
??????? ????????, ?? ????? ???? ?????? ??????? ¬???????, ??? ??? ? ????
?????? ?????? x ????? ??????? ? ????????? ¬??????? ? ???????, ??? ????????
? ?????????????? ?????????????, ?????????????? ????? ?????? ??????? ???????? ? ??????????.??????????? ??????. ??? ????????? ??????? ????????, ?????????? ??????? ???? ?? ????????? ??????????, ??????????????? ? ????
?????? ?? ???. 2, ? ????????? ?? ???????????????? ? ??? ???????????? ??????????, ??????????????? ?? ??????? 3.
???. 2. ???????????? ???????
Вестник Тюменского государственного университета.? 2012.? №? 4
??????????? ?????????? ????????? ...
149
???. 3. ??????????? ???????
??? ?????????? ?????? ????????? ??????, ??????????????? ?????? ? ??????? 4, ??????? Check(R(0),R(5)) ??????? ? ???, ??? ?????? ???????? ?? ????????????, ??? ??? R(5)?D(R(0)), ?????? ??? R(7)?D(R(1)), ??? ??? ????????
«????????» ? «¬????????» ???????? ????????????????? ? R(8)?D(R(2)), ??? ???
??? ??????? ????? ???? «?????????» ? R(9)?D(R(3)), ??? ??? ???????? «??????????? ??????» ? «¬??????????? ??????» ???????? ?????????????????.
???????????????? ????????????? ??????????? ????????? ??????????, ?????? ???, ?????????????? ?? ??????? 4.
???. 4. ????????????? ??????????? ????????? ??????????
??????
1. ??????????? ??????????? ?????????? ?????????, ??????? ???????? ????????? ?????????? ??????????? ???????? ?? ???? ?????????? ???????? ????????
???????????? ????????? ?????? ??? ????????? ??????????? ?????????.
??? ? ???? ??????? ???? ??????????? ???????????? ??? ??? ???????? ??? ??????
??????? ???????, ???, ????????, ?????????????? ????????????? ???????????
?????????????? ??????.
2. ???????? ???????????? ?????? ????????????????? ????????? ??? ?????
??? ??????, ????????? ?? ????? ?????????????? ?????? ALC.
??????-?????????????? ?????. ???????????
© ?.?. ??????, ?.?.
?????????, ?.?. ?????????
150
© ?.?. ??????, ?.?. ?????????, ?.?. ?????????
?????? ??????????
1. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., and Patel-Schneider, P.F., editors.
The Description Logic Handbook: Theory, Implementation and Applications. CUP, 2003. P.
601.
2. ?????? ?.?. ???????????????? ??????? ??????????? ????????: ?????????,
?????????? ? ?????? ?????? // ??????? ?????. 2002. ?3. ?. 21-27.
3. Sebastian Rudolph. Foundations of Description Logics // Axel Polleres, Claudia
d?Amato, Marcelo Arenas, Siegfried Handschuh, Paula Kroner, Sascha Ossowski, Peter F.
Patel-Schneider, Reasoning Web. Semantic Technologies for the Web of Data ? 7th
International Summer School 2011, Springer, LNCS, Vol.6848, 2011, ?. 76-136.
4. ?????? ?.?., ????????? ?.?. ????????-??????????????? ???? ??????????? ???
??????????? ???????? ????????? ?????????? ???????????? ??????????? // ???????
?????. 2008. ?6. ?. 152-158.
5. ?????? ?.?., ???????? ?.?. ??????????? ?????????? ???????? ????? ????? ???
????????? ??????? ??????-????????? // ??????? ?????. 2008. ?6. ?. 159-165.
6. Tsarkov, D. and Horrocks, I. FaCT++ Description Logic Reasoner: System Description
// Proc. of the Int. Joint Conf. on Automated Reasoning (IJCAR 2006), v. 4130 of Lecture
Notes in Artificial Intelligence, Springer, 2006, ?. 292-297.
Вестник Тюменского государственного университета.? 2012.? №? 4
Документ
Категория
Без категории
Просмотров
10
Размер файла
825 Кб
Теги
алгоритм, табличного, проверка, сложные, концептов, основы, модификация, непересекаемости
1/--страниц
Пожаловаться на содержимое документа