Speaker:

Xiaoyang Gong (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• September 12, 2025 (Friday)

Venue:

518, Research Building 4

Abstract:

We study automatic presentations of the structures $(\mathbb{N}; S)$, $(\mathbb{N}; E_S)$, $(\mathbb{N}; \leq)$, and their expansions by a unary predicate $U$. Here $S$ is the successor function, $E_S$ is the undirected version of $S$, and $\leq$ is the natural order. We call these structures word structures. Our goal is three-fold. First, we study the isomorphism problem for automatic word structures by focusing on the following three problems. The first problem asks to design an algorithm that, given an automatic structure $\mathcal A$, decides if $\mathcal A$ is isomorphic to $(\mathbb{N}; S)$. The second asks to design an algorithm that, given two automatic presentations of $(\mathbb{N}; S, U_1)$ and $(\mathbb{N}; S, U_2)$, where $U_1$ and $U_2$ are unary predicates, decides if these structures are isomorphic. The third problem investigates if there is an algorithm that, given two automatic presentations of $(\mathbb{N}; \leq, U_1)$ and $(\mathbb{N}; \leq, U_2)$, decides whether $U_1\cap U_2\neq \emptyset$. We show that these problems are undecidable.