Automata over Algebraic Structures

ABSTRACT:
In this talk we introduce the concept of finite automata over algebraic structures. We address the classical emptiness problem and its various refinements in our setting. In particular, we prove several decidability and undecidability results. We also explain the way our automata model connects with the existential first order theory of algebraic structures.

BIOGRAPHY:
Bakh Khoussainov is a professor of computer science at the University of Auckland. He is a fellow of The Royal Society of New Zealand for his research contributions in logic and computability. He has been a Humboldt fellow, JSPS fellow, and was awarded New Zealand Mathematical Society research award for research excellence. He is an editor of the Journal for Symbolic Logic. Bakh's current research interests are automatic structures, computable model theory, algorithmically random structures, and effective aspects of differential games.