Paper Info
Title
EF plus EX Forest Algebras
Abstract
We examine languages of unranked forests definable using the temporal operators EF and EX. We characterize the languages definable in this logic, and various fragments thereof, using the syntactic forest algebras introduced by Bojanczyk and Walukiewicz. Our algebraic characterizations yield efficient algorithms for deciding when a given language of forests is definable in this logic. The proofs are based on understanding the wreath product closures of a few small algebras, for which we introduce a general ideal theory for forest algebras. This combines ideas from the work of Bojanczyk and Walukiewicz for the analogous logics on binary trees and from early work of Stiffler on wreath product of finite semigroups.
Year
DOI
Venue
2015
10.1007/978-3-319-23021-4_12
ALGEBRAIC INFORMATICS (CAI 2015)
DocType
Volume
ISSN
Conference
9270
0302-9743
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Andreas Krebs1218.20
Howard Straubing252860.92