Tuesday, June 11, 2019 2:30 pm
-
2:30 pm
EDT (GMT -04:00)
Sylvie Davis, Department of Pure Mathematics, University of Waterloo
"Monoids, Computation, and the State Complexity of Regular Languages"
The
state
complexity
of
regular
languages
is
an
active
area
of
research
in
theoretical
computer
science.
A
regular
language
is
a
set
of
words
such
that
a
computer
program
with
finite
memory
can
determine
whether
or
not
a
word
belongs
to
the
language.
Such
programs
are
said
to
"recognize"
the
language.
The
state
complexity
of
a
regular
language
is
a
measure
of
the
amount
of
memory
required
to
recognize
the
language,
with
respect
to
a
specific
state-based
model
of
computation
called
a
deterministic
finite
automaton.
We
will
explore
the
relationship
between
finite-memory
computation
and
abstract
algebra,
and
show
how
reinterpreting
deterministic
finite
automata
as
monoid
actions
allows
us
to
attack
problems
in
state
complexity.
MC
5479