Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/13343

Unification and matching on compressed terms
Gascón Caro, Adrià; Godoy Balil, Guillem; Schmidt-Schauß, Manfred
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
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 (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.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Lambda calculus
Singleton tree grammars
Algorithms
Càlcul lambda
Llenguatges formals
Algorismes
info:eu-repo/semantics/publishedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Creus López, Carles; Gascón Caro, Adrià; Godoy Balil, Guillem; Ramos, Lander
Creus López, Carles; Gascón Caro, Adrià; Godoy Balil, Guillem
Barguño, Luis; Creus López, Carles; Godoy Balil, Guillem; Jacquemard, Florent; Vacher, Camile
Creus López, Carles; Godoy Balil, Guillem; Massanes Basi, Francesc d'Assis; Tiwari, Ashish Kumar