On functional symbol-free logic programs

В статье рассматриваются логические программы без функциональных символов, использующие и не использующие отрицание. Обсуждены три алгоритмические проблемы: существование разрешающего интерпретатора, $\Delta$-эквивалентность логических программ и обычная эквивалентность логических программ. Известна разрешимость первых двух проблем для программ, не использующих отрицание. В данной работе показывается разрешимость третьей проблемы для таких программ и неразрешимость всех трех проблем для программ, использующих отрицание.