### Profinite Methods in Automata Theory

Jean-Eric Pin
This survey paper presents the success story of the topological approach to automata theory. It is based on profinite topologies, which are built from finite topogical spaces. The survey includes several concrete applications to automata theory.

### Strong Completeness of Coalgebraic Modal Logics

Lutz Schröder & Dirk Pattinson
Canonical models are of central importance in modal logic, in particular as they witness strong completeness and hence compactness. While the canonical model construction is well understood for Kripke semantics, non-normal modal logics often present subtle difficulties - up to the point that canonical models may fail to exist, as is the case e.g. in most probabilistic logics. Here, we present a generic canonical model construction in the semantic framework of coalgebraic modal logic, which...

### Mediating for Reduction (on Minimizing Alternating Büchi Automata)

Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik & Tomas Vojnar
We propose a new approach for minimizing alternating B\"uchi automata (ABA). The approach is based on the so called \emph{mediated equivalence} on states of ABA, which is the maximal equivalence contained in the so called \emph{mediated preorder}. Two states $p$ and $q$ can be related by the mediated preorder if there is a~\emph{mediator} (mediating state) which forward simulates $p$ and backward simulates $q$. Under some further conditions, letting a computation on some word jump from...

### Preface -- 26th International Symposium on Theoretical Aspects of Computer Science

Susanne Albers & Jean-Yves Marion
The interest in STACS has remained at a high level over the past years. The STACS 2009 call for papers led to over 280 submissions from 41 countries. Each paper was assigned to three program committee members. The program committee held a two-week electronic meeting at the beginning of November and selected 54 papers. As co-chairs of the program committee, we would like to sincerely thank its members and the many external referees for their...

### Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

Daniel Kirsten & Sylvain Lombardy
This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.

Bodo Manthey

• 2009
134

• Text
134

• Dagstuhl
134