Safe stratified Datalog with integer order does not have syntax
Alexei P. Stolboushkin, Michael A. Taitslin · ACM Transactions on Database Systems · 1998
Stratified Datalog with integer (gap)-order (or Datalog ¬,< z ) is considered. A Datalog ¬,< z -program is said to be safe if its bottom-up processing terminates on all valid inputs. We prove that safe Datalog ¬,< z programs do not have effective syntax in the sense that there is no recursively enumerable set S of safe Datalog ¬,< z programs such that every safe Datalog ¬,< z program is equivalent to a program in S .