D:\sbornik\...\nas.DVI


Mathematical Problems of Computer Science 36, 7{12, 2012.

T he Degr ee of Unsolvability of the Completion

Semantics for Gener al Logic P r ogr ams

L e vo n A . H a yka z ya n

Yerevan State University

e-mail levon@rock.com

Abstract

The completion semantics considers interpretations that satisfy a special ¯rst-order
theory was ¯rst introduced in [1]. These interpretations include but are not limited
to Herbrand interpretations. Nevertheless, in logic programming the restriction to
Herbrand interpretations is very desirable. As [2] remarks, however, this results in a
non-recursively enumerable semantics. In this paper we show the ¦11-completeness of
the completion semantics with restriction to Herbrand interpretations.

Refer ences

[1 ] K . L . Cla r k, \ N e g a t io n a s fa ilu r e " , In H. Gallaire, J . M inker, L ogic and D atabeses, p p
2 9 3 -3 2 3 , P le n u m , 1 9 7 8 .

[2 ] J. C. S h e p h e r d s o n , \ N e g a t io n a s fa ilu r e , c o m p le t io n a n d s t r a t ī c a t io n " , In D . M .
Gabbay, C. J . Hogger, J . A. R obinson, L ogic P rogramming, p p 3 5 5 -4 1 9 , Cla r e n d o n
P r e s s , 1 9 9 8 .

[3 ] J. W . L lo yd , R . W . To p o r , \ Ma kin g p r o lo g m o r e e xp r e s s ive " , J ournal of L ogic P ro-
gramming, vo l. 1 , p p . 2 2 5 -2 4 0 , 1 9 8 4 .

[4 ] J. W . L lo yd , F oundations of L ogic P rogramming, S p r in g e r -V e r la g , 1 9 9 4 .

[5 ] H . R o g e r s , The Theory of R ecursive F unctions and E ®ective Computability, Mc Gr a w-
H ill, 1 9 6 7 .

ÀݹѳÝñ³óí³Í ïñ³Ù³µ³Ý³Ï³Ý Íñ³·ñ»ñÇ ÷³ÏÙ³Ý
ë»Ù³ÝïÇϳÛÇ ³ÝÉáõÍ»ÉÇáõÃÛ³Ý ³ëïÇ׳ÝÁ

È. гÛϳ½Û³Ý

²Ù÷á÷áõÙ

ö³ÏÙ³Ý ë»Ù³ÝïÇÏ³Ý Ý»ñÙáõÍí»É ¿ [1] ³ß˳ïáõÃÛáõÝáõÙ, áõñ ¹Çï³ñÏíáõÙ »Ý
ÇÝï»ñåñ»ï³ódzݻñ, áñáÝù µ³í³ñ³ñáõÙ »Ý ѳïáõÏ ³é³çÇÝ Ï³ñ·Ç ï»ëáõÃÛ³Ý:
²Ûë ÇÝï»ñåñ»ï³ódzݻñÁ Ý»ñ³éáõÙ »Ý, µ³Ûó ã»Ý ë³Ñٳݳ÷³Ïíáõ٠лñµñ³ÝÇ
ÇÝï»ñåñ»ï³ódzݻñáí: ²ÛÝáõ³Ù»Ý³ÛÝÇí, ïñ³Ù³µ³Ý³Ï³Ý Íñ³·ñ³íáñÙ³Ý Ù»ç

7



8 The Degree of Unsolvability of the Completion Semantics for General Logic Programs

лñµñ³ÝÇ ÇÝï»ñåñ»ï³ódzݻñáí ë³Ñٳݳ÷³ÏáõÙÁ ËÇëï ó³ÝϳÉÇ ¿: ê³Ï³ÛÝ
ÇÝãå»ë ÝßíáõÙ ¿ [2] ³ß˳ïáõÃÛáõÝáõÙ, ¹³ µ»ñáõÙ ¿ áã é»ÏáõñëÇíáñ»Ý Ãí³ñÏ»ÉÇ
ë»Ù³ÝïÇϳÛÇ: êáõÛÝ ³ß˳ïáõÃÛáõÝáõÙ óáõÛó ¿ ïñíáõÙ ÷³ÏÙ³Ý ë»Ù³ÝïÇϳÛÇ ¦ 11-
ÉñÇíáõÃÛáõÝÁ лñµñ³ÝÇ ÇÝï»ñåñ»ï³ódzݻñáí ë³Ñٳݳ÷³ÏÙ³Ý ¹»åùáõÙ:

Ñòåïåíü íåðàçðåøèìîñòè ñåìàíòèêè çàìûêàíèÿ
îáîáùåííûõ ëîãè÷åñêèõ ïðîãðàìì

Ë. Àéêàçÿí

Àííîòàöèÿ

Ñåìàíòèêà çàìûêàíèÿ áûëà ââåäåíà â ðàáîòå [1], â êîòîðîé ðàññìàòðèâàþòñÿ
èíòåðïðåòàöèè, óäîâëåòâîðÿþùèå ñïåöèàëüíîé òåîðèè ïåðâîãî ïîðÿäêà.
Ýòè èíòåðïðåòàöèè âêëþ÷àþò â ñåáÿ Ýðáðàíîâñêèå èíòåðïðåòàöèè, íî íå
îãðàíè÷èâàþòñÿ èìè. Òåì íå ìåíåå â ëîãè÷åñêîì ïðîãðàììèðîâàíèè
îãðàíè÷åíèå Ýðáðàíîâñêèìè èíòåðïðåòàöèÿìè âåñüìà æåëàòåëüíî. Îäíàêî, êàê
îòìå÷åíî â ðàáîòå [2], ýòî ïðèâîäèò ê íå ðåêóðñèâíî ïåðå÷èñëèìîé ñåìàíòèêå. Â
äàííîé ðàáîòå ïîêàçûâàåòñÿ ¦ 11 -ïîëíîòà ñåìàíòèêè çàìûêàíèÿ ïðè îãðàíè÷åíèè
Ýðáðàíîâñêèìè èíòåðïðåòàöèÿìè.