Context matching for compressed terms

Adrian Gascon Caro; Guillem Godoy; Manfred Schmidt-Schauss

doi:10.1109/LICS.2008.17

Context matching for compressed terms

Adrian Gascon Caro, Guillem Godoy, Manfred Schmidt-Schauss

School of Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Logic in Computer Science, 2008. LICS '08. 23rd Annual IEEE Symposium on
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	93-102
Number of pages	10
ISBN (Print)	978-0-7695-3183-0
DOIs	https://doi.org/10.1109/LICS.2008.17
Publication status	Published - 2008

Access to Document

10.1109/LICS.2008.17

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4557903

Cite this

@inproceedings{fa11fec2684e4253bd15774cb32f25d0,

title = "Context matching for compressed terms",

abstract = "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.",

author = "{Gascon Caro}, Adrian and Guillem Godoy and Manfred Schmidt-Schauss",

year = "2008",

doi = "10.1109/LICS.2008.17",

language = "English",

isbn = "978-0-7695-3183-0",

pages = "93--102",

booktitle = "Logic in Computer Science, 2008. LICS '08. 23rd Annual IEEE Symposium on",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

TY - GEN

T1 - Context matching for compressed terms

AU - Gascon Caro, Adrian

AU - Godoy, Guillem

AU - Schmidt-Schauss, Manfred

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1109/LICS.2008.17

DO - 10.1109/LICS.2008.17

M3 - Conference contribution

SN - 978-0-7695-3183-0

SP - 93

EP - 102

BT - Logic in Computer Science, 2008. LICS '08. 23rd Annual IEEE Symposium on

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

Context matching for compressed terms

Abstract

Access to Document

Fingerprint

Cite this