License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.367
URN: urn:nbn:de:0030-drops-32434
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3243/
Kopczynski, Eryk
Trees in Trees: Is the Incomplete Information about a Tree Consistent?
Abstract
We are interested in the following problem: given a tree automaton Aut and an incomplete tree description P, does a tree T exist such that T is accepted by Aut and consistent with P? A tree description is a tree-like structure which provides incomplete information about the shape of T. We show that this problem can be solved in polynomial time as long as Aut and the set of possible arrangements that can be forced by P are fixed. We show how our result is related to an open problem in the theory of incomplete XML information.
BibTeX - Entry
@InProceedings{kopczynski:LIPIcs:2011:3243,
author = {Eryk Kopczynski},
title = {{Trees in Trees: Is the Incomplete Information about a Tree Consistentl}},
booktitle = {Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
pages = {367--380},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-32-3},
ISSN = {1868-8969},
year = {2011},
volume = {12},
editor = {Marc Bezem},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3243},
URN = {urn:nbn:de:0030-drops-32434},
doi = {10.4230/LIPIcs.CSL.2011.367},
annote = {Keywords: XML, tree automata, incomplete tree descriptions, Euler cycle}
}
|
Keywords: |
|
XML, tree automata, incomplete tree descriptions, Euler cycle |
|
Collection: |
|
Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
31.08.2011 |
