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

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