2026-07-26T08:00:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24158 2025-11-12T13:33:48Z ddc:004 open_access

Word Structures and Their Automatic Presentations Gong, Xiaoyang Khoussainov, Bakh Zhuge, Yuyang Automatic structures the isomorphism problem decidability undecidability regular relations We study automatic presentations of the structures (ℕ; S), (ℕ; E_S), (ℕ; ≤), and their expansions by a unary predicate U. Here S is the successor function, E_S is the undirected version of S, and ≤ 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 A, decides if A is isomorphic to (ℕ; S). The second asks to design an algorithm that, given two automatic presentations of (ℕ; S, U₁) and (ℕ; S, U₂), where U₁ and U₂ are unary predicates, decides if these structures are isomorphic. The third problem investigates if there is an algorithm that, given two automatic presentations of (ℕ; ≤, U₁) and (ℕ; ≤, U₂), decides whether U₁ ∩ U₂ ≠ ∅. We show that these problems are undecidable. Next, we study intrinsic regularity of the function S in the structure Path_ω = (ℕ; E_S). We build an automatic presentation of Path_ω in which S is not regular. This implies that S is not intrinsically regular in Path_ω. For U ⊆ ℕ, let d_U be the function that computes the distances between the consecutive elements of U. We build automatic presentations of (ℕ; ≤, U) where d_U can realise logarithmic, radical, intermediate, and exponential functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaoyang Gong and Bakh Khoussainov and Yuyang Zhuge 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.51 urn:nbn:de:0030-drops-241581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode