Unification with Singleton Tree Grammars

Adria Gascón, Guillem Godoy, Manfred Schmidt-Schauß

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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-called Singleton Tree Grammars (STG), 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 paper 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.
Original languageEnglish
Title of host publicationRewriting Techniques and Applications
Subtitle of host publication20th International Conference, RTA 2009 Brasília, Brazil, June 29 - July 1, 2009 Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-642-02348-4
ISBN (Print)978-3-642-02347-7
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Unification with Singleton Tree Grammars'. Together they form a unique fingerprint.

Cite this