Skip to Main content Skip to Navigation
Conference papers

Regular n-ary Queries in Trees and Variable Independence

Emmanuel Filiot 1, 2, * Sophie Tison 1, 2, *
* Corresponding author
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Regular n-ary queries in trees are queries which are definable by an MSO formula with n free first-order variables. We investigate the variable independence problem -- originally introduced for databases -- in the context of trees. In particular, we show how to decide whether a regular query is equivalent to a union of cartesian products, independently of the input tree. As an intermediate step, we reduce this problem to the problem of deciding whether the number of answers to a regular query is bounded by some constant, independently of the input tree. As a (non-trivial) generalization, we introduce variable independence w.r.t. a dependence forest between blocks of variables, which we prove to be decidable.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Emmanuel Filiot <>
Submitted on : Monday, April 21, 2008 - 10:13:58 AM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 4:46:52 PM


Files produced by the author(s)


  • HAL Id : inria-00274648, version 2



Emmanuel Filiot, Sophie Tison. Regular n-ary Queries in Trees and Variable Independence. 5th IFIP International Conference on Theoretical Computer Science, Sep 2008, Milano, Italy. pp.429-443. ⟨inria-00274648v2⟩



Record views


Files downloads