%
% GENERATED FROM https://www.coli.uni-saarland.de
%    by   : anonymous
%    IP   : coli2006.lst.uni-saarland.de
%    at   : Mon, 05 Feb 2024 15:43:34 +0100 GMT
%    
% Selection : Author: Philippe_Devienne
%




@Article{Devienne_et_al:1996,
      AUTHOR = {Devienne, Philippe and Lebegue, Patrick and Parrain, Anne and Routier, Jean-Christophe and Würtz, Jörg},
      TITLE = {Smallest Horn Clause Programs},
      YEAR = {1996},
      JOURNAL = {Journal of Logic Programming},
      VOLUME = {27},
      NUMBER = {3},
      PAGES = {227-267},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/JLP96.ps.gz},
      ABSTRACT = {The simplest non-trivial program pattern in logic programming is the following one : $$left\beginarrayl p(	extitfact)leftarrow\ p(	extitleft)leftarrow p(	extitright).\ leftarrow p(	extitgoal). endarray
ight.defglobble#1gobble$$ where 	extitfact, 	extitgoal, 	extitleft and 	extitright are arbitrary terms. Because the well known 	extitappend program matches this pattern, we will denote such programs 	extitappend-like''. In spite of their simple appearance, we prove in this paper that termination and satisfiability (i.e the existence of answer-substitutions, called the 	extitemptiness problem) for are undecidable. We also study some subcases depending on the number of occurrences of variables in 	extitfact, 	extitgoal, 	extitleft or 	extitright. Moreover, we prove that the computational power of 	extitappend-like programs is equivalent to the one of Turing machines ; we show that there exists an 	extitappend-like universal program. Thus, we propose an equivalent of the Böhm-Jacopini theorem for logic programming. This result confirms the expressiveness of logic programming. The proofs are based on program transformations and encoding of problems, unpredictable iterations within number theory defined by J.H. Conway or the Post correspondence problem.},
      ANNOTE = {COLIURL : Devienne:1996:SHC.pdf Devienne:1996:SHC.ps}
}