License
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://drops.dagstuhl.de/opus/volltexte/2011/3243/
Go to the corresponding Portal


Kopczynski, Eryk

Trees in Trees: Is the Incomplete Information about a Tree Consistent?

pdf-format:
Document 1.pdf (593 KB)


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 =		{http://dx.doi.org/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
Seminar: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011


DROPS-Home | Fulltext Search | Imprint Published by LZI