Skip to Main content Skip to Navigation
Conference papers

Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables

Iovka Boneva 1 Joachim Niehren 1 Momar Sakho 1
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We study the complexity of regular matching and inclusion for compressed tree patterns extended by context variables. The addition of context variables to tree patterns permits us to properly capture compressed string patterns but also compressed patterns for unranked trees with tree and hedge variables. Regular inclusion for the latter is relevant to certain query answering on Xml streams with references.
Keywords : trees tree languages and tree automata Complex event processing data streams automata computational complexity patterns queries
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download
https://hal.inria.fr/hal-01811835
Contributor : Inria Links <>
Submitted on : Thursday, June 27, 2019 - 5:50:04 PM
Last modification on : Tuesday, December 3, 2019 - 1:20:56 AM

File

Vignette du document
0-short.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01811835, version 4

Collections

CNRS | CRISTAL | INRIA | UNIV-LILLE | CRISTAL-LINKS

Citation

Iovka Boneva, Joachim Niehren, Momar Sakho. Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables. LATA 2019 - 13th International Conference on Language and Automata Theory and Applications, Mar 2019, Saint Petersburg, Russia. ⟨hal-01811835v4⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

51

Files downloads

300

 

Contact                    Legal Notice                    Personal Data