16 citations · 39 across the 13 of their papers we have counts for
15 papers
Simple Classes of Automatic Structures
Achim Blumensath
We study two subclasses of the class of automatic structures: automatic structures of polynomial growth and Presburger structures. We present algebraic characterisations of the gro…
Automata for Enriched Trees and Applications
Achim Blumensath
We study trees where each successor set is equipped with some additional structure. We introduce a family of automaton models for such trees and prove their equivalence to certain…
Some Remarks on First-Order Definable Tree Languages
Achim Blumensath
We study the question of whether a given regular language of finite trees can be defined in first-order logic. We develop an algebraic approach to address this question and we use…
The Expansion Problem for Infinite Trees
Achim Blumensath
We study Ramsey like theorems for infinite trees and similar combinatorial tools. As an application we consider the expansion problem for tree algebras.
The Power-Set Construction for Tree Algebras
Achim Blumensath
We study power-set operations on classes of trees and tree algebras. Our main result consists of a distributive law between the tree monad and the upwards-closed power-set monad, i…
-Forest Algebras and Temporal Logics
Achim Blumensath, Jakub Lédl
We use the algebraic framework for languages of infinite trees introduced in [4] to derive effective characterisations of various temporal logics, in particular the logic EF (a fra…
Algebraic Language Theory for Eilenberg--Moore Algebras
Achim Blumensath
We develop an algebraic language theory based on the notion of an Eilenberg--Moore algebra. In comparison to previous such frameworks the main contribution is the support for algeb…
Bisimulation Invariant Monadic-Second Order Logic in the Finite
Achim Blumensath, Felix Wolf
We consider bisimulation-invariant monadic second-order logic over various classes of finite transition systems. We present several combinatorial characterisations of when the expr…
Regular Tree Algebras
Achim Blumensath
We introduce a class of algebras that can be used as recognisers for regular tree languages. We show that it is the only such class that forms a pseudo-variety and we prove the exi…
Branch-Continuous Tree Algebras
Achim Blumensath
We study a class of algebras that can be used as recognisers for regular languages of infinite trees.
A Compositional Coalgebraic Semantics of Strategic Games
Achim Blumensath, Viktor Winschel
We provide a compositional coalgebraic semantics for strategic games. In our framework, like in the semantics of functional programming languages, coalgebras represent the observab…
Decidability Results for the Boundedness Problem
Achim Blumensath, Martin Otto, Mark Weyer
We prove decidability of the boundedness problem for monadic least fixed-point recursion based on positive monadic second-order (MSO) formulae over trees. Given an MSO-formula phi(…
Monadic second-order definable graph orderings
Achim Blumensath, Bruno Courcelle
We study the question of whether, for a given class of finite graphs, one can define, for each graph of the class, a linear ordering in monadic second-order logic, possibly with th…
On the Monadic Second-Order Transduction Hierarchy
Achim Blumensath, Bruno Courcelle
We compare classes of finite relational structures via monadic second-order transductions. More precisely, we study the preorder where we set C \subseteq K if, and only if, there e…
Guarded Second-Order Logic, Spanning Trees, and Network Flows
Achim Blumensath
According to a theorem of Courcelle monadic second-order logic and guarded second-order logic (where one can also quantify over sets of edges) have the same expressive power over t…