Alladi Ramakrishnan Hall

Algebraically characterising subclasses of regular languages and functions

Amaldev Manuel

IIT Goa

Languages accepted by finite state automata are precisely those recognised
by finite semigroups. This connection extends to well behaved subclasses of
regular languages and suitably chosen subclasses of finite semigroups. A
pioneering and perfect example is the theorem of Schutzenberger that
equates star-free languages and languages recognised by group-free finite
semigroups. It yields an algorithm to answer the membership problem for
star-free languages: given a regular language is it star-free? This
algebraic method remains our primary tool to answer membership problems to
this day. This approach also works for generalisations of finite words, for
instance for classes of infinite words, classes of functions defined by
automata etc. In this talk I will go through some examples of algebraic
characterizations taken from my past research. We will see the case of
languages defined by first-order logic with the neighbour predicate that
will be characterised using a particular form of two-sided semidirect
product of aperidic commutative involution semigroups and locally trivial
involution semigroups. Going to functions, we will see how to characterise
functions defined by distance automata and (max,+)-automata using
stabilisation monoids. If time permits, we will also see a characterisation
of two-variable first order logic over countable words, a generalisation of
the variety DA often called a diamond of automata theory. Finally I will
conclude with some recent work of deciding closeness of finite state
transducers by solving word equations.