Bakhodyr Khoussainov (University of Electronic Science and Technology of China)
Time:
- 15:00-16:00 (Time in Beijing)
- November 22, 2023 (Thursday)
Venue:
Online, Tencent Meeting: 486-877-316
Abstract:
Finitely presented algebraic systems, e.g, groups, are fundamental in algebra and computation, They have computably enumerable word equality problems and are finitely generated (f.g,), We refer to f.g, algebraic systems with computably enumerable word equality problems as computably enumerable. Not all computably enumerable, f.g algebraic systems are finitely presented.
This talk explores the quest for finitely presented expansions
expansion of algebraic systems. such as transforming groups into rings or introducing automorphisms. is an important technique in algebra, model theory, and theoretical computer science. Bergstra and Tucker proved that all computably enumerable algebraic systems with decidable word problems have finitely presented expansions. They, along with Goncharov, independently asked if every f.g, computably enumerable algebraic system has a finitely presented expansion. In this talk. we provide examples of f.g. computably enumerable semigroups, groups, and algebras that lack finitely presented expansions, thus answering the question of Bergstra-Tucker and Goncharov. Additionally, we construct examples of residually finite, infinite, and algorithmically finite group, answering Miasnikov and Osin’s question. These constructions rely on the interplay between key concepts from computability (e.g., simple and immune sets) and algebra (e.g., residual finiteness and the GolodShafaverevich theorem).
This work is joint with A. Miasnikov.
Speaker Bio:
Bakh Khoussainov，教授，新西兰院士，电子科技大学计算机学院全职教授（我国西部地区引进的第一位发达国家的院士），目前担任电子科技大学算法与逻辑团队主任。他长期从事理论计算机科学中计算与逻辑领域的研究工作，2005年被新西兰最顶尖权威的学术组织——新西兰皇家学会评选为新西兰皇家学会院士，被评价为“在逻辑与理论计算机科学领域的领先专家，工作涉及对可计算性和复杂性理论的深入和非常广泛的研究”。2019年获得德国洪堡研究奖，该奖项旨在授予在基础研究、理论创新、学科引领等方面上取得了卓越成就的研究者。同年他还获得伦敦数学学会与新西兰数学学会联合授予的唯一Aitken Lecturer称号，该荣誉称号每两年仅授予一名最具杰出贡献的新西兰数学家（截至目前仅有包括美国工业与应用数学学会会士（SIAM Fellow）Hinke Osinga教授在内的5位研究者获此殊荣）。2017年他因其对于奇偶博弈问题的突出贡献荣获CCF A类会议ACM STOC 2017年最佳论文奖。他还曾获得新西兰数学学会研究奖，此奖项为新西兰数学领域最高奖，每年仅颁发给一名新西兰数学家，该奖项还曾颁发给包括美国数学学会会士G. Martin, R. Downey教授（AMS Fellow）, M. Conder教授（AMS Fellow）等优秀数学家。
