Search Results

Documents authored by Blumensath, Achim

Document
DOI: 10.4230/DagRep.15.3.177
Categories for Automata and Language Theory (Dagstuhl Seminar 25141)

Authors: Achim Blumensath, Mikołaj Bojańczyk, Bartek Klin, and Daniela Petrişan

Published in: Dagstuhl Reports, Volume 15, Issue 3 (2025)

Abstract
Categorical methods have a long history in automata and language theory, but a coherent theory has started to emerge only in recent years. The abstract viewpoint of category theory can provide a unifying perspective on various forms of automata; it can make it easier to bootstrap a theory in a new setting; and it provides conceptual clarity regarding which aspects and properties are fundamental and which are only coincidental. Due to being in its early stages, the field is currently still divided into several different communities with little connections between them. One of the central aims of the Dagstuhl Seminar "Categories for Automata and Language Theory" (25141) was to enhance communication between automata theory and category theory communities. To this end, the seminar brought together researchers from both areas and included introductory tutorials designed to provide common ground and help participants better understand each other’s approach and terminology. The following key topics were explored during the seminar: - Categorical unification of language theory, either via the theory of monads, or via the category of MSO-transductions and their composition; - Coalgebraic methods and their applications to automata theory, to infinite trace semantics and connection to bisimulation-invariant fragments of logics; - Functorial automata and generic algorithms therein; - Fibrational and monoidal perspectives on language theory; - Higher-order automata and profinite lambda-calculus.
Cite as

Achim Blumensath, Mikołaj Bojańczyk, Bartek Klin, and Daniela Petrişan. Categories for Automata and Language Theory (Dagstuhl Seminar 25141). In Dagstuhl Reports, Volume 15, Issue 3, pp. 177-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{blumensath_et_al:DagRep.15.3.177,
  author =	{Blumensath, Achim and Boja\'{n}czyk, Miko{\l}aj and Klin, Bartek and Petri\c{s}an, Daniela},
  title =	{{Categories for Automata and Language Theory (Dagstuhl Seminar 25141)}},
  pages =	{177--200},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{3},
  editor =	{Blumensath, Achim and Boja\'{n}czyk, Miko{\l}aj and Klin, Bartek and Petri\c{s}an, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.3.177},
  URN =		{urn:nbn:de:0030-drops-248949},
  doi =		{10.4230/DagRep.15.3.177},
  annote =	{Keywords: categorical automata theory, automata theory, category theory, monads}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.19
ω-Forest Algebras and Temporal Logics

Authors: Achim Blumensath and Jakub Lédl

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{blumensath_et_al:LIPIcs.MFCS.2021.19,
  author =	{Blumensath, Achim and L\'{e}dl, Jakub},
  title =	{{\omega-Forest Algebras and Temporal Logics}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.19},
  URN =		{urn:nbn:de:0030-drops-144594},
  doi =		{10.4230/LIPIcs.MFCS.2021.19},
  annote =	{Keywords: forest algebras, temporal logics, bisimulation}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.117
Bisimulation Invariant Monadic-Second Order Logic in the Finite

Authors: Achim Blumensath and Felix Wolf

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider bisimulation-invariant monadic second-order logic over various classes of finite transition systems. We present several combinatorial characterisations of when the expressive power of this fragment coincides with that of the modal mu-calculus. Using these characterisations we prove for some simple classes of transition systems that this is indeed the case. In particular, we show that, over the class of all finite transition systems with Cantor-Bendixson rank at most k, bisimulation-invariant MSO coincides with L_mu.
Cite as

Achim Blumensath and Felix Wolf. Bisimulation Invariant Monadic-Second Order Logic in the Finite. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 117:1-117:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blumensath_et_al:LIPIcs.ICALP.2018.117,
  author =	{Blumensath, Achim and Wolf, Felix},
  title =	{{Bisimulation Invariant Monadic-Second Order Logic in the Finite}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{117:1--117:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.117},
  URN =		{urn:nbn:de:0030-drops-91215},
  doi =		{10.4230/LIPIcs.ICALP.2018.117},
  annote =	{Keywords: bisimulation, monadic second-order logic, composition method}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.19
On a Fragment of AMSO and Tiling Systems

Authors: Achim Blumensath, Thomas Colcombet, and Pawel Parys

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We prove that satisfiability over infinite words is decidable for a fragment of asymptotic monadic second-order logic. In this fragment we only allow formulae of the form "exists t forall s exists r: phi(r,s,t)", where phi does not use quantifiers over number variables, and variables r and s can be only used simultaneously, in subformulae of the form s < f(x) <= r.
Cite as

Achim Blumensath, Thomas Colcombet, and Pawel Parys. On a Fragment of AMSO and Tiling Systems. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blumensath_et_al:LIPIcs.STACS.2016.19,
  author =	{Blumensath, Achim and Colcombet, Thomas and Parys, Pawel},
  title =	{{On a Fragment of AMSO and Tiling Systems}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.19},
  URN =		{urn:nbn:de:0030-drops-57202},
  doi =		{10.4230/LIPIcs.STACS.2016.19},
  annote =	{Keywords: monadic second-order logic, boundedness, tiling problems}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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