Take the 2-minute tour ×

I hope to find an online version of accessible texts in symbolic dynamics. Marcus and Lind have a text I hope to get online. What I don't know is if any text yet exists that considers symbolic dynamics over alternative domains or realms.

Much of the current theory studies what I will call one-dimensional shifts, which are essentially translations of strings of symbols, and so (to some extent) involve the combinatorics of infinite words, or certain subsets of $F^Z$ with $F$ often a finite set or alphabet and $Z$ being the integers, so the elements are bi-infinite words. But what of dynamics on $F^{Z \times Z}$, or on more exotic structures, say, where the exponent might be a sufficiently rich directed graph? Has the theory advanced to the point where symbolic dynamics in these realms can be as clearly understood as in the one-dimensional realm?

An ideal answer would come from a student or researcher who can fully address questions like "In order to get ready for studying SD in such realms, which portions of Marcus and Lind (or other accessible texts) should I read first?" or like "What are the one or two papers that illumined the subject of exotic SD for you?". I also welcome other references or suggested lines of research.

I am quite at the beginning of such studies; it won't bother me if you assume I am totally ignorant of dynamics in supplying an answer. My motivation is to find a few undecidable (in the sense of Turing computable) problems that I can use to gauge the decidability of certain problems in some resticted systems of second-order logic. A possible line of attack involves seeing how much symbolic dynamics in one-dimension carries over to more exotic realms. I welcome commments about such connections, too.

Gerhard "Time To Learn Something New" Paseman, 2011.04.29

share|improve this question
What do you mean by dynamics on $F^{\mathbb{Z} \times \mathbb{Z}}$? Are you still studying a single shift operator or are you studying both the horizontal and vertical shifts? –  Qiaochu Yuan Apr 30 '11 at 10:43
For that example, studying ( what I call ) a pair of shifts even like north and northwest would make sense. I use $Z \times Z$ more as an example, though. I'm hoping that a directed graph or a partially ordered algebraic structure might serve as exponent. Gerhard "Ask Me About System Design" Paseman, 2011.04.30 –  Gerhard Paseman Apr 30 '11 at 15:52

2 Answers 2

A good survey to consider in the beginning is http://www-users.math.umd.edu/users/mmb/papers/openfinalsub3nov2007.pdf You can also consider symbolic dynamics on trees : http://www-igm.univ-mlv.fr/~aubrun/articles/icalp09.pdf and other works by the same author. Also consider the following home.gwu.edu/~robinson/Documents/AMS.pdf You might enjoy scouring through http://vanha.math.utu.fi/staff/kari.php

share|improve this answer
In fact directed sets like trees were the (type of) exponent for which I was fishing. If you have more along those lines, or a suggestion for a web search beyond "symbolic dynamics trees", I would welcome it. Gerhard "Ask Me About System Design" Paseman, 2011.04.30 –  Gerhard Paseman May 1 '11 at 2:41
I am sorry I do not know much. I have just come across monge.univ-mlv.fr/~aubrun/recherche.html and her co-authors. –  Nishant Chandgotia May 1 '11 at 6:54

I believe what you're referring to here are called $\mathbb Z^d$-actions (with $d=2$ in your setting). This is a pretty large area of (algebraic) dynamics with people like Klaus Schmidt, Doug Lind, Thomas Ward and Manfried Einsiedler (and many others) actively working in it.

Perhaps, the following short survey paper by Klaus Schmidt could help you get going: http://www.mathematik.uni-bielefeld.de/~rehmann/ECM/cdrom/3ecm/pdfs/pant3/schdtk.pdf

share|improve this answer
Thank you. I hope the (algebraic) modifier holds promise of even more exotic realms. I shall look at Schmidt's survey. Gerhard "Ask Me About System Design" Paseman, 2011.04.30 –  Gerhard Paseman Apr 30 '11 at 15:57
Schmidt (Klaus, not wolfgang) wrote a book called "Dynamical Systems of Algebraic Origin" which might be of interest. Also, there's a second volume to the new recent book of Ward and Einsiedler which will talk about entropy, one his chapters is dedicated to the Rudolph-Johnson theorem, which is a prime example for uses of N^2 dynamics (which is also symbolic, if you look at it from a proper persepctive), you can catch the draft in - uea.ac.uk/menu/acad_depts/mth/entropy –  Asaf Apr 30 '11 at 18:49

Your Answer


