Regular Matching and Inclusion on Compressed ...
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables
Auteur(s) :
Boneva, Iovka [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Sakho, Momar [Auteur correspondant]
Linking Dynamic Data [LINKS]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Sakho, Momar [Auteur correspondant]
Linking Dynamic Data [LINKS]
Titre de la revue :
Information and Computation
Éditeur :
Elsevier
Date de publication :
2022
ISSN :
0890-5401
Mot(s)-clé(s) en anglais :
tree patterns
tree automata
computational complexity
streams
Xml
grammar compression
tree automata
computational complexity
streams
Xml
grammar compression
Discipline(s) HAL :
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Informatique et langage [cs.CL]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Informatique et langage [cs.CL]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-03151014/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03151014/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03151014/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 0-long.pdf
- Accès libre
- Accéder au document