Unification for Compressed Terms

Master Specialization:  Algorithmics and  Programming
Topic Aproval date: 20/03/09
Orientation: research

Student: Adrià Gascó Caro
Thesis advisor(s): Guillem Godoy Balil
Contact: ggodoy at lsi.upc.edu

Term unification is a fundamental concept in many areas of computer science. This problem is efficiently solvable for plain terms. However, many applications of this problem require a succint representation for terms.
We introduce efficient algorithms for term unification where the inputted terms are represented by Singleton Tree Grammars (STGs), which is a grammar-based compression mechanism of big interest in recent research.