Regular Matching and Inclusion on Compressed ...
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables
Author(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]
Journal title :
Information and Computation
Publisher :
Elsevier
Publication date :
2022
ISSN :
0890-5401
English keyword(s) :
tree patterns
tree automata
computational complexity
streams
Xml
grammar compression
tree automata
computational complexity
streams
Xml
grammar compression
HAL domain(s) :
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]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-03151014/document
- Open access
- Access the document
- https://hal.inria.fr/hal-03151014/document
- Open access
- Access the document
- https://hal.inria.fr/hal-03151014/document
- Open access
- Access the document
- document
- Open access
- Access the document
- 0-long.pdf
- Open access
- Access the document