LIPIcs.CSL.2011.367.pdf
- Filesize: 0.57 MB
- 14 pages
Document
Trees in Trees: Is the Incomplete Information about a Tree Consistent?
Author
-
Part of:
Volume:
Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (CSL 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-08-31
Cite As Get BibTex
Eryk Kopczynski. Trees in Trees: Is the Incomplete Information about a Tree Consistent?. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 367-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.CSL.2011.367
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.
Subject Classification
Keywords
- XML
- tree automata
- incomplete tree descriptions
- Euler cycle
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads