Hostname: page-component-7b7567c8c-slfcl Total loading time: 0 Render date: 2026-11-19T08:05:17.372Z Has data issue: false hasContentIssue false

Characterizations of periods of multi-dimensional shifts

Published online by Cambridge University Press:  27 September 2013

EMMANUEL JEANDEL
Affiliation:
LORIA, Campus Scientifique, BP 239, 54506 Vandoeuvre-lès-Nancy, France email emmanuel.jeandel@loria.fr
PASCAL VANIER
Affiliation:
Einstein Institute of Mathematics, Hebrew University of Jerusalem, Givat Ram, Jerusalem 91904, Israel email pascal.vanier@ens-lyon.org
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that the sets of periods of multi-dimensional shifts of finite type are precisely the sets of integers of the complexity class NP. We also show that the functions counting their number are the functions of #P. We also give characterizations of some other notions of periodicity in terms of space complexity. We finish the paper by giving some characterizations for sofic and effective subshifts.

Information

Type
Research Article
Copyright
© Cambridge University Press, 2013