Geodesic
On complexity of the anti-unification problem
Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 131-144

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we suggest a new algorithm of anti-unification of logic terms represented by acyclic directed graphs and estimate its complexity. The anti-unification problem consists of the following: for two given terms find the most specific term that has the given terms as instances. We suggest an anti-unification algorithm whose complexity linearly depends on the size of the most specific term it computes. It is thus established that the anti-unification problem is of almost the same complexity as the unification problem. It is also shown that there exist terms whose most specific term is of size $O(n^2)$, where $n$ is the size of the graphs representing these terms. 
@article{DM_2008_20_1_a11,
     author = {E. V. Kostylev and V. A. Zakharov},
     title = {On complexity of the anti-unification problem},
     journal = {Diskretnaya Matematika},
     pages = {131--144},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_1_a11/}
}
TY  - JOUR
AU  - E. V. Kostylev
AU  - V. A. Zakharov
TI  - On complexity of the anti-unification problem
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 131
EP  - 144
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_1_a11/
LA  - ru
ID  - DM_2008_20_1_a11
ER  - 
%0 Journal Article
%A E. V. Kostylev
%A V. A. Zakharov
%T On complexity of the anti-unification problem
%J Diskretnaya Matematika
%D 2008
%P 131-144
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_1_a11/
%G ru
%F DM_2008_20_1_a11
E. V. Kostylev; V. A. Zakharov. On complexity of the anti-unification problem. Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 131-144. http://geodesic.mathdoc.fr/item/DM_2008_20_1_a11/