|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2011, Issue 2, Pages 50–54
(Mi uzeru182)
|
|
|
|
Informatics
Decidability of $\Delta$-equivalence problem for monadic logic programs
L. A. Haykazyan Chair of Programming and Information Technologies YSU, Armenia
Abstract:
In the present paper the $\Delta$-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 $\Delta$-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, $\Delta$-equivalence.
Received: 17.09.2010 Accepted: 20.10.2010
Citation:
L. A. Haykazyan, “Decidability of $\Delta$-equivalence problem for monadic logic programs”, Proceedings of the YSU, Physical and Mathematical Sciences, 2011, no. 2, 50–54
Linking options:
https://www.mathnet.ru/eng/uzeru182 https://www.mathnet.ru/eng/uzeru/y2011/i2/p50
|
Statistics & downloads: |
Abstract page: | 52 | Full-text PDF : | 15 | References: | 15 |
|