DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS

L.A. Haykazyan

doi:10.46991/PYSU:A/2011.45.2.050

DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS

Authors

L.A. Haykazyan Chair of Programming and Information Technologies, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2011.45.2.050

Keywords:

logic programming, Δ-equivalence

Abstract

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.

Downloads

Published

2011-04-28

How to Cite

Haykazyan, L. (2011). DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS. Proceedings of the YSU A: Physical and Mathematical Sciences, 45(2 (225), 50–54. https://doi.org/10.46991/PYSU:A/2011.45.2.050