Characterizations of periods of multi-dimensional shifts

Emmanuel Jeandel; Pascal Vanier

doi:10.1017/etds.2013.60

Characterizations of periods of multi-dimensional shifts

Emmanuel Jeandel
, Pascal Vanier

LORIA Laboratoire Lorrain de Recherche en Informatique et ses Applications
The Hebrew University of Jerusalem

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	431-460
Number of pages	30
Journal	Ergodic Theory and Dynamical Systems
Volume	35
Issue number	2
DOIs	https://doi.org/10.1017/etds.2013.60
Publication status	Published - 11 Sept 2015
Externally published	Yes

Access to Document

10.1017/etds.2013.60

Cite this

@article{881d62e4982140b794080a7844734006,

title = "Characterizations of periods of multi-dimensional shifts",

abstract = "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.",

author = "Emmanuel Jeandel and Pascal Vanier",

note = "Publisher Copyright: {\textcopyright} Cambridge University Press, 2013.",

year = "2015",

month = sep,

day = "11",

doi = "10.1017/etds.2013.60",

language = "English",

volume = "35",

pages = "431--460",

journal = "Ergodic Theory and Dynamical Systems",

issn = "0143-3857",

number = "2",

}

TY - JOUR

T1 - Characterizations of periods of multi-dimensional shifts

AU - Jeandel, Emmanuel

AU - Vanier, Pascal

N1 - Publisher Copyright: © Cambridge University Press, 2013.

PY - 2015/9/11

Y1 - 2015/9/11

N2 - 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.

AB - 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.

U2 - 10.1017/etds.2013.60

DO - 10.1017/etds.2013.60

M3 - Article

AN - SCOPUS:84924207004

SN - 0143-3857

VL - 35

SP - 431

EP - 460

JO - Ergodic Theory and Dynamical Systems

JF - Ergodic Theory and Dynamical Systems

IS - 2

ER -

Characterizations of periods of multi-dimensional shifts

Abstract

Access to Document

Fingerprint

Cite this