Speaker:

Yuyang Zhuge, Xiaoyang Gong(University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• May 26, 2023 (Friday)

Venue:

518, Research Building 4

Abstract:

We introduce automatic structures. We provide examples and discuss several research directions. One direction of research is the isomorphism problem. The problem asks to design an algorithm that given two automatic structures decides if they are isomorphic. We explain the state of the art in this direction and provide our contribution. The other direction is concerned with finding exotic automatic presentations of automatic structures. These are examples of automatic structures that defy an intuition. Here provide examples of counter-intuitive automatic structures.
Our focus will be on structures of the type (\omega; S, U), where \omega is the set of natural numbers, S is the successor function on the set \omega of natural numbers, and U is a unary predicate on \omega. These structures are called word structures.