Document Open Access Logo

Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic

Authors Mathieu Sablik, Michael Schraudner

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.110.pdf
  • Filesize: 0.73 MB
  • 14 pages

Document Identifiers

Author Details

Mathieu Sablik
Michael Schraudner

Cite As Get BibTex

Mathieu Sablik and Michael Schraudner. Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 110:1-110:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.110

Abstract

Realization of d-dimensional effective subshifts as projective sub-actions of d + d'-dimensional sofic subshifts for d' >= 1 is now well known [Hochman, 2009; Durand/Romashchenko/Shen, 2012; Aubrun/Sablik, 2013]. In this paper we are interested in qualitative aspects of this realization. We introduce a new topological conjugacy invariant for effective subshifts, the speed of convergence, in view to exhibit algorithmic properties of these subshifts in contrast to the usual framework that focuses on undecidable properties.

Subject Classification

Keywords
  • Subshift
  • computability
  • time complexity
  • space complexity
  • tilings

Metrics

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

References

  1. Nathalie Aubrun and Mathieu Sablik. An order on sets of tilings corresponding to an order on languages. In Susanne Albers, Susanne Albers, Susanne Albers, Susanne Albers, and Jean-Yves Marion, editors, 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings, volume 3 of LIPIcs, pages 99-110. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1833.
  2. Nathalie Aubrun and Mathieu Sablik. Simulation of Effective Subshifts by Two-dimensional Subshifts of Finite Type. Acta Appl. Math., 126:35-63, 2013. URL: http://dx.doi.org/10.1007/s10440-013-9808-5.
  3. Nathalie Aubrun and Mathieu Sablik. Multidimensional effective s-adic systems are sofic. Uniform Distribution Theory, 9(2), 2014. Google Scholar
  4. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications. J. Comput. System Sci., 78(3):731-764, 2012. URL: http://dx.doi.org/10.1016/j.jcss.2011.11.001.
  5. Thomas Fernique and Mathieu Sablik. Local rules for computable planar tilings. In Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, pages 133-141, 2012. URL: http://dx.doi.org/10.4204/EPTCS.90.11.
  6. Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math., 176(1):131-167, 2009. URL: http://dx.doi.org/10.1007/s00222-008-0161-7.
  7. Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics, 171(3):2011-2038, 2010. URL: http://dx.doi.org/10.4007/annals.2010.171.2011.
  8. John E. Hopcroft and Jeffrey D. Ullman. Some results on tape-bounded turing machines. J. ACM, 16(1):168-177, 1969. URL: http://dx.doi.org/10.1145/321495.321508.
  9. Emmanuel Jeandel and Pascal Vanier. π⁰₁ sets and tilings. In TAMC'11, pages 230-239, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20877-5_24.
  10. Emmanuel Jeandel and Pascal Vanier. Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type. In STACS'13, pages 490-501, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.490.
  11. Douglas A. Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, NY, USA, 1995. Google Scholar
  12. Alejandro Maass. On the sofic limit sets of cellular automata. Ergodic Theory Dynam. Systems, 15(4):663-684, 1995. URL: http://dx.doi.org/10.1017/S0143385700008609.
  13. Shahar Mozes. Tilings, substitutions systems and dynamical systems generated by them. J. d'Analyse Math., 53:139-186, 1989. Google Scholar
  14. Ronie Pavlov and Michael Schraudner. Classification of sofic projective subdynamics of multidimensional shifts of finite type. to appear in J. d'Analyse Math., 2010. Google Scholar
  15. Stephen G Simpson. Medvedev degrees of 2-dimensional subshifts of finite type. To appear in Ergodic Theory and Dynamical Systems, 2010. Google Scholar
  16. Hao Wang. Proving theorems by Pattern Recognition II. Bell Systems technical journal, 40:1-41, 1961. Google Scholar
  17. Benjamin Weiss. Subshifts of finite type and sofic systems. Monatsh. Math., 77:462-474, 1973. Google Scholar
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 About DROPS Imprint Privacy Contact