DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS

Author(s)

DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS L.A. Haykazyan

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.

DOI: 10.46991/PYSUA.2011.45.2.050 Physical and Mathematical Sciences, 45(2 (225) 50-54

Download PDF

Keywords

logic programming, Δ-equivalence

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]