Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2022

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

Iovka Boneva
Joachim Niehren
Momar Sakho
  • Fonction : Auteur correspondant
  • PersonId : 1019942

Connectez-vous pour contacter l'auteur

Résumé

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.
Fichier principal
Vignette du fichier
0-long.pdf (543.66 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03151014 , version 1 (24-02-2021)

Identifiants

Citer

Iovka Boneva, Joachim Niehren, Momar Sakho. Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables. Information and Computation, 2022, 286, ⟨10.1016/j.ic.2021.104776⟩. ⟨hal-03151014⟩
81 Consultations
163 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More