DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS - Haykazyan, L.A. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2011)
Chair of Programming and Information Technologies, YSU In the present paper the Δ-equivalence problem of monadic logic programs (logic programs using only monadic functional and predicate symbols) is investigated. It is shown that contrary to the general case, the relation of Δ-equivalence is decidable in case of monadic programs. Our proof is based on the decidability of Rabin’s monadic second order logic of successor functions.
Keywords: logic programming; Δ-equivalence