逻辑学文章
ARTIFICIAL INTELLIGENCE
237
RESEARCH NOTE
On the Existence of Nonterminating Queries for a Restricted Class of PROLOG-Clauses Danny de Schreye*, Maurice Bruynooghe**, Kristof Verschaetse* D e p a r t m e n t o f C o m p u t e r S c t e n c e, K a t h o h e k e Untversttett L e u v e n, Celestljnenlaan 2 0 0 A, 3 0 3 0 H e v e r l e e, B e l g i u m
ABSTRACT Thts work studtes the extstence of nontermmatmg quertes for a restrtcted class of recurstve predtcates The class ts restrtcted to predtcates defined by a set of clauses contammg only one (dtrect) recurslve clause Moreover, thzs clause must be of the form P( ) - P( ) For this restrtcted cla~s of predtcates, we prove a necessary and sufficwnt condmon for the extstence of a query whtch is nontermmatmg tn the absence of the occur check The condttton t9 based upon concepts from rattonal trees
I. Introduction O u r w o r k was i n s p i r e d by a c o n j e c t u r e of S m i t h, G e n e s e r e t h a n d G i n s b e r g[11] on a n e c e s s a r y c o n d i t i o n for the e x i s t e n c e of an m f i m t e c o m p u t a t i o n a l p a t h for a class o f p r o g r a m s called cyclic collections. W i t h t h e t e r m i n o l o g y of[9] a cyclic c o l l e c t i o n is a set o f definite H o r n clauses of the type: !
PI: - P 2, t
B1,
Pz: - P3, B2,
P.:- PI, B
,
* Supported by the Belgian IWONL-IRSIA under contract number 5203 ** Supported by the Belgian National Fund for Scmntlfic Research Artlfictal lntelhgence 41 (1989/90) 237-248 0004-3702/89/$3 50© 1989, Elsevier Scmnce Pubhshers B V (North-Holland)

热门文档