On complexity of the anti-unification problem

DOI10.1515/DMA.2008.007MaRDI QIDQ3184519zbMATH OpenOpenAlexFDO

Authors Egor V. Kostylev, Vladimir A. Zakharov

Publication date 21 October 2009

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma.2008.007

zbMATH Keywords

acyclic directed graphsanti-unification algorithmanti-unification of logic termscomputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A note on the parallel complexity of anti-unification
• Unifications, deunifications, and their complexity
• scientific article; zbMATH DE number 3995082
• On the complexity of Boolean unification
• The undecidability of the D_A-unification problem
• COMPLEXITY OF UNIVERSAL CIRCUMSCRIPTION
• The undecidability of the semi-unification problem
• Publication:3204025
• Complexity of unification problems with associative-commutative operators
• On quasi-inconsistency and its complexity

Cites work

• A Machine-Oriented Logic Based on the Resolution Principle
• A note on the parallel complexity of anti-unification
• An Efficient Unification Algorithm
• Efficient parallel term matching and anti-unification
• Linear unification
• Properties of substitutions and unifications
• The logic-termal equivalence is polynomial-time decidable

Cited in

(8)

• Anti-unification algorithms and their applications in program analysis
• Idempotent anti-unification
• Term-graph anti-unification
• A new algorithm for computing least generalization of a set of atoms
• Anti-unification in constraint logic programming
• On Asymmetric Unification and the Combination Problem in Disjoint Theories
• Anti-unification of unordered goals
• A note on the parallel complexity of anti-unification

This page was built for publication: On complexity of the anti-unification problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3184519)