[logic-ml] Talk by Bakh Khoussainov (25 Jan, 11.00-)

[Kazushige TERUI]

みなさま

来週木曜日に京都大学にてBakh Khoussainovさんによる講演があります。
詳細は下記の通りです。よろしければご参加ください。

京都大学数理解析研究所
照井一成

==========
Time:    11:00-12:00, 25 Jan, 2018
Place:    Rm 478, Research Building 2, Main Campus, Kyoto University
    京都大学 本部構内 総合研究2号館 4階478号室
    http://www.kyoto-u.ac.jp/en/access/yoshida/main.html (Building 34)

Speaker: Bakh Khoussainov (University of Auckland)

Title: Finitely presented expansions of semigroups, algebras, and groups.

Abstract:  Finitely presented algebraic systems, such as groups and semigroups,
are of foundational interest in algebra and computation. Finitely
presented algebraic systems necessarily have a computably enumerable (c.e.
for short) word equality problem and these systems are finitely generated.
Call finitely generated algebraic systems with a c.e. word equality problem
computably enumerable. Computably enumerable finitely generated algebraic
systems are not necessarily finitely presented. This paper is concerned with
finding finitely presented expansions of finitely generated c.e. algebraic systems.
The method of expansions of algebraic systems, such as turning groups
into rings or distinguishing elements in the underlying algebraic systems, is an
important method used in algebra, model theory, and in various areas of theoretical
computer science. Bergstra and Tucker proved that all c.e. algebraic
systems with decidable word problem possess finitely presented expansions.
Then they, and, independently, Goncharov asked if every finitely generated
c.e. algebraic system has a finitely presented expansion. We build
examples of finitely generated c.e. semigroups, groups, and algebras that fail to
possess finitely presented expansions, thus answering the question of Bergstra-Tucker
and Goncharov for the classes of semigroups, groups and algebras. We
also construct an example of a residually finite, infinite, and algorithmically
finite group, thus answering the question of Miasnikov and Osin. Our constructions
are based on the interplay between key concepts and known results
from computability theory (such as simple and immune sets) and algebra (such
as residual finiteness and the theorem of Golod-Shafaverevich).
The work is joint with D. Hirschfeldt and A. Miasnikov.


------------------------------------------
Kazushige TERUI
Research Institute for Mathematical Sciences,
Kyoto University.
Kitashirakawa Oiwakecho, Sakyo-ku, Kyoto 606-8502, JAPAN.
Phone: +81-75-753-7235
Fax: +81-75-753-7276
terui at kurims.kyoto-u.ac.jp
http://www.kurims.kyoto-u.ac.jp/~terui/