Paper: Two-way unary temporal logic over trees (at LICS 2007)

Authors: Mikołaj Bojańczyk

Abstract

We consider a temporal logic EF + F^-1 for unranked, unordered finite trees. The logic has two operators: EF_\varphi , which says "in some proper descendant \varphi holds", and F^-1 \varphi , which says "in some proper ancestor \varphi holds". We present an algorithm for deciding if a regular language of unranked finite trees can be expressed in EF + F^-1. The algorithm uses a characterization expressed in terms of forest algebras.

BibTeX

  @InProceedings{Bojaczyk-Twowayunarytemporal,
    author = 	 {Mikołaj Bojańczyk},
    title = 	 {Two-way unary temporal logic over trees},
    booktitle =  {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)},
    year =	 {2007},
    month =	 {July}, 
    pages =      {121--130},
    location =   {Wroclaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }