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

lmcs:1215 - Logical Methods in Computer Science, September 19, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:19)2012
Wreath Products of Forest Algebras, with Applications to Tree LogicsArticle

Authors: Mikolaj Bojanczyk ; Igor Walukiewicz ; Howard Straubing

    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.


    Volume: Volume 8, Issue 3
    Published on: September 19, 2012
    Imported on: October 2, 2010
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,F.4.3
    Funding:
      Source : OpenAIRE Graph
    • SHF: AF: Small: Algebraic Methods for the Study of Logics on Trees; Funder: National Science Foundation; Code: 0915065

    8 Documents citing this article

    Consultation statistics

    This page has been seen 1005 times.
    This article's PDF has been downloaded 259 times.