Beauty and Challenges of Combinatorics on Words

Date: 
Tuesday, December 16, 2008 - 9:26am

UCSB COMPUTER SCIENCE DEPARTMENT PRESENTS:
MONDAY, JANUARY 5, 2009
3:30 – 4:30
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: OSCAR IBARRA

SPEAKER: Juhani Karhumaki
Department of Mathematics and Turku Centre for Computer Science
University of Turku, Finland

Title: Beauty and Challenges of Combinatorics on Words

Abstract:

Combinatorics on Words is a relatively new research topic in discrete
mathematics and theoretical computer science. It is very
multidisciplinary having connection to many research areas, such as
algorithmics, codings, crystallography, probability, algebra, DNA
sequences, and of course automata theory. Indeed, many of the
fundamental results of the theory have been discovered by considering
concrete problems of these areas. The basic object in CoW is a sequence
of symbols, either finite or infinite, taken from a finite alphabet.
The questions asked by the theory might be either algorithmic, algebraic
or combinatorial depending on the application. The goal of this talk is
to give a short introduction to the problems of this field and point out
several applications of the theory. Also, a challenging nature of the
topic is emphasized by giving several easily understandable open
problems of CoW. Finally a number of deep achievements of the theory are
mentioned.

Bio:

Juhani Karhumaki is Professor and Head of the Department of Mathematics
at the University of Turku, Finland. He also leads the Fundamentals of
Computing and Discrete Mathematics Centre, which is the largest and most
active research laboratories in the Turku Centre for Computer Science.
His research areas include combinatorics of words, automata theory and
formal languages, decidability and undecidability questions. He is a
member of the Finnish Academy of Sciences and the Academia Europaea. He
is on the Editorial Boards of several journals and has served as program
committee chair of many international conferences.