Bojanczyk, Mikolaj and Walukiewicz, Igor and Straubing, Howard - Wreath Products of Forest Algebras, with Applications to Tree Logics

lmcs:1215 - Logical Methods in Computer Science, September 19, 2012, Volume 8, Issue 3
Wreath Products of Forest Algebras, with Applications to Tree Logics

Authors: Bojanczyk, Mikolaj and Walukiewicz, Igor and Straubing, Howard

We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These include the temporal logics CTL and EF, and first-order logic over the ancestor relation. While the characterizations are in general non-effective, we are able to use them to formulate necessary conditions for definability and provide new proofs that a number of languages are not definable in these logics.


Source : oai:arXiv.org:1208.6172
DOI : 10.2168/LMCS-8(3:19)2012
Volume: Volume 8, Issue 3
Published on: September 19, 2012
Submitted on: October 2, 2010
Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,F.4.3


Share

Consultation statistics

This page has been seen 49 times.
This article's PDF has been downloaded 12 times.