| | |
| | |
Stat |
Members: 3643 Articles: 2'479'597 Articles rated: 2609
19 March 2024 |
|
| | | |
|
Article overview
| |
|
On Injective Embeddings of Tree Patterns | Jakub Michaliszyn
; Anca Muscholl
; Sławek Staworko
; Piotr Wieczorek
; Zhilin Wu
; | Date: |
23 Apr 2012 | Abstract: | We study three different kinds of embeddings of tree patterns:
weakly-injective, ancestor-preserving, and lca-preserving. While each of them
is often referred to as injective embedding, they form a proper hierarchy and
their computational properties vary (from P to NP-complete). We present a
thorough study of the complexity of the model checking problem i.e., is there
an embedding of a given tree pattern in a given tree, and we investigate the
impact of various restrictions imposed on the tree pattern: bound on the degree
of a node, bound on the height, and type of allowed labels and edges. | Source: | arXiv, 1204.4948 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |