Provided by:
RWTH Aachen University
Topic:
Data Management
Format:
PDF
In this paper, the authors consider the possibility problem of determining if a document is a possible world of a probabilistic document, in the setting of probabilistic XML (eXtensible Markup Language). This basic question is a special case of query answering or tree automata evaluation, but it has specific practical uses, such as checking whether a user provided probabilistic document outcome is possible or sufficiently likely. In this paper, they study the complexity of the possibility problem for probabilistic XML models of varying expressiveness.
