D:\sbornik\...\ipia-art.DVI


Mathematical Problems of Computer Science 24, 2005, 34{41.

On I nter pr eter s of Logic P r ogr amming Systems

S e m yo n A . N ig iya n a n d A r a m M. H a m b a r d z u m ya n

Department of System Programming,Yerevan State University,

e-mail nigiyan@ysu.am, me76@front.ru

Abstract

We introduce the notions of totally resolving and totally complete interpreters for
Horn programming languages. We prove the existence of totally complete interpreter
(an interpreter which gives all the answers for a query if the query is a logical conse-
quence of the program) for any Horn programming language and existence of totally
resolving interpreter (an interpreter which gives all the answers for any program and
query) for languages whose programs have ¯nite templates of their least models. We
also consider problems of total completeness and total resolvability for PROLOG in-
terpreter from viewpoint of some (natural) program transformations and prove that it
is not possible to make the interpreter totally complete.

Refer ences

[1 ] N ig iya n S . A ., K h a c h o ya n L . O. Transformations of L ogic P rograms. P r o g r a m m in g a n d
Co m p u t e r S o ft wa r e , V o l. 2 3 , N o . 6 , p p . 3 0 2 -3 0 9 , 1 9 9 7 .

[2 ] N ig iya n S . A , K h a c h o ya n L . O. On ¢ -equivalence problem of logic programs. R e p o r t s o f
N a t io n a l A c a d e m y o f S c ie n c e s o f A r m e n ia , V o l. 9 9 , N o . 2 , p p . 9 9 -1 0 3 ( in R u s s ia n ) , 1 9 9 9 .

[3 ] Clo c ks in W . F., Me llis h C. S . P rogramming in P rolog. B e r lin : S p r in g e r -V e r la g , 1 9 8 4 .

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

[5 ] N ig iya n S . A . The P rolog Interpreter from the Viewpoint of L ogical Semantics. P r o g r a m -
m in g a n d Co m p u t e r S o ft wa r e , V o l. 2 0 , N o . 2 , p p . 6 9 -7 5 , 1 9 9 4 .

[6 ] H a m b a r d z u m ya n A . M. The Completeness and Solvability P roblems for Simple M onadic
P R OL OG Interpreter. P r o c e e d in g s o f t h e Co n fe r e n c e o n Co m p u t e r S c ie n c e a n d In fo r m a -
t io n Te c h n o lo g ie s , Y e r e va n , p p . 3 6 -3 8 , 1 9 9 9 .

3 4



S. A. Nigiyan and A. M. Hambardzumyan 3 5

îñ³Ù³µ³Ý³Ï³Ý Íñ³·ñ³íáñÙ³Ý
ѳٳϳñ·»ñÇ ÇÝï»ñåñ»ï³ïáñÝ»ñÇ Ù³ëÇÝ

ê. ². ÜÇ·ÇÛ³Ý, ². Ø. гٵ³ñÓáõÙÛ³Ý

²Ù÷á÷áõÙ

²ß˳ï³ÝùáõÙ Ý»ñϳ۳óíáõÙ »Ý ïáï³É ÉáõÍ»ÉÇ ¨ ïáï³É ÉñÇí ÇÝï»ñåñ»ï³ïáñÝ»ñÇ
ѳëϳóáõÃÛáõÝÝ»ñÁ ÐáñÝÇ Íñ³·ñ³íáñÙ³Ý É»½áõÝ»ñÇ Ñ³Ù³ñ: ²å³óáõóíáõÙ ¿
ïáï³É ÉñÇí ÇÝï»ñåñ»ï³ïáñÇ (ÇÝï»ñåñ»ï³ïáñ, áñÁ ï³ÉÇë ¿ ѳñóÙ³Ý µáÉáñ
å³ï³ë˳ÝÝ»ñÁ, »Ã» ѳñóáõÙÁ ѳݹÇë³ÝáõÙ ¿ Íñ³·ñÇ ïñ³Ù³µ³Ý³Ï³Ý ѻ勉Ýù)
·áÛáõÃÛáõÝÁª Ï³Ù³Û³Ï³Ý ÐáñÝÇ Íñ³·ñ³íáñÙ³Ý É»½íÇ Ñ³Ù³ñ, ¨ ïáï³É ÉáõÍ»ÉÇ
ÇÝï»ñåñ»ï³ïáñÇ (ÇÝï»ñåñ»ï³ïáñ, áñÁ Ï³Ù³Û³Ï³Ý Íñ³·ñÇ ¨ ѳñóÙ³Ý Ñ³Ù³ñ
ï³ÉÇë ¿ µáÉáñ å³ï³ë˳ÝÝ»ñÁ) ·áÛáõÃÛáõÝÁ ³ÛÝ É»½áõÝ»ñÇ Ñ³Ù³ñ, áñáÝó Íñ³·ñ»ñÇ
÷áùñ³·áõÛÝ Ùá¹»ÉÝ»ñÇ ß³µÉáÝÝ»ñÁ í»ñç³íáñ »Ý: ܳ¨ ¹Çï³ñÏíáõÙ »Ý ïáï³É
ÉñÇíáõÃÛ³Ý ¨ ïáï³É ÉáõÍ»ÉÇáõÃÛ³Ý Ñ³ñó»ñÁ äðàÈà-Ç ÇÝï»ñåñ»ï³ïáñÇ Ñ³Ù³ñª
Íñ³·ñ»ñÇ ¨ ѳñóáõÙÝ»ñÇ áñáß (µÝ³Ï³Ý) Ó¨³÷áËáõÃÛáõÝÝ»ñÇ ï»ë³Ï»ïÇó, ¨
³å³óáõóíáõÙ ¿, áñ ÇÝï»ñåñ»ï³ïáñÁ Ñݳñ³íáñ ã¿ ¹³ñÓÝ»É ïáï³É ÉáõÍ»ÉÇ: