This article is cited in 2 scientific papers (total in 2 papers)
On complexity of the anti-unification problem
E. V. Kostylev, V. A. Zakharov
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.
PDF file (197 kB)
Discrete Mathematics and Applications, 2008, 18:1, 85–98
E. V. Kostylev, V. A. Zakharov, “On complexity of the anti-unification problem”, Diskr. Mat., 20:1 (2008), 131–144; Discrete Math. Appl., 18:1 (2008), 85–98
Citation in format AMSBIB
\by E.~V.~Kostylev, V.~A.~Zakharov
\paper On complexity of the anti-unification problem
\jour Diskr. Mat.
\jour Discrete Math. Appl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Zakharov V.A., Novikova T.A., “Primenenie algebry podstanovok dlya unifikatsii programm”, Trudy Instituta sistemnogo programmirovaniya RAN, 21 (2011), 141–166
Novikova T.A., Zakharov V.A., “Unifikatsiya programm”, Trudy Instituta sistemnogo programmirovaniya RAN, 23 (2012), 455–476
|Number of views:|