Consistency of injective tree patterns

Claire David, Nadime Francis, Filip Murlak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Testing if an incomplete description of an XML document is consistent, that is, if it describes a real document conforming to the imposed schema, amounts to deciding if a given tree pattern can be matched injectively into a tree accepted by a fixed automaton. This problem can be solved in polynomial time for patterns that use the child relation and the sibling order, but do not use the descendant relation. For general patterns the problem is in NP, but no lower bound has been known so far. We show that the problem is NP-complete already for patterns using only child and descendant relations. The source of hardness turns out to be the interplay between these relations: for patterns using only descendant we give a polynomial algorithm. We also show that the algorithm can be adapted to patterns using descendant and following-sibling, but combining descendant and next-sibling leads to intractability.
Original languageEnglish
Title of host publicationProceedings of the 34th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14)
EditorsVenkatesh Raman, S.~P. Suresh
Place of PublicationNew~Dehli, India
PublisherLeibniz-Zentrum für Informatik
Number of pages12
Publication statusPublished - 1 Dec 2014


Dive into the research topics of 'Consistency of injective tree patterns'. Together they form a unique fingerprint.

Cite this