Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twenty-Second Annual IEEE Symposium on

Logic in Computer Science (LICS 2007)

Paper: Alternation-free modal mu-calculus for data trees (at LICS 2007)

Authors: Marcin Jurdzinski Ranko Lazic

Abstract

An alternation-free modal ì-calculus over data trees is introduced and studied. A data tree is an unranked ordered tree whose every node is labelled by a letter from a finite alphabet and an element ("datum") from an infinite set. For expressing data-sensitive properties, the calculus is equipped with freeze quantification. A freeze quantifier stores in a register the datum labelling the current tree node, which can then be accessed for equality comparisons deeper in the formula. The main results in the paper are that, for the fragment with forward modal operators and one register, satisfiability over finite data trees is decidable but not primitive recursive, and that for the subfragment consisting of safety formulae, satisfiability over countable data trees is decidable but not elementary. The proofs use alternating tree automata which have registers, and establish correspondences with nondeterministic tree automata which have faulty counters. Allowing backward modal operators or two registers causes undecidability. As consequences, decidability is obtained for two data-sensitive fragments of the XPath query language. The paper shows that, for reasoning about data trees, the forward fragment of the calculus with one register is a powerful alternative to a recently proposed first-order logic with two variables.

BibTeX

  @InProceedings{JurdzinskiLazic-Alternationfreemoda,
    author = 	 {Marcin Jurdzinski and Ranko Lazic},
    title = 	 {Alternation-free modal mu-calculus for data trees},
    booktitle =  {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)},
    year =	 {2007},
    month =	 {July}, 
    pages =      {131--140},
    location =   {Wroclaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski