[logic-ml] Talk by Bakh Khoussainov and Toru Takisaka (1 Dec 11:00-)

[Tetsuya Sato]

京都大学数理解析研究所の佐藤です。

12月1日11:00から、オークランド大学のBakh Khoussainov先生と
京都大学数理解析研究所の滝坂透氏の両名に以下のjoint talkを
していただくことになりましたので、ご連絡いたします。
どうぞお気軽にお越しください。

==========
Time:	11:00-12:00, 1 Dec, 2016
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)
	http://www.kyoto-u.ac.jp/ja/access/campus/map6r_y.htm (34番の建物)

Speakers: Bakh Khoussainov (University of Auckland)
          and Toru Takisaka (RIMS, Kyoto university)

Title:	On large scale geometries of infinite strings

Abstract:
Motivated by notions in geometric group theory, we introduce
the concept of large scale geometry on  infinite strings.

Informally, two infinite strings have the same large scale
geometry if there is a bi-Lipschitz map between both strings
with a finite uniform distortion. We call these maps
quasi-isometric maps.

Introduction of large scale geometries poses several
questions. The first question is related to understanding
the partial order induced by quasi-isometric maps on large
scale geometries of strings. We prove that there is the
greatest large scale geometry and infinitely many minimal
large scale geometries.
The second is related to understanding the quasi-isometric
maps on various classes of strings.
The third question address the issue of building quasi-isometric
maps between computable infinite strings. We show that the
problem is Sigma_3-complete.
The fourth question is about understanding sets of large
scale geometries given some tools (e.g. Buchi automata)
that describe sets of strings. We provide an efficient
algorithm that gives a full description of large scale
geometries of strings accepted by such automata.
Finally, the fifth question asks if it is possible to
associate with every large scale geometry an algebraic
structure that describes the geometry uniquely.
Here we use tools of geometric group theory by invoking
the notion of asymptotic cone.