António Malheiro
DM & CMA/FCT/UNL

On the decidability of conjugacy for homogeneous monoids

Abstract:The well known notion of conjugacy for groups can be generalized in several different ways to semigroups. In this talk we would like to present some of the known generalizations, and how they interact in the case of monoids defined by homogeneous presentations. We give a combinatorial description of conjugacy in the sylvester monoid, showing that is decidable for this monoid. We then prove that conjugacy is undecidable in general for homogeneous monoids and even for multihomogeneous monoids. The results were obtained in collaboration with João Araújo, Alan Cain, Michael Kinyon, and Janusz Konieczny.

Jorge Orestes Cerdeira
DM & CMA/FCT/UNL

On Cerný’s conjecture for synchronizing automata

Abstract: A deterministic finite automaton with n states is called synchronizing if there is a sequence of letters which maps the n states onto a single one. In this talk I will give a proof that searching for a synchronizing word of minimum length is NP-hard, and derive a network flow version of Cerný’s conjecture which states that for every synchronizing automata there is a synchronizing word of length at most (n-1)2.