Context matching for compressed terms

Adrian Gascon Caro, Guillem Godoy, Manfred Schmidt-Schauss

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

Abstract / Description of output

This paper is an investigation of the matching problem for term equations s = t where s contains context variables and first-order variables, and both terms s and t are given using some kind of compressed representation. The main result is a polynomial time algorithm for context matching with dags, when the number of different context variables is fixed for the problem. NP-completeness is obtained when the terms are represented using the more general formalism of singleton tree grammars. As an ingredient of this proof, we also show that the special case of first-order matching with singleton tree grammars is decidable in polynomial time.
Original languageEnglish
Title of host publicationLogic in Computer Science, 2008. LICS '08. 23rd Annual IEEE Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Print)978-0-7695-3183-0
Publication statusPublished - 2008


Dive into the research topics of 'Context matching for compressed terms'. Together they form a unique fingerprint.

Cite this