# IEEE Symposium on Logic in Computer Science

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

# Logic in Computer Science (LICS 2007)

## 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}
}