Abstract
We study anti-unification for unranked terms and hedges that may contain term and hedge variables. The anti-unification problem of two hedges \({\tilde{s}}_1\) and \({\tilde{s}}_2\) is concerned with finding their generalization, a hedge \({\tilde{q}}\) such that both \({\tilde{s}}_1\) and \({\tilde{s}}_2\) are instances of \({\tilde{q}}\) under some substitutions. Hedge variables help to fill in gaps in generalizations, while term variables abstract single (sub)terms with different top function symbols. First, we design a complete and minimal algorithm to compute least general generalizations. Then, we improve the efficiency of the algorithm by restricting possible alternatives permitted in the generalizations. The restrictions are imposed with the help of a rigidity function, which is a parameter in the improved algorithm and selects certain common subsequences from the hedges to be generalized. The obtained rigid anti-unification algorithm is further made more precise by permitting combination of hedge and term variables in generalizations. Finally, we indicate a possible application of the algorithm in software engineering.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aït-Kaci, H., Sasaki, Y.: An axiomatic approach to feature term generalization. In: Raedt, L.D., Flach, P.A. (eds.) ECML. Lecture Notes in Computer Science, vol. 2167, pp. 1–12. Springer, Heidelberg (2001)
Alpuente, M., Escobar, S., Meseguer, J., Ojeda, P.: A modular equational generalization algorithm. In: Hanus, M. (ed.) LOPSTR. Lecture Notes in Computer Science, vol. 5438, pp. 24–39. Springer, Heidelberg (2008)
Alpuente, M., Escobar, S., Meseguer, J., Ojeda, P.: Order-sorted generalization. Electr. Notes Theor. Comput. Sci. 246, 27–38 (2009)
Armengol, E., Plaza, E.: Bottom-up induction of feature terms. Mach. Learn. 41(3), 259–294 (2000)
Baader, F.: Unification, weak unification, upper bound, lower bound, and generalization problems. In: Book, R.V. (ed.) RTA. Lecture Notes in Computer Science, vol. 488, pp. 86–97. Springer, Heidelberg (1991)
Baxter, I.D., Yahin, A., de Moura, L.M., Sant’Anna, M., Bier, L.: Clone detection using abstract syntax trees. In: ICSM, pp. 368–377 (1998)
Biere, A.: Normalisation, unification and generalisation in free monoids. Master’s thesis, University of Karlsruhe (in German, 1993)
Bulychev, P., Minea, M.: An evaluation of duplicate code detection using anti-unification. In: Proc. 3rd International Workshop on Software Clones (2009)
Bulychev, P.E., Kostylev, E.V., Zakharov, V.A.: Anti-unification algorithms and their applications in program analysis. In: Pnueli, A., Virbitskaite, I., Voronkov, A. (eds.) Ershov Memorial Conference. Lecture Notes in Computer Science, vol. 5947, pp. 413–423. Springer, Heidelberg (2009)
Burghardt, J.: E-generalization using grammars. Artif. Intell. 165(1), 1–35 (2005)
Cicekli, I., Cicekli, N.K.: Generalizing predicates with string arguments. Appl. Intell. 25(1):23–36 (2006)
Cirstea, H., Kirchner, C., Kopetz, R., Moreau, P.E.: Anti-patterns for rule-based languages. J. Symb. Comput. 45(5), 523–550 (2010)
Delcher, A.L., Kasif, S.: Efficient parallel term matching and anti-unification. J. Autom. Reasoning 9(3), 391–406 (1992)
Evans, W.S., Fraser, C.W., Ma, F.: Clone detection via structural abstraction. Softw. Qual. J. 17(4), 309–330 (2009)
Gusfield, D.: Algorithms on Strings, Trees, and Sequences—Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)
Huet, G.: Résolution d’équations dans des langages d’ordre 1,2,...,ω. PhD thesis, Université Paris VII (1976)
Kitzelmann, E., Schmid, U.: Inductive synthesis of functional programs: an explanation based generalization approach. J. Mach. Learn. Res. 7, 429–454 (2006)
Koschke, R., Falke, R., Frenzel, P.: Clone detection using abstract syntax suffix trees. In: WCRE, pp. 253–262. IEEE Computer Society (2006)
Krumnack, U., Schwering, A., Gust, H., Kühnberger, K.U.: Restricted higher-order anti-unification for analogy making. In: Orgun, M.A., Thornton, J. (eds.) Australian Conference on Artificial Intelligence. Lecture Notes in Computer Science, vol. 4830, pp. 273–282. Springer, Heidelberg (2007)
Kutsia, T.: Solving equations with sequence variables and sequence functions. J. Symb. Comput. 42(3), 352–388 (2007)
Kutsia, T.: Flat matching. J. Symb. Comput. 43(12), 858–873 (2008)
Kutsia, T., Marin, M.: Matching with regular constraints. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR. Lecture Notes in Computer Science, vol. 3835, pp. 215–229. Springer, Heidelberg (2005)
Kutsia, T., Marin, M.: Order-sorted unification with regular expression sorts. In: Lynch, C. (ed.) RTA, Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 6, pp. 193–208 (2010)
Kutsia, T., Levy, J., Villaret, M.: Sequence unification through currying. In: Baader, F. (ed.) RTA. Lecture Notes in Computer Science, vol. 4533, pp. 288–302. Springer, Heidelberg (2007)
Kutsia, T., Levy, J., Villaret, M.: On the relation between context and sequence unification. J. Symb. Comput. 45(1), 74–95 (2010)
Kutsia, T., Levy, J., Villaret, M.: Anti-unification for unranked terms and hedges. In: Schmidt-Schauß, M. (ed.) RTA. Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 10, pp. 219–234 (2011)
Li, H., Thompson, S.J.: Similar code detection and elimination for erlang programs. In: Carro, M., Peña, R. (eds.) PADL. Lecture Notes in Computer Science, vol. 5937, pp. 104–118. Springer, Heidelberg (2010)
Lu, J., Mylopoulos, J., Harao, M., Hagiya, M.: Higher order generalization and its application in program verification. Ann. Math. Artif. Intell. 28(1–4), 107–126 (2000)
Pfenning, F.: Unification and anti-unification in the calculus of constructions. In: LICS, pp. 74–85. IEEE Computer Society (1991)
Plaza, E.: Cases as terms: a feature term approach to the structured representation of cases. In: Veloso, M.M., Aamodt, A. (eds.) ICCBR. Lecture Notes in Computer Science, vol. 1010, pp. 265–276. Springer, Heidelberg (1995)
Plotkin, G.D.: A note on inductive generalization. Mach. Intell. 5(1), 153–163 (1970)
Reynolds, J.C.: Transformational systems and the algebraic structure of atomic formulas. Mach. Intell. 5(1), 135–151 (1970)
Roy, C.K., Cordy, J.R.: A Survey of Software Clone Detection Research. Tech. rep., School of Computing, Queen’s University at Kingston, ON, Canada (2007)
Roy, C.K., Cordy, J.R., Koschke, R.: Comparison and evaluation of code clone detection techniques and tools: a qualitative approach. Sci. Comput. Program 74(7), 470–495 (2009)
Schmid, U.: Inductive synthesis of functional programs, universal planning, folding of finite programs and schema abstraction by analogical reasoning. In: Lecture Notes in Computer Science, vol. 2654. Springer, Heidelberg (2003)
Wahler, V., Seipel, D., von Gudenberg, J.W., Fischer, G.: Clone detection in source code by frequent itemset techniques. In: SCAM, pp. 128–135. IEEE Computer Society Press, Los Alamitos (2004)
Yamamoto, A., Ito, K., Ishino, A., Arimura, H.: Modelling semi-structured documents with hedges for deduction and induction. In: Rouveirol, C., Sebag, M. (eds.) ILP. Lecture Notes in Computer Science, vol. 2157, pp. 240–247. Springer, Heidelberg (2001)
Yang, W.: Identifying syntactic differences between two programs. Softw. Pract. Exper. 21(7), 739–755 (1991)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been partially supported by the Spanish Ministerio de Economa y Competitividad under the projects HeLo (TIN2012-33042) and TASSAT (TIN2010-20967-C04-01), by the EC FP6 for Integrated Infrastructures Initiatives under the project SCIEnce (contract No. 026133), by the Austrian Science Fund (FWF) under the project SToUT (P 24087-N18), and by the Generalitat de Catalunya under the grant AGAUR 2009-SGR-1434.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Kutsia, T., Levy, J. & Villaret, M. Anti-unification for Unranked Terms and Hedges. J Autom Reasoning 52, 155–190 (2014). https://doi.org/10.1007/s10817-013-9285-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10817-013-9285-6