Bojanczyk, Mikolaj - Two-Way Unary Temporal Logic over Trees

lmcs:917 - Logical Methods in Computer Science, August 5, 2009, Volume 5, Issue 3
Two-Way Unary Temporal Logic over Trees

Authors: Bojanczyk, Mikolaj

We consider a temporal logic EF+F^-1 for unranked, unordered finite trees. The logic has two operators: EF\phi, which says "in some proper descendant \phi holds", and F^-1\phi, which says "in some proper ancestor \phi 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.


Source : oai:arXiv.org:0904.4119
DOI : 10.2168/LMCS-5(3:5)2009
Volume: Volume 5, Issue 3
Published on: August 5, 2009
Submitted on: January 8, 2008
Keywords: Computer Science - Logic in Computer Science,F.4.1


Share

Consultation statistics

This page has been seen 56 times.
This article's PDF has been downloaded 18 times.