HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables

Iovka Boneva 1 Joachim Niehren 1 Momar Sakho 1, *
* Corresponding author
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : We study the complexity of regular matching and inclusion for compressed tree patterns with context variables subject to regular constraints. Context variables with regular constraints permit to properly generalize on unranked tree patterns with hedge variables. Regular inclusion on unranked tree patterns is relevant to certain query answering on Xml streams with references. We show that regular matching and inclusion with regular constraints can be reduced in polynomial time to the corresponding problem without regular constraints.
Complete list of metadata

https://hal.inria.fr/hal-03151014
Contributor : Inria Links Connect in order to contact the contributor
Submitted on : Wednesday, February 24, 2021 - 1:16:07 PM
Last modification on : Friday, April 1, 2022 - 3:49:12 AM
Long-term archiving on: : Tuesday, May 25, 2021 - 6:34:17 PM

File

0-long.pdf
Files produced by the author(s)

Identifiers

Citation

Iovka Boneva, Joachim Niehren, Momar Sakho. Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables. Information and Computation, Elsevier, 2021, ⟨10.1016/j.ic.2021.104776⟩. ⟨hal-03151014⟩

Share

Metrics

Record views

58

Files downloads

110