DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS
DOI:
https://doi.org/10.46991/PYSU:A/2011.45.2.050Keywords:
logic programming, Δ-equivalenceAbstract
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
Issue
Section
Informatics
License
Copyright (c) 2011 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.