Geodesic
On optimization of monadic logic programs
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2014), pp. 40-47 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The article is devoted to the optimization of monadic logic programs and goals (programs and goals, which do not use functional symbols of arity $\ > 1$ and use only predicate symbols of arity $1$). A program $P$ is terminating with respect to a goal $G$, if an SLD-tree of $P$ and $G$ is finite. In general, monadic programs are not terminating. Program and goal transformations are introduced, by which a monadic program $P$ and a variable-free monadic goal $G$ are transformed into $P^{\prime}$ and $G^{\prime}$, such that $P^{\prime}$ is terminating with respect to $G^{\prime}$ and $P \models G$, if and only if $P^{\prime}\models G^{\prime}$. Note that the transformed program $P^{\prime}$ is the same for all goals.
Keywords: monadic logic programs, optimization
Mots-clés : termination, transformation. 
@article{UZERU_2014_1_a7,
     author = {S. A. Khachatryan},
     title = {On optimization of monadic logic programs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {40--47},
     year = {2014},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2014_1_a7/}
}
TY  - JOUR
AU  - S. A. Khachatryan
TI  - On optimization of monadic logic programs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2014
SP  - 40
EP  - 47
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UZERU_2014_1_a7/
LA  - en
ID  - UZERU_2014_1_a7
ER  - 
%0 Journal Article
%A S. A. Khachatryan
%T On optimization of monadic logic programs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2014
%P 40-47
%N 1
%U http://geodesic.mathdoc.fr/item/UZERU_2014_1_a7/
%G en
%F UZERU_2014_1_a7
S. A. Khachatryan. On optimization of monadic logic programs. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2014), pp. 40-47. http://geodesic.mathdoc.fr/item/UZERU_2014_1_a7/

[1] Yu.Sh. Gurevich, “The Decision Problem for the Logic of Predicates and of Operations”, Algebra and Logic, 8:3 (1969), 160–174 | DOI

[2] L. Cavedon, “Acyclic Logic Programs and the Completeness of SLDNF-Resolution”, Theoretical Comput., 86 (1991), 81–92 | DOI | MR | Zbl

[3] M.A. Bezem, “Strong Termination of Logic Programs”, Journal of Logic Programming, 15:1 $\$ 2 (1993), 79–97 | DOI | MR | Zbl

[4] J.W. Lloyd, Foundations of Logic Programming, Springer-Verlag, 1984 | MR | Zbl

[5] U. Nilsson, J. Maluszski, Logic, Programming and PROLOG, ed. 2, John Wiley $\$ Sons Inc., 1995

[6] A.B. Matos, “Monadic Logic Programs and Functional Complexity”, Theoretical Computer Science, 176 (1997), 175–204 | DOI | MR | Zbl

[7] S. Khachatryan, “On the Optimization of Variable-Free Logic Programs”, Proceedings of CSIT, 2011, 50–51

[8] N. Dershowitz, “Dermination of Rewriting”, J. Symbolic Comput., 3 (1987), 69–116 | DOI | MR

[9] N. Vereshchagin, A. Shen, Basic Set Theory, AMS, 2002 | MR | Zbl