2026-07-19T14:11:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3243 2024-03-06T10:34:00Z ddc:004 open_access

Trees in Trees: Is the Incomplete Information about a Tree Consistent? Kopczynski, Eryk XML tree automata incomplete tree descriptions Euler cycle 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eryk Kopczynski 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.367 urn:nbn:de:0030-drops-32434 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.367 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode