Shift space

Shift space

In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words representing the evolution of a discrete system. In fact, shift spaces and "symbolic dynamical systems" are often considered synonyms.

Notation

Let "A" be a finite set of states. An "infinite" (respectively "bi-infinite") "word" over "A" is a sequence mathbf x=(x_n)_{nin M}, where M=mathbb N (resp. M=mathbb Z) and x_n is in "A" for any integer "n".The shift operator acts on an infinite or bi-infinite word by shifting all symbols to the left, i.e.,:(sigma(mathbf x))(n)=x_{n+1} for all "n".In the following we choose M=mathbb N and thus speak of infinite words, but all definitions are naturally generalizable to the bi-infinite case.

Definition

A set of infinite words over "A" is a "shift space" if it is closed with respect to the natural product topology of A^mathbb N and invariant under the shift operator. Thus a set Ssubseteq A^mathbb N is a subshift if and only if
# for any (pointwise) convergent sequence (mathbf x_k)_{kgeq 0} of elements of "S", the limit lim_{k oinfty}mathbf x_k also belongs to "S"; and
# sigma(X)=X.

A shift space "S" is sometimes denoted as (S,sigma) in order to emphasize the role of the shift operator.

Some authors [cite journal|author = Thomsen, K.|title = On the structure of a sofic shift space|url = http://www.imf.au.dk/publications/pp/2003/imf-pp-2003-6.pdf |format = PDF Reprint|accessdate = 2008-01-29|journal = Transactions of the American Mathematical Society|volume = 356|year = 2004|pages = 3557–3619|doi = 10.1090/S0002-9947-04-03437-3 ] use the term "subshift" for a set of infinite words which is just invariant under the shift, and reserve the term "shift space" for those which are also closed.

Characterization and sofic subshifts

A subset "S" of A^mathbb N is a shift space if and only if there exists a set "X" of finite words such that "S" coincides with the set of all infinite words over "A" having no factor in "X".

When "X" is a regular language, the corresponding subshift is called sofic. In particular, if "X" is finite then "S" is called a subshift of finite type.

Examples

The first trivial example of shift space (of finite type) is the "full shift" A^mathbb N.

Let A={a,b}. The set of all infinite words over "A" containing at most one "b" is a sofic subshift, not of finite type.

Further reading

* cite book
author = Lind, Douglas
coauthors = Marcus, Brian
title = An Introduction to Symbolic Dynamics and Coding
year = 1995
publisher = Cambridge University Press
location = Cambridge UK
isbn = 0521559006

* cite book
author = Lothaire, M.
title = Algebraic Combinatorics on Words
url = http://www-igm.univ-mlv.fr/~berstel/Lothaire/AlgCWContents.html
accessdate = 2008-01-29
year = 2002
publisher = Cambridge University Press
location = Cambridge UK
isbn = 0521812208
chapter = Finite and Infinite Words
chapterurl = http://www-igm.univ-mlv.fr/%7Eberstel/Lothaire/ChapitresACW/C1.ps

* cite journal
author = Morse, Marston
authorlink = Marston Morse
coauthors = Hedlund, Gustav A.
title = Symbolic Dynamics
url = http://links.jstor.org/sici?sici=0002-9327(193810)60%3A4%3C815%3ASD%3E2.0.CO%3B2-4
format = JSTOR
accessdate = 2008-01-29
journal = American Journal of Mathematics
volume = 60
year = 1938
pages = 815–866
doi = 10.2307/2371264

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Shift JIS — (also SJIS, MIME name Shift JIS) is a character encoding for the Japanese language originally developed by a Japanese company called ASCII Corporation in conjunction with Microsoft and standardized as JIS X 0208 Appendix 1. It is based on… …   Wikipedia

  • Space Taxi — Entwickler John F. Kutcher Publisher …   Deutsch Wikipedia

  • Space Groove — is an album recorded by ProjeKct Two, a King Crimson frakctal group. It was recorded at Studio Belewbeldible during November 19 November 21, 1997.Track listVolume One: Space Groove # Space Groove II 19:03 # Space Groove III 2:40 # Space Groove I… …   Wikipedia

  • Space shifting — is a concept that has been argued in copyright law to permit owners of some form of media, such as a song or movie, to convert that media from one format to another, generally by converting an audiotape, videotape, compact disc, or DVD into an… …   Wikipedia

  • Shift operator — In mathematics, and in particular functional analysis, the shift operators are examples of linear operators, important for their simplicity and natural occurrence. They are used in diverse areas, such as Hardy spaces, the theory of abelian… …   Wikipedia

  • space exploration — Investigation of the universe beyond Earth s atmosphere by means of manned and unmanned spacecraft. Study of the use of rockets for spaceflight began early in the 20th century. Germany s research on rocket propulsion in the 1930s led to… …   Universalium

  • Space-cadet keyboard — The Space cadet keyboard is a device used on MIT Lisp machines and designed by Tom Knight, which inspired several still current jargon terms in the field of computer science and influenced the design of Emacs. It was inspired by the Knight… …   Wikipedia

  • Shift matrix — In mathematics, a shift matrix is a binary matrix with ones only on the superdiagonal or subdiagonal, and zeroes elsewhere. A shift matrix U with ones on the superdiagonal is an upper shift matrix.The alternative subdiagonal matrix L is… …   Wikipedia

  • Space Race — For a discussion of all spaceflight programs to date, see History of spaceflight. For a list of key events, see Timeline of space exploration. For other uses of the term, see Space Race (disambiguation). A replica of Sputnik 1, the world s… …   Wikipedia

  • Space Shuttle Challenger disaster — For more information about the final mission and crew of the Challenger, see STS 51 L. Space Shuttle Challenger s smoke plume after the in flight breakup that killed all seven crew members …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”