Document Open Access Logo

Automatic Equivalence Structures of Polynomial Growth

Authors Moses Ganardi, Bakhadyr Khoussainov

PDF
Thumbnail PDF

File

LIPIcs.CSL.2020.21.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Moses Ganardi
  • University of Siegen, Siegen, Germany
Bakhadyr Khoussainov
  • University of Auckland, Auckland, New Zealand

Funding

  • Ganardi, Moses: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 731143.

Cite AsGet BibTex

Moses Ganardi and Bakhadyr Khoussainov. Automatic Equivalence Structures of Polynomial Growth. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CSL.2020.21

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • automatic structures
  • polynomial growth
  • isomorphism problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Vince Bárány. Automatic presentations of infinite structures. PhD thesis, RWTH Aachen University, Germany, 2007. URL: http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/2019/.
  2. Achim Blumensath. Automatic Structures. Master’s thesis, RWTH Aachen University, 1999. Google Scholar
  3. Achim Blumensath and Erich Grädel. Finite Presentations of Infinite Structures: Automata and Interpretations. Theory Comput. Syst., 37(6):641-674, 2004. URL: https://doi.org/10.1007/s00224-004-1133-y.
  4. Jiamou Liu Dietrich Kuske and Markus Lohrey. The isomorphism problem on classes of automatic structures with transitive relations. Trans. Amer. Math. Soc., 365:5103-5151, 2013. Google Scholar
  5. Ginsburg, Seymour and Spanier, Edwin. Semigroups, Presburger formulas, and languages. Pacific journal of Mathematics, 16(2):285-296, 1966. Google Scholar
  6. Ryuichi Ito. Every Semilinear Set is a Finite Union of Disjoint Linear Sets. J. Comput. Syst. Sci., 3(2):221-231, 1969. URL: https://doi.org/10.1016/S0022-0000(69)80014-0.
  7. Lukasz Kaiser, Sasha Rubin, and Vince Bárány. Cardinality and counting quantifiers on omega-automatic structures. In STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings, pages 385-396, 2008. URL: https://doi.org/10.4230/LIPIcs.STACS.2008.1360.
  8. Bakhadyr Khoussainov and Anil Nerode. Automatic Presentations of Structures. In Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, International Workshop LCC '94, Indianapolis, Indiana, USA, 13-16 October 1994, pages 367-392, 1994. URL: https://doi.org/10.1007/3-540-60178-3_93.
  9. Bakhadyr Khoussainov, André Nies, Sasha Rubin, and Frank Stephan. Automatic Structures: Richness and Limitations. Logical Methods in Computer Science, 3(2), 2007. URL: https://doi.org/10.2168/LMCS-3(2:2)2007.
  10. Bakhadyr Khoussainov, Sasha Rubin, and Frank Stephan. Automatic linear orders and trees. ACM Trans. Comput. Log., 6(4):675-700, 2005. URL: https://doi.org/10.1145/1094622.1094625.
  11. Dietrich Kuske and Markus Lohrey. First-order and counting theories of omega-automatic structures. J. Symb. Log., 73(1):129-150, 2008. URL: https://doi.org/10.2178/jsl/1208358745.
  12. W.J. LeVeque. Topics in Number Theory. Number Bd. 1 in Dover Books on Mathematics. Dover Publications, 2002. URL: https://books.google.de/books?id=ocAySqjVLeEC.
  13. Jiamou Liu and Mia Minnes. Deciding the isomorphism problem in classes of unary automatic structures. Theor. Comput. Sci., 412(18):1705-1717, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.045.
  14. Yuri V Matiyasevich. Hilbert’s tenth problem, volume 105. MIT press Cambridge, 1993. Google Scholar
  15. André Nies. Describing Groups. Bulletin of Symbolic Logic, 13(3):305-339, 2007. URL: http://www.math.ucla.edu/%7Easl/bsl/1303/1303-001.ps, URL: https://doi.org/10.2178/bsl/1186666149.
  16. G. Oliver and R. Thomas. Automatic presentations of finitely generated groups. In STACS '05: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science. Springer-Verlag, 2005. Google Scholar
  17. Rohit Parikh. On Context-Free Languages. Journal of the ACM, 13(4):570-581, 1966. Google Scholar
  18. Sasha Rubin. Automatic Structures. PhD thesis, University of Auckland, 2004. Google Scholar
  19. Reginald E. Sawilla, Alan K. Silvester, and Hugh C. Williams. A New Look at an Old Equation. In Alfred J. van der Poorten and Andreas Stein, editors, Algorithmic Number Theory, 8th International Symposium, ANTS-VIII, Banff, Canada, May 17-22, 2008, Proceedings, volume 5011 of Lecture Notes in Computer Science, pages 37-59. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-79456-1_2.
  20. Nicole Schweikardt. Arithmetic, first-order logic, and counting quantifiers. ACM Trans. Comput. Log., 6(3):634-671, 2005. URL: https://doi.org/10.1145/1071596.1071602.
  21. Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeffrey Shallit. Characterizing Regular Languages with Polynomial Densities. In Ivan M. Havel and Václav Koubek, editors, Mathematical Foundations of Computer Science 1992, 17th International Symposium, MFCS'92, Prague, Czechoslovakia, August 24-28, 1992, Proceedings, volume 629 of Lecture Notes in Computer Science, pages 494-503. Springer, 1992. URL: https://doi.org/10.1007/3-540-55808-X_48.
  22. Kevin Woods. Presburger Arithmetic, Rational Generating Functions, and quasi-polynomials. J. Symb. Log., 80(2):433-449, 2015. URL: https://doi.org/10.1017/jsl.2015.4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact