2026-08-10T20:05:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11664 2024-03-06T10:48:44Z ddc:004 open_access

Automatic Equivalence Structures of Polynomial Growth Ganardi, Moses Khoussainov, Bakhadyr automatic structures polynomial growth isomorphism problem In this paper we study the class EqP of automatic equivalence structures of the form ?=(D, E) where the domain D is a regular language of polynomial growth and E is an equivalence relation on D. Our goal is to investigate the following two foundational problems (in the theory of automatic structures) aimed for the class EqP. The first is to find algebraic characterizations of structures from EqP, and the second is to investigate the isomorphism problem for the class EqP. We provide full solutions to these two problems. First, we produce a characterization of structures from EqP through multivariate polynomials. Second, we present two contrasting results. On the one hand, we prove that the isomorphism problem for structures from the class EqP is undecidable. On the other hand, we prove that the isomorphism problem is decidable for structures from EqP with domains of quadratic growth. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Bakhadyr Khoussainov 2020 Is Part Of LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2020.21 urn:nbn:de:0030-drops-116645 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.21 eng https://creativecommons.org/licenses/by/3.0/legalcode