Document Open Access Logo

ω-Forest Algebras and Temporal Logics

Authors Achim Blumensath, Jakub Lédl

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.19.pdf
  • Filesize: 0.65 MB
  • 21 pages

Document Identifiers

Author Details

Achim Blumensath
  • Masaryk University, Brno, Czech Republic
Jakub Lédl
  • Masaryk University, Brno, Czech Republic

Funding

  • Blumensath, Achim: Work supported by the Czech Science Foundation, grant No. GA17-01035S.
  • Lédl, Jakub: Work supported by the Czech Science Foundation, grant No. GA17-01035S.

Cite AsGet BibTex

Achim Blumensath and Jakub Lédl. ω-Forest Algebras and Temporal Logics. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.19

Abstract

We use the algebraic framework for languages of infinite trees introduced in [A. Blumensath, 2020] to derive effective characterisations of various temporal logics, in particular the logic EF (a fragment of CTL) and its counting variant cEF.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic
Keywords
  • forest algebras
  • temporal logics
  • bisimulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Blumensath. Branch-Continuous Tree Algebras. unpublished. URL: http://arxiv.org/abs/1807.04568.
  2. A. Blumensath. Recognisability for algebras of infinite trees. Theoretical Computer Science, 412:3463-3486, 2011. Google Scholar
  3. A. Blumensath. An Algebraic Proof of Rabin’s Tree Theorem. Theoretical Computer Science, 478:1-21, 2013. Google Scholar
  4. A. Blumensath. Regular Tree Algebras. Logical Methods in Computer Science, 16:16:1-16:25, 2020. Google Scholar
  5. A. Blumensath. Algebraic Language Theory for Eilenberg–Moore Algebras. Logical Methods in Computer Science, 17:6:1-6:60, 2021. Google Scholar
  6. M. Bojańczyk. Recognisable languages over monads. unpublished note. URL: http://arxiv.org/abs/1502.04898v1.
  7. M. Bojańczyk and T. Idziaszek. Algebra for Infinite Forests with an Application to the Temporal Logic EF. In Proc. 20th International Conference on Concurrency Theory, CONCUR, LNCS 5710, pages 131-145, 2009. Google Scholar
  8. M. Bojańczyk, T. Idziaszek, and M. Skrzypczak. Regular languages of thin trees. In Proc. 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, pages 562-573, 2013. Google Scholar
  9. M. Bojańczyk and B. Klin. A non-regular language of infinite trees that is recognizable by a finite algebra. Logical Methods in Computer Science, 15, 2019. Google Scholar
  10. M. Bojańczyk and I. Walukiewicz. Forest Algebras. In J. Flum, E. Grädel, and T. Wilke, editors, Logic and Automata: History and Perspectives, pages 107-132. Amsterdam University Press, 2007. Google Scholar
  11. T. Colcombet and A. Jaquard. A Complexity Approach to Tree Algebras: the Bounded Case. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 127:1-127:13, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact