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 <>
Submitted on : Wednesday, February 24, 2021 - 1:16:07 PM
Last modification on : Tuesday, March 30, 2021 - 3:05:42 PM

File

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

Identifiers

  • HAL Id : hal-03151014, version 1

Collections

Citation

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

Share

Metrics

Record views

22

Files downloads

157