Semigroups with low difficulty word problem
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Jonathan Hayman.
The word problem for groups is a wellstudied notion in
computational group theory. Results of Anisimov, Muller and Schupp, Lehnert
and Schweitzer, Holt, Roever, Thomas and many more relate the word problem and
the coword problem of (classes of) groups to (classes of) formal languages,
for example regular languages and contextfree languages.
In my research I considered a natural definition of the word problem and the
coword problem of semigroups.
Using the notions of recognisable, rational, and extended rational subsets of
monoids, I extended some of the results about groups to semigroups.
I then defined a hierarchy of semigroups by difficulty of their word
problem.
In my talk I will give an accessible overview of the results, and I will show
how my results can be seen in the context of logic and complexity theory.
I will also give a few open questions which I hope to answer in the near
future.
This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
