EF+EX forest algebras

DOI10.1007/978-3-319-23021-4_12MaRDI QIDQ2947153zbMATH OpenOpenAlexFDO

Authors A. Krebs, Howard Straubing

Publication date 22 September 2015

Published in Algebraic Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.0809

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Trees (05C05) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Temporal logic (03B44)

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.

Recommendations

• Algebra for Infinite Forests with an Application to the Temporal Logic EF
• Wreath products of forest algebras, with applications to tree logics
• CONCUR 2004 - Concurrency Theory
• Characterizing EF and EX tree logics
• New applications of the wreath product of forest algebras

Cites work

• scientific article; zbMATH DE number 5872386 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• Characterizing EF and EX tree logics
• EF+EX forest algebras
• On the expressive power of temporal logic
• Piecewise testable tree languages
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• Temporal logic and semidirect products: An effective characterization of the until hierarchy
• Wreath products of forest algebras, with applications to tree logics

Cited in

(9)

• Wreath products of forest algebras, with applications to tree logics
• Two-Way Unary Temporal Logic over Trees
• CONCUR 2004 - Concurrency Theory
• EF+EX forest algebras
• scientific article; zbMATH DE number 5872386 (Why is no real title available?)
• New applications of the wreath product of forest algebras
• Characterizing EF and EX tree logics
• Wreath products of distributive forest algebras
• Algebra for Infinite Forests with an Application to the Temporal Logic EF

This page was built for publication: EF+EX forest algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947153)