Loading...
Please wait, while we are loading the content...
Similar Documents
Regular n-ary queries in trees and variable independence
| Content Provider | CiteSeerX |
|---|---|
| Author | Filiot, Emmanuel Tison, Sophie |
| Description | Summary. 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. 1 In: International Conference on Theoretical Computer Science (IFIP TCS), 2008 |
| File Format | |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Free First-order Variable Regular Query Cartesian Product Intermediate Step Dependence Forest Variable Independence Regular N-ary Query Variable Independence Problem Mso Formula |
| Content Type | Text |
| Resource Type | Article |
