Geodesic
Decidability of $\Delta$-equivalence problem for monadic logic programs
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2011), pp. 50-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{UZERU_2011_2_a8,
     author = {L. A. Haykazyan},
     title = {Decidability of $\Delta$-equivalence problem for monadic logic programs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {50--54},
     year = {2011},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2011_2_a8/}
}
TY  - JOUR
AU  - L. A. Haykazyan
TI  - Decidability of $\Delta$-equivalence problem for monadic logic programs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2011
SP  - 50
EP  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZERU_2011_2_a8/
LA  - en
ID  - UZERU_2011_2_a8
ER  - 
%0 Journal Article
%A L. A. Haykazyan
%T Decidability of $\Delta$-equivalence problem for monadic logic programs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2011
%P 50-54
%N 2
%U http://geodesic.mathdoc.fr/item/UZERU_2011_2_a8/
%G en
%F UZERU_2011_2_a8
L. A. Haykazyan. Decidability of $\Delta$-equivalence problem for monadic logic programs. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2011), pp. 50-54. http://geodesic.mathdoc.fr/item/UZERU_2011_2_a8/

[1] S.A. Nigiyan, L.O. Khachoyan, “Transformations of Logic Programs”, Programming and Computer Software, 23 (1997), 302–309 (in Russian) | MR | Zbl

[2] A. Matos, “Monadic logic programs and functional complexity”, Theoretical Computer Science, 176 (1997), 175–204 | DOI | MR | Zbl

[3] J. Lloyd, Foundations of Logic Programming, Springer-Verlag, 1984, 124 pp. | MR | Zbl

[4] M. Rabin, “Decidability of second-order theories and automata on infinite trees”, Bulletin of the American Mathematical Society, 74 (1968), 1025–1029 | DOI | MR | Zbl