#### 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.

Done