RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskr. Mat., 2008, Volume 20, Issue 1, Pages 131–144 (Mi dm996)  

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


Abstract: 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.

DOI: https://doi.org/10.4213/dm996

Full text: PDF file (197 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2008, 18:1, 85–98

Bibliographic databases:

UDC: 519.7
Received: 14.06.2007

Citation: 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
\Bibitem{KosZak08}
\by E.~V.~Kostylev, V.~A.~Zakharov
\paper On complexity of the anti-unification problem
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 1
\pages 131--144
\mathnet{http://mi.mathnet.ru/dm996}
\crossref{https://doi.org/10.4213/dm996}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2420504}
\zmath{https://zbmath.org/?q=an:1176.68092}
\elib{http://elibrary.ru/item.asp?id=20730236}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 1
\pages 85--98
\crossref{https://doi.org/10.1515/DMA.2008.007}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-64549163164}


Linking options:
  • http://mi.mathnet.ru/eng/dm996
  • https://doi.org/10.4213/dm996
  • http://mi.mathnet.ru/eng/dm/v20/i1/p131

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Zakharov V.A., Novikova T.A., “Primenenie algebry podstanovok dlya unifikatsii programm”, Trudy Instituta sistemnogo programmirovaniya RAN, 21 (2011), 141–166  elib
    2. Novikova T.A., Zakharov V.A., “Unifikatsiya programm”, Trudy Instituta sistemnogo programmirovaniya RAN, 23 (2012), 455–476  elib
  • Дискретная математика
    Number of views:
    This page:401
    Full text:115
    References:38
    First page:17

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020