Unification and matching on compressed terms
Authors:
Open Access
- 22 July 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 12 (4) , 1-37
Abstract
Term unification plays an important role in many areas of computer science, especially in those related to logic. The universal mechanism of grammar-based compression for terms, in particular the so-calledsingleton tree grammars (STGAs), have recently drawn considerable attention. Using STGs, terms of exponential size and height can be represented in linear space. Furthermore, the term representation by directed acyclic graphs (dags) can be efficiently simulated. The present article is the result of an investigation on term unification and matching when the terms given as input are represented using different compression mechanisms for terms such as dags and singleton tree grammars. We describe a polynomial time algorithm for context matching with dags, when the number of different context variables is fixed for the problem. For the same problem, NP-completeness is obtained when the terms are represented using the more general formalism of singleton tree grammars. For first-order unification and matching polynomial time algorithms are presented, each of them improving previous results for those problems.Keywords
All Related Versions
Funding Information
- LOGICTOOLS-2 (TIN2007-68093-C02-01)
- Ministerio de Educación, Cultura y Deporte (TIN2007-66523)
This publication has 25 references indexed in Scilit:
- On the complexity of Bounded Second-Order Unification and Stratified Context UnificationLogic Journal of the IGPL, 2010
- Context unification with one context variableJournal of Symbolic Computation, 2010
- Efficient memory representation of XML document treesInformation Systems, 2008
- Conjunctive queries over treesJournal of the ACM, 2006
- On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional TextsJournal of Computer and System Sciences, 2002
- An Efficient Unification AlgorithmACM Transactions on Programming Languages and Systems, 1982
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Linear unificationJournal of Computer and System Sciences, 1978
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977
- A Machine-Oriented Logic Based on the Resolution PrincipleJournal of the ACM, 1965