COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Semigroups with low difficulty word problem

## Semigroups with low difficulty word problemAdd to your list(s) Download to your calendar using vCal - Markus Pfeiffer, St Andrew's
- Friday 26 April 2013, 16:00-17:00
- Room FW26, Computer Laboratory, William Gates Building.
If you have a question about this talk, please contact Jonathan Hayman. The word problem for groups is a well-studied 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 context-free 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:- All Talks (aka the CURE list)
- Computer Laboratory talks
- Computing and Mathematics
- Logic and Semantics Seminar (Computer Laboratory)
- Room FW26, Computer Laboratory, William Gates Building
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
Note that ex-directory lists are not shown. |
## Other listsINTP Forum Open Innovation Cambridge Centre for Climate Change Mitigation Research Seminar Series## Other talksNational crises, viewed in the light of personal crises Climate Change: Protecting Carbon Sinks The homelands of the plague: Soviet disease ecology in Central Asia, 1920s–1950s Multilingual Identities and Heterogeneous Language Ideologies in the New Latino Diaspora Information Theory, Codes, and Compression Recent developments and debates in East Asian monsoon palaeoclimatology |