Video library: B. Khoussainov, Large scale geometries of infinite strings

VIDEO LIBRARY


Adian 90: Conference on Mathematical Logic, Algebra, and Computation July 8, 2021 11:30, Moscow, Steklov Mathematical Institute of RAS (Moscow) and online in Zoom

Large scale geometries of infinite strings B. Khoussainov^ab ^a The UESTC, Chengdu, China ^b The University of Auckland, New Zealand
Abstract: We aim to shed light on our understanding of large-scale properties of infinite strings. Say that an infinite string X has weaker large-scale geometry than that of Y if there is color preserving bi-Lipschitz map from X to Y with small distortion. This defines a partially ordered set of large-scale geometries on infinite strings. This partial order presents an algebraic tool for classification of global patterns. We prove that this partial order has a greatest element and has infinite chains and anti-chains. We study the sets of large-scale geometries of strings accepted by finite state machines. We provide an algorithm that describes large scale geometries of strings accepted by $\omega$- automata. This connects the work with the complexity theory. We prove that the quasi-isometry problem is $\Sigma_2^0$-complete, thus providing a bridge with computability theory. We build algebraic structures that are invariants of large-scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. We study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness. Language: English