License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2020.21
URN: urn:nbn:de:0030-drops-116645
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11664/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Khoussainov, Bakhadyr

Automatic Equivalence Structures of Polynomial Growth

pdf-format:
LIPIcs-CSL-2020-21.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs:2020:11664,
  author =	{Moses Ganardi and Bakhadyr Khoussainov},
  title =	{{Automatic Equivalence Structures of Polynomial Growth}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11664},
  URN =		{urn:nbn:de:0030-drops-116645},
  doi =		{10.4230/LIPIcs.CSL.2020.21},
  annote =	{Keywords: automatic structures, polynomial growth, isomorphism problem}
}

Keywords: automatic structures, polynomial growth, isomorphism problem
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI