Centre for Interdisciplinary Research in Computational Algebra (CIRCA) lunchtime seminar

There will be a CIRCA lunchtime seminar on Thursday 10th April at 1pm in Maths Lecture Theatre B.

Duncan Adamson and Callum Barber will speak.

Duncan's Title: Subsequence Universality in Languages

Duncan's Abstract: Subsequences are a fundamental object in combinatorics on words. Informally, a subsequence of a word $w$ is a word $u$ which can be formed by deleting some of the symbols from $w$. A word $w$ is $k$-universal, for a given alphabet $Sigma$, every word of length $k$ over the alphabet $Sigma$ (i.e. the set $Sigma^k$) appears as a subsequence of $w$. In this talk, we will look at the problem of deciding if a regular-language contains any $k$-universal word. We show that this problem is NP-hard even for $1$-universal words in general, while decidable in polynomial time for constant sized alphabets.

Callum's Title: Congruences and Diagonal Subsemigroups

Callum's Abstract: For a group G it is easy to show that every subgroup of GxG that contains the diagonal is also a congruence on G. However the same result does not hold for semigroups. We will call a semigroup for which it does hold DSC. It is easy to see that any finite group must be DSC, and that any DSC semigroup must be simple. Building on this, we will show that for several broad classes of semigroups that the only DSC members are groups. However it turns out that there does exist non-group DSC semigroups, which we obtain by utilising a construction introduced by Byleen for the purpose of constructing interesting congruence-free semigroups.

Details about this event can be found at https://circa.st-andrews.ac.uk/2025/04/08/circa-seminar-10th-april/

For more information about CIRCA and its activities, visit https://circa.st-andrews.ac.uk/