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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

16 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	431-460
Nombre de pages	30
journal	Ergodic Theory and Dynamical Systems
Volume	35
Numéro de publication	2
Les DOIs	https://doi.org/10.1017/etds.2013.60
état	Publié - 11 sept. 2015
Modification externe	Oui

Accès au document

10.1017/etds.2013.60

Contient cette citation

@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",

publisher = "Cambridge University Press",

number = "2",

}

TY - JOUR

T1 - Characterizations of periods of multi-dimensional shifts

AU - Jeandel, Emmanuel

AU - Vanier, Pascal

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation