2011; Physical and Mathematical Sciences, 45(2 (225): 50–54
Shared with The Gufo

DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS

L.A. Haykazyan*

Received: 2025-02-22 · Published: 2011-04-28

© 2011 The Author(s) and the original publisher.

CC BY 4.0 This work is licensed under a Creative Commons Attribution 4.0 International License.
Shared article.
Original title
DECIDABILITY OF Δ-EQUIVALENCE PROBLEM FOR MONADIC LOGIC PROGRAMS
Author
L.A. Haykazyan
Published
2011-04-28
Licence
Creative Commons Attribution 4.0 International
Original
https://doi.org/10.46991/PYSUA.2011.45.2.050

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.
1 / ? 100% Open in new tab Download Cite

Loading the full text…

Download Follow Updates