Logic in Computer Science (LICS 2002)

Paper: Tree Extension Algebras: Logics, Automata, and Query Languages (at LICS 2002)

Authors: Michael Benedikt Leonid Libkin

Abstract

We study relations on trees defined by first-order constraints over a vocabulary that includes tree extension inequalities, in addition to unary node tests and domain comparisons. We show that from a formula one can generate a tree automaton that accepts the set of tuples of trees defined by the formula, and conversely that every automaton over tree-tuples is captured by such a formula. We look at the fragment with only extension inequalities and leaf tests, and show that it corresponds to a new class of automata on tree tuples, which is strictly weaker then general tree-tuple automata. We use the automata representations to show separation and expressibility results for formulae in the logic. We then turn to relational calculi over the logic defined here: that is, from constraints we extend to queries that have second-order parameters for a finite set of tree tuples. We give normal forms for queries, and use these to get bounds on the data complexity of query evaluation, showing that while general query evaluation is unbounded within the polynomial hierarchy, generic query evaluation has very low complexity, giving strong bounds on the expressive power of relational calculi with tree extension constraints. We also give normal forms for safe queries in the calculus.

BibTeX

  @InProceedings{BenediktLibkin-TreeExtensionAlgebr,
    author = 	 {Michael Benedikt and Leonid Libkin},
    title = 	 {Tree Extension Algebras: Logics, Automata, and Query
    Languages},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2002},
    year =	 2002,
    editor =	 {Gordon Plotkin},
    month =	 {July}, 
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }