320:
1561:
is an image of a subshift of finite type where different edges of the transition graph may be mapped to the same symbol. For example, if one only watches the output from a hidden Markov chain, then the output appears to be a sofic system. It may be regarded as the set of labellings of paths through
1488:
is then any subspace of the full shift that is shift-invariant (that is, a subspace that is invariant under the action of the shift operator), non-empty, and closed for the product topology defined below. Some subshifts can be characterized by a transition matrix, as above; such subshifts are then
1826:
1346:
2968:
1137:
1603:), with certain nearest-neighbor configurations excluded. Interacting Ising models are defined as subshifts together with a continuous function of the configuration space (continuous with respect to the product topology, defined below); the
2824:
2032:
2697:
728:
Conversely, there exists a space of subshifts on 6 symbols, projected to subshifts on 2 symbols, such that any Markov measure on the smaller subshift has a preimage measure that is not Markov of any order (Example 2.6 ).
3081:
1672:
2207:
A variety of different metrics can be defined on a shift space. One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common; this is the
276:
2503:
1176:
2847:
1425:
1445:: there is a sequence of edges from any one vertex to any other vertex. It is precisely transitive subshifts of finite type which correspond to dynamical systems with orbits that are dense.
3174:
723:
149:
984:
192:. It consists of sequences whose transitions between consecutive letters are only those allowed by the graph. For this example, the subshift consists of only three one-sided sequences:
2353:
443:
331:
and an invariant distribution on the states, we can impose a probability measure on the set of subshifts. For example, consider the Markov chain given on the left on the states
2073:
1871:
1662:
2191:
2143:
2106:
778:
190:
529:
375:
2423:
483:
305:
663:
96:
636:
610:
581:
555:
3223:
2712:
1884:
2542:
1456:: it has a graph with an edge that connects every vertex to every other vertex; that is, all of the entries of the adjacency matrix are 1. The full
2995:
3491:
1821:{\displaystyle V^{\mathbb {Z} }=\prod _{n\in \mathbb {Z} }V=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in V\;\forall k\in \mathbb {Z} \}}
2235:
3540:
3451:
3427:
3385:
3349:
3407:
1604:
1341:{\displaystyle \Sigma _{A}=\left\{(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}.}
3582:
3572:
195:
3529:
Symbolic
Dynamics and Its Applications: American Mathematical Society, Short Course, January 4-5, 2002, San Diego, California
3510:
2431:
2156:
66:
A (one-sided) shift of finite type is the set of all sequences, infinite on one end only, that can be made up of the letters
2963:{\displaystyle \zeta (z)=\exp \left(\sum _{n=1}^{\infty }{\Bigl |}{\textrm {Fix}}(T^{n}){\Bigr |}{\frac {z^{n}}{n}}\right),}
2835:
3532:
3483:
2703:
308:
1364:
1132:{\displaystyle \Sigma _{A}^{+}=\left\{(x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}.}
3224:
Sofic
Measures: Characterizations of Hidden Markov Chains by Linear Algebra, Formal Languages, and Symbolic Dynamics
3104:
3587:
3443:
3341:
1442:
668:
101:
3577:
2982:
3479:
1578:
328:
1526:
557:, and this projection also projects the probability measure down to a probability measure on the subshifts on
2301:
3567:
3195:
1615:
1567:
151:. A (two-sided) shift of finite type is similar, but consists of sequences that are infinite on both ends.
1588:
is defined to be the set of all infinite concatenations of some fixed finite collection of finite words.
2231:
1608:
1510:
1465:
380:
278:. Similarly, the two-sided subshift described by this graph consists of only three two-sided sequences.
2046:
1844:
1635:
2167:
2119:
2082:
1546:
754:
725:, meaning that the observable part of the system can be affected by something infinitely in the past.
157:
3369:
1542:
1538:
1534:
1167:
968:
281:
Other directed graphs on the same letters produce other subshifts. For example, adding another arrow
51:
1358:
maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e.
2839:
1530:
936:
488:
334:
3245:
2392:
963:
obtained in this way. If the sequence extends to infinity in only one direction, it is called a
448:
3531:. Proceedings of symposia in applied mathematics: AMS short course lecture notes. Vol. 60.
947:
on such sequences; it plays the role of the time-evolution operator of the dynamical system. A
3422:, Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991).
3536:
3506:
3487:
3447:
3423:
3381:
3345:
3185:
3091:
1836:
798:
43:
39:
2114:
union of cylinder sets. Every open set in the subshift is the intersection of an open set of
3546:
3457:
3391:
1627:
1571:
1506:
1461:
860:
806:
638:, not even multiple orders. Intuitively, this is because if one observes a long sequence of
284:
641:
69:
3550:
3461:
3402:
3395:
3377:
3227:- Karl Petersen, Mathematics 210, Spring 2006, University of North Carolina at Chapel Hill
3190:
1563:
1518:
615:
589:
560:
534:
17:
3282:
1522:
1514:
1352:
944:
868:
787:
307:
to the graph produces a subshift that, instead of containing three sequences, contains
47:
319:
3561:
3473:
3469:
3431:(Provides a short expository introduction, with exercises, and extensive references.)
2216:
2209:
2152:
1489:
called subshifts of finite type. Often, subshifts of finite type are called simply
3437:
3090:
runs over the closed orbits. For subshifts of finite type, the zeta function is a
2243:
2219:
1876:
939:
of the graph, and the sequence can be either one-sided or two-sided infinite. Let
323:
The hidden part of a hidden Markov model, whose observable states is non-Markovian.
154:
A subshift can be defined by a directed graph on these letters, such as the graph
2819:{\displaystyle s_{\mu }=-\sum _{i=1}^{n}\pi _{i}\sum _{j=1}^{n}p_{ij}\log p_{ij}}
2027:{\displaystyle C_{t}=\{x\in V^{\mathbb {Z} }:x_{t}=a_{0},\ldots ,x_{t+s}=a_{s}\}}
1591:
Subshifts of finite type are identical to free (non-interacting) one-dimensional
3290:
1600:
1592:
55:
31:
2692:{\displaystyle \mu (C_{t})=\pi _{a_{0}}p_{a_{0},a_{1}}\cdots p_{a_{s-1},a_{s}}}
2196:
2038:
818:
3076:{\displaystyle \zeta (z)=\prod _{\gamma }\left(1-z^{|\gamma |}\right)^{-1}\ }
2111:
2230:
A subshift of finite type may be endowed with any one of several different
1509:
are isomorphic to subshifts of finite type; examples include systems with
3360:
1614:
Subshifts may be quantized in a certain way, leading to the idea of the
1430:
Clearly this map is only invertible in the case of the two-sided shift.
3200:
1566:: a subshift of finite type then corresponds to an automaton which is
586:
The curious thing is that the probability measure on the subshifts on
50:. They also describe the set of all possible sequences executed by a
1577:
Context-free systems are defined analogously, and are generated by
1142:
This is the space of all sequences of symbols such that the symbol
3250:
3372:; Ferenczi, SĂ©bastien; Mauduit, Christian; Siegel, A. (eds.).
1875:
which induces the topology of the subshift, is the family of
3503:
Grammatical
Complexity and One-Dimensional Dynamical Systems
2147:
with the subshift. With respect to this topology, the shift
3242:
Hidden Markov processes in the context of symbolic dynamics
271:{\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots }
3376:. Lecture Notes in Mathematics. Vol. 1794. Berlin:
3374:
Substitutions in dynamics, arithmetics and combinatorics
2215:. In fact, both the one- and two-sided shift spaces are
3420:
Ergodic Theory, Symbolic
Dynamics and Hyperbolic Spaces
2498:{\displaystyle \sum _{i=1}^{n}\pi _{i}p_{ij}=\pi _{j}.}
3505:. Directions in Chaos. Vol. 6. World Scientific.
2395:
1611:
are explicitly expressible in terms of this function.
3475:
3107:
2998:
2850:
2715:
2545:
2434:
2304:
2170:
2122:
2085:
2049:
1887:
1847:
1675:
1638:
1493:. Subshifts of finite type are also sometimes called
1368:
1367:
1179:
987:
757:
671:
644:
618:
592:
563:
537:
491:
451:
383:
337:
287:
198:
160:
104:
72:
1626:
A subshift has a natural topology, derived from the
3361:
Strictly
Ergodic Subshifts and Associated Operators
978:Formally, one may define the sequences of edges as
665:, then one would become increasingly sure that the
3408:Subshifts of Finite Type, Sofic Systems and Graphs
3168:
3075:
2962:
2818:
2691:
2497:
2417:
2347:
2185:
2137:
2100:
2067:
2026:
1865:
1820:
1656:
1419:
1340:
1131:
772:
717:
657:
630:
604:
575:
549:
523:
477:
437:
369:
299:
270:
184:
143:
90:
2930:
2900:
2155:; that is, with respect to this topology, it is
1420:{\displaystyle \displaystyle (T(x))_{j}=x_{j+1}.}
3283:Ergodic Theory: Basic Examples and Constructions
3126:
2508:A Markov chain, as defined above, is said to be
42:, and in particular are the objects of study in
3439:An introduction to symbolic dynamics and coding
893:the set of edges containing the directed edge
3287:Encyclopedia of Complexity and Systems Science
3169:{\displaystyle \zeta (z)=(\det(I-zA))^{-1}\ .}
3291:https://doi.org/10.1007/978-0-387-30440-3_177
718:{\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}
144:{\displaystyle AAA\cdots ,ABAB\cdots ,\dots }
27:Type of shift space studied in ergodic theory
8:
2021:
1936:
1815:
1715:
782:of all bi-infinite sequences of elements of
3416:Ergodic theory and subshifts of finite type
3240:Boyle, Mike; Petersen, Karl (2010-01-13),
1800:
3281:Matthew Nicol and Karl Petersen, (2009) "
3249:
3151:
3106:
3061:
3049:
3041:
3040:
3018:
2997:
2941:
2935:
2929:
2928:
2919:
2906:
2905:
2899:
2898:
2892:
2881:
2849:
2807:
2788:
2778:
2767:
2757:
2747:
2736:
2720:
2714:
2681:
2662:
2657:
2642:
2629:
2624:
2612:
2607:
2588:
2569:
2556:
2544:
2536:of a cylinder set may then be defined by
2486:
2470:
2460:
2450:
2439:
2433:
2403:
2394:
2330:
2320:
2309:
2303:
2177:
2176:
2175:
2169:
2129:
2128:
2127:
2121:
2092:
2091:
2090:
2084:
2056:
2055:
2054:
2048:
2015:
1996:
1977:
1964:
1951:
1950:
1949:
1924:
1905:
1892:
1886:
1854:
1853:
1852:
1846:
1811:
1810:
1788:
1766:
1753:
1737:
1703:
1702:
1695:
1682:
1681:
1680:
1674:
1645:
1644:
1643:
1637:
1401:
1388:
1366:
1326:
1325:
1296:
1286:
1281:
1262:
1240:
1227:
1211:
1184:
1178:
1117:
1116:
1087:
1077:
1072:
1053:
1031:
1018:
997:
992:
986:
764:
763:
762:
756:
705:
693:
684:
670:
649:
643:
617:
591:
562:
536:
515:
502:
490:
469:
456:
450:
445:. If we "forget" the distinction between
424:
410:
396:
382:
361:
348:
336:
286:
197:
159:
103:
71:
2989:-fold shift. It has a product formula
485:, we project this space of subshifts on
318:
3212:
2706:with relation to the Markov measure is
2348:{\displaystyle \sum _{j=1}^{n}p_{ij}=1}
3336:Brin, Michael; Stuck, Garrett (2002).
3309:
3307:
1533:(this is the first system shown to be
967:subshift of finite type, and if it is
3436:Lind, Douglas; Marcus, Brian (1995).
839:is the set of finite subsequences of
7:
3418:, (1991), appearing as Chapter 2 in
3235:
3233:
3218:
3216:
1433:A subshift of finite type is called
867:Using these elements we construct a
612:is not created by a Markov chain on
2236:measure-preserving dynamical system
1480:is understood to refer to the full
935:it is meant that the sequence is a
531:into another space of subshifts on
2893:
2238:. A common object of study is the
1801:
1181:
989:
438:{\displaystyle \pi =(2/7,4/7,1/7)}
58:are the subshifts of finite type.
25:
3338:Introduction to Dynamical Systems
2512:with the shift of finite type if
2068:{\displaystyle V^{\mathbb {Z} }.}
1866:{\displaystyle V^{\mathbb {Z} },}
1657:{\displaystyle V^{\mathbb {Z} },}
1511:transverse homoclinic connections
1448:An important special case is the
3527:Williams, Susan G., ed. (2004).
2186:{\displaystyle V^{\mathbb {Z} }}
2138:{\displaystyle V^{\mathbb {Z} }}
2101:{\displaystyle V^{\mathbb {Z} }}
773:{\displaystyle V^{\mathbb {Z} }}
185:{\displaystyle A\to B\to C\to A}
1839:. A basis for the topology of
3148:
3144:
3129:
3123:
3117:
3111:
3050:
3042:
3008:
3002:
2925:
2912:
2860:
2854:
2597:
2594:
2562:
2549:
2246:to the topology of the shift.
1930:
1898:
1778:
1724:
1385:
1381:
1375:
1369:
1252:
1198:
1146:can be followed by the symbol
1043:
1011:
702:
699:
685:
678:
432:
390:
377:, with invariant distribution
315:Markov and non-Markov measures
309:an uncountably infinite number
291:
176:
170:
164:
1:
3533:American Mathematical Society
3484:American Mathematical Society
2364:stationary probability vector
2242:, which is an extension of a
1570:. Such systems correspond to
931:sequences of edges, where by
524:{\displaystyle A,B_{1},B_{2}}
370:{\displaystyle A,B_{1},B_{2}}
3322:Brin & Stuck (2002) p.61
3313:Brin & Stuck (2002) p.60
2418:{\textstyle \sum \pi _{i}=1}
832:and the associated language
1599:-letter generalizations of
927:be the set of all infinite
478:{\displaystyle B_{1},B_{2}}
3604:
3444:Cambridge University Press
3342:Cambridge University Press
1460:-shift corresponds to the
951:is then defined as a pair
54:. The most widely studied
3368:Pytheas Fogg, N. (2002).
3301:Pytheas Fogg (2002) p.205
2836:Artin–Mazur zeta function
2249:A Markov chain is a pair
2159:with continuous inverse.
1579:phrase structure grammars
1527:Prouhet–Thue–Morse system
1495:topological Markov shifts
975:subshift of finite type.
745:symbols (alphabet). Let
2704:Kolmogorov–Sinai entropy
1476:By convention, the term
1170:is defined analogously:
1162:-th entry of the matrix
889:the set of vertices and
329:Markov transition matrix
36:subshifts of finite type
18:Subshifts of finite type
3196:Quantum finite automata
1616:quantum finite automata
1166:is 1. The space of all
949:subshift of finite type
3583:Combinatorics on words
3573:Automata (computation)
3170:
3077:
2964:
2897:
2820:
2783:
2752:
2693:
2499:
2455:
2419:
2349:
2325:
2187:
2139:
2102:
2069:
2037:The cylinder sets are
2028:
1867:
1822:
1658:
1421:
1342:
1133:
774:
719:
659:
632:
606:
577:
551:
525:
479:
439:
371:
324:
301:
300:{\displaystyle A\to C}
272:
186:
145:
92:
3171:
3078:
2965:
2877:
2821:
2763:
2732:
2694:
2500:
2435:
2420:
2350:
2305:
2195:is homeomorphic to a
2188:
2140:
2103:
2070:
2029:
1868:
1823:
1659:
1491:shifts of finite type
1422:
1343:
1168:bi-infinite sequences
1134:
775:
720:
660:
658:{\displaystyle B^{n}}
633:
607:
578:
552:
526:
480:
440:
372:
322:
302:
273:
187:
146:
93:
91:{\displaystyle A,B,C}
3501:Xie, Huimin (1996).
3105:
2996:
2848:
2713:
2543:
2432:
2393:
2302:
2234:, thus leading to a
2168:
2120:
2083:
2047:
1885:
1845:
1673:
1636:
1365:
1177:
985:
755:
669:
642:
616:
590:
561:
535:
489:
449:
381:
335:
285:
196:
158:
102:
70:
52:finite state machine
2840:formal power series
1002:
945:left shift operator
741:be a finite set of
631:{\displaystyle A,B}
605:{\displaystyle A,B}
576:{\displaystyle A,B}
550:{\displaystyle A,B}
62:Motivating examples
3414:Michael S. Keane,
3166:
3073:
3023:
2960:
2838:is defined as the
2816:
2689:
2495:
2415:
2345:
2257:consisting of the
2183:
2135:
2098:
2077:Every open set in
2065:
2024:
1863:
1818:
1708:
1654:
1605:partition function
1443:strongly connected
1417:
1416:
1338:
1129:
988:
824:-invariant subset
786:together with the
770:
715:
655:
628:
602:
573:
547:
521:
475:
435:
367:
325:
297:
268:
182:
141:
88:
38:are used to model
3588:Symbolic dynamics
3493:978-0-8218-8328-0
3186:Transfer operator
3162:
3092:rational function
3072:
3014:
2950:
2909:
2259:transition matrix
1837:discrete topology
1691:
1572:regular languages
1507:dynamical systems
971:, it is called a
799:discrete topology
713:
44:symbolic dynamics
40:dynamical systems
16:(Redirected from
3595:
3578:Markov processes
3554:
3516:
3497:
3465:
3399:
3355:
3340:(2nd ed.).
3323:
3320:
3314:
3311:
3302:
3299:
3293:
3279:
3273:
3270:
3264:
3261:
3255:
3254:
3253:
3237:
3228:
3220:
3175:
3173:
3172:
3167:
3160:
3159:
3158:
3097:
3089:
3082:
3080:
3079:
3074:
3070:
3069:
3068:
3060:
3056:
3055:
3054:
3053:
3045:
3022:
2988:
2980:
2969:
2967:
2966:
2961:
2956:
2952:
2951:
2946:
2945:
2936:
2934:
2933:
2924:
2923:
2911:
2910:
2907:
2904:
2903:
2896:
2891:
2825:
2823:
2822:
2817:
2815:
2814:
2796:
2795:
2782:
2777:
2762:
2761:
2751:
2746:
2725:
2724:
2698:
2696:
2695:
2690:
2688:
2687:
2686:
2685:
2673:
2672:
2649:
2648:
2647:
2646:
2634:
2633:
2619:
2618:
2617:
2616:
2593:
2592:
2574:
2573:
2561:
2560:
2531:
2521:
2504:
2502:
2501:
2496:
2491:
2490:
2478:
2477:
2465:
2464:
2454:
2449:
2424:
2422:
2421:
2416:
2408:
2407:
2388:
2378:
2361:
2354:
2352:
2351:
2346:
2338:
2337:
2324:
2319:
2294:
2284:
2270:
2256:
2212:
2194:
2192:
2190:
2189:
2184:
2182:
2181:
2180:
2150:
2146:
2144:
2142:
2141:
2136:
2134:
2133:
2132:
2109:
2107:
2105:
2104:
2099:
2097:
2096:
2095:
2076:
2074:
2072:
2071:
2066:
2061:
2060:
2059:
2033:
2031:
2030:
2025:
2020:
2019:
2007:
2006:
1982:
1981:
1969:
1968:
1956:
1955:
1954:
1929:
1928:
1910:
1909:
1897:
1896:
1874:
1872:
1870:
1869:
1864:
1859:
1858:
1857:
1834:
1827:
1825:
1824:
1819:
1814:
1793:
1792:
1771:
1770:
1758:
1757:
1745:
1744:
1707:
1706:
1687:
1686:
1685:
1665:
1663:
1661:
1660:
1655:
1650:
1649:
1648:
1628:product topology
1598:
1547:Toeplitz systems
1543:Sturmian systems
1521:with a positive
1519:closed manifolds
1483:
1462:Bernoulli scheme
1459:
1453:
1440:
1426:
1424:
1423:
1418:
1412:
1411:
1393:
1392:
1357:
1347:
1345:
1344:
1339:
1334:
1330:
1329:
1309:
1308:
1307:
1306:
1291:
1290:
1267:
1266:
1245:
1244:
1232:
1231:
1219:
1218:
1189:
1188:
1165:
1161:
1149:
1145:
1138:
1136:
1135:
1130:
1125:
1121:
1120:
1100:
1099:
1098:
1097:
1082:
1081:
1058:
1057:
1036:
1035:
1023:
1022:
1001:
996:
962:
942:
926:
922:
906:
902:
892:
888:
884:
866:
863:with entries in
861:adjacency matrix
859:
849:
842:
838:
831:
827:
823:
807:product topology
804:
796:
792:
785:
781:
779:
777:
776:
771:
769:
768:
767:
748:
744:
740:
724:
722:
721:
716:
714:
706:
698:
697:
688:
664:
662:
661:
656:
654:
653:
637:
635:
634:
629:
611:
609:
608:
603:
582:
580:
579:
574:
556:
554:
553:
548:
530:
528:
527:
522:
520:
519:
507:
506:
484:
482:
481:
476:
474:
473:
461:
460:
444:
442:
441:
436:
428:
414:
400:
376:
374:
373:
368:
366:
365:
353:
352:
306:
304:
303:
298:
277:
275:
274:
269:
191:
189:
188:
183:
150:
148:
147:
142:
97:
95:
94:
89:
21:
3603:
3602:
3598:
3597:
3596:
3594:
3593:
3592:
3558:
3557:
3543:
3526:
3523:
3521:Further reading
3513:
3500:
3494:
3468:
3454:
3435:
3403:Natasha Jonoska
3388:
3378:Springer-Verlag
3370:Berthé, Valérie
3367:
3358:David Damanik,
3352:
3335:
3332:
3327:
3326:
3321:
3317:
3312:
3305:
3300:
3296:
3280:
3276:
3272:Xie (1996) p.22
3271:
3267:
3263:Xie (1996) p.21
3262:
3258:
3239:
3238:
3231:
3221:
3214:
3209:
3191:De Bruijn graph
3182:
3147:
3103:
3102:
3095:
3087:
3036:
3029:
3025:
3024:
2994:
2993:
2986:
2974:
2937:
2915:
2876:
2872:
2846:
2845:
2832:
2803:
2784:
2753:
2716:
2711:
2710:
2677:
2658:
2653:
2638:
2625:
2620:
2608:
2603:
2584:
2565:
2552:
2541:
2540:
2528:
2523:
2518:
2513:
2482:
2466:
2456:
2430:
2429:
2399:
2391:
2390:
2385:
2380:
2375:
2366:
2359:
2326:
2300:
2299:
2291:
2286:
2281:
2272:
2262:
2250:
2228:
2210:
2205:
2171:
2166:
2165:
2163:
2148:
2123:
2118:
2117:
2115:
2086:
2081:
2080:
2078:
2050:
2045:
2044:
2042:
2011:
1992:
1973:
1960:
1945:
1920:
1901:
1888:
1883:
1882:
1848:
1843:
1842:
1840:
1832:
1784:
1762:
1749:
1733:
1676:
1671:
1670:
1639:
1634:
1633:
1631:
1624:
1596:
1555:
1553:Generalizations
1539:strongly mixing
1515:diffeomorphisms
1503:
1481:
1474:
1457:
1451:
1438:
1397:
1384:
1363:
1362:
1355:
1292:
1282:
1277:
1258:
1236:
1223:
1207:
1197:
1193:
1180:
1175:
1174:
1163:
1151:
1147:
1143:
1083:
1073:
1068:
1049:
1027:
1014:
1010:
1006:
983:
982:
952:
940:
924:
920:
908:
907:if and only if
904:
894:
890:
886:
871:
864:
851:
847:
840:
837:
833:
829:
825:
821:
802:
794:
790:
783:
758:
753:
752:
750:
749:denote the set
746:
742:
738:
735:
689:
667:
666:
645:
640:
639:
614:
613:
588:
587:
559:
558:
533:
532:
511:
498:
487:
486:
465:
452:
447:
446:
379:
378:
357:
344:
333:
332:
317:
283:
282:
194:
193:
156:
155:
100:
99:
68:
67:
64:
28:
23:
22:
15:
12:
11:
5:
3601:
3599:
3591:
3590:
3585:
3580:
3575:
3570:
3568:Ergodic theory
3560:
3559:
3556:
3555:
3541:
3522:
3519:
3518:
3517:
3511:
3498:
3492:
3470:Teschl, Gerald
3466:
3452:
3433:
3412:
3400:
3386:
3365:
3356:
3350:
3331:
3328:
3325:
3324:
3315:
3303:
3294:
3274:
3265:
3256:
3229:
3211:
3210:
3208:
3205:
3204:
3203:
3198:
3193:
3188:
3181:
3178:
3177:
3176:
3165:
3157:
3154:
3150:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3084:
3083:
3067:
3064:
3059:
3052:
3048:
3044:
3039:
3035:
3032:
3028:
3021:
3017:
3013:
3010:
3007:
3004:
3001:
2981:is the set of
2971:
2970:
2959:
2955:
2949:
2944:
2940:
2932:
2927:
2922:
2918:
2914:
2902:
2895:
2890:
2887:
2884:
2880:
2875:
2871:
2868:
2865:
2862:
2859:
2856:
2853:
2831:
2828:
2827:
2826:
2813:
2810:
2806:
2802:
2799:
2794:
2791:
2787:
2781:
2776:
2773:
2770:
2766:
2760:
2756:
2750:
2745:
2742:
2739:
2735:
2731:
2728:
2723:
2719:
2700:
2699:
2684:
2680:
2676:
2671:
2668:
2665:
2661:
2656:
2652:
2645:
2641:
2637:
2632:
2628:
2623:
2615:
2611:
2606:
2602:
2599:
2596:
2591:
2587:
2583:
2580:
2577:
2572:
2568:
2564:
2559:
2555:
2551:
2548:
2534:Markov measure
2526:
2516:
2506:
2505:
2494:
2489:
2485:
2481:
2476:
2473:
2469:
2463:
2459:
2453:
2448:
2445:
2442:
2438:
2414:
2411:
2406:
2402:
2398:
2383:
2373:
2356:
2355:
2344:
2341:
2336:
2333:
2329:
2323:
2318:
2315:
2312:
2308:
2289:
2285:for which all
2279:
2240:Markov measure
2227:
2224:
2204:
2201:
2179:
2174:
2131:
2126:
2094:
2089:
2064:
2058:
2053:
2035:
2034:
2023:
2018:
2014:
2010:
2005:
2002:
1999:
1995:
1991:
1988:
1985:
1980:
1976:
1972:
1967:
1963:
1959:
1953:
1948:
1944:
1941:
1938:
1935:
1932:
1927:
1923:
1919:
1916:
1913:
1908:
1904:
1900:
1895:
1891:
1862:
1856:
1851:
1829:
1828:
1817:
1813:
1809:
1806:
1803:
1799:
1796:
1791:
1787:
1783:
1780:
1777:
1774:
1769:
1765:
1761:
1756:
1752:
1748:
1743:
1740:
1736:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1705:
1701:
1698:
1694:
1690:
1684:
1679:
1653:
1647:
1642:
1623:
1620:
1586:renewal system
1554:
1551:
1523:metric entropy
1502:
1499:
1473:
1470:
1428:
1427:
1415:
1410:
1407:
1404:
1400:
1396:
1391:
1387:
1383:
1380:
1377:
1374:
1371:
1353:shift operator
1349:
1348:
1337:
1333:
1328:
1324:
1321:
1318:
1315:
1312:
1305:
1302:
1299:
1295:
1289:
1285:
1280:
1276:
1273:
1270:
1265:
1261:
1257:
1254:
1251:
1248:
1243:
1239:
1235:
1230:
1226:
1222:
1217:
1214:
1210:
1206:
1203:
1200:
1196:
1192:
1187:
1183:
1140:
1139:
1128:
1124:
1119:
1115:
1112:
1109:
1106:
1103:
1096:
1093:
1090:
1086:
1080:
1076:
1071:
1067:
1064:
1061:
1056:
1052:
1048:
1045:
1042:
1039:
1034:
1030:
1026:
1021:
1017:
1013:
1009:
1005:
1000:
995:
991:
912:
869:directed graph
835:
788:shift operator
766:
761:
734:
731:
712:
709:
704:
701:
696:
692:
687:
683:
680:
677:
674:
652:
648:
627:
624:
621:
601:
598:
595:
572:
569:
566:
546:
543:
540:
518:
514:
510:
505:
501:
497:
494:
472:
468:
464:
459:
455:
434:
431:
427:
423:
420:
417:
413:
409:
406:
403:
399:
395:
392:
389:
386:
364:
360:
356:
351:
347:
343:
340:
316:
313:
311:of sequences.
296:
293:
290:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
181:
178:
175:
172:
169:
166:
163:
140:
137:
134:
131:
128:
125:
122:
119:
116:
113:
110:
107:
87:
84:
81:
78:
75:
63:
60:
48:ergodic theory
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3600:
3589:
3586:
3584:
3581:
3579:
3576:
3574:
3571:
3569:
3566:
3565:
3563:
3552:
3548:
3544:
3542:0-8218-3157-7
3538:
3534:
3530:
3525:
3524:
3520:
3514:
3508:
3504:
3499:
3495:
3489:
3485:
3481:
3477:
3476:
3471:
3467:
3463:
3459:
3455:
3453:0-521-55124-2
3449:
3445:
3441:
3440:
3434:
3432:
3429:
3428:0-19-853390-X
3425:
3421:
3417:
3413:
3410:
3409:
3404:
3401:
3397:
3393:
3389:
3387:3-540-44141-7
3383:
3379:
3375:
3371:
3366:
3363:
3362:
3357:
3353:
3351:0-521-80841-3
3347:
3343:
3339:
3334:
3333:
3329:
3319:
3316:
3310:
3308:
3304:
3298:
3295:
3292:
3288:
3284:
3278:
3275:
3269:
3266:
3260:
3257:
3252:
3247:
3243:
3236:
3234:
3230:
3226:
3225:
3219:
3217:
3213:
3206:
3202:
3199:
3197:
3194:
3192:
3189:
3187:
3184:
3183:
3179:
3163:
3155:
3152:
3141:
3138:
3135:
3132:
3120:
3114:
3108:
3101:
3100:
3099:
3093:
3065:
3062:
3057:
3046:
3037:
3033:
3030:
3026:
3019:
3015:
3011:
3005:
2999:
2992:
2991:
2990:
2984:
2978:
2957:
2953:
2947:
2942:
2938:
2920:
2916:
2888:
2885:
2882:
2878:
2873:
2869:
2866:
2863:
2857:
2851:
2844:
2843:
2842:
2841:
2837:
2830:Zeta function
2829:
2811:
2808:
2804:
2800:
2797:
2792:
2789:
2785:
2779:
2774:
2771:
2768:
2764:
2758:
2754:
2748:
2743:
2740:
2737:
2733:
2729:
2726:
2721:
2717:
2709:
2708:
2707:
2705:
2682:
2678:
2674:
2669:
2666:
2663:
2659:
2654:
2650:
2643:
2639:
2635:
2630:
2626:
2621:
2613:
2609:
2604:
2600:
2589:
2585:
2581:
2578:
2575:
2570:
2566:
2557:
2553:
2546:
2539:
2538:
2537:
2535:
2529:
2519:
2511:
2492:
2487:
2483:
2479:
2474:
2471:
2467:
2461:
2457:
2451:
2446:
2443:
2440:
2436:
2428:
2427:
2426:
2412:
2409:
2404:
2400:
2396:
2386:
2376:
2369:
2365:
2342:
2339:
2334:
2331:
2327:
2321:
2316:
2313:
2310:
2306:
2298:
2297:
2296:
2292:
2282:
2275:
2269:
2265:
2260:
2254:
2247:
2245:
2241:
2237:
2233:
2225:
2223:
2221:
2220:metric spaces
2218:
2214:
2202:
2200:
2198:
2172:
2160:
2158:
2154:
2153:homeomorphism
2124:
2113:
2087:
2062:
2051:
2040:
2016:
2012:
2008:
2003:
2000:
1997:
1993:
1989:
1986:
1983:
1978:
1974:
1970:
1965:
1961:
1957:
1946:
1942:
1939:
1933:
1925:
1921:
1917:
1914:
1911:
1906:
1902:
1893:
1889:
1881:
1880:
1879:
1878:
1877:cylinder sets
1860:
1849:
1838:
1835:is given the
1807:
1804:
1797:
1794:
1789:
1785:
1781:
1775:
1772:
1767:
1763:
1759:
1754:
1750:
1746:
1741:
1738:
1734:
1730:
1727:
1721:
1718:
1712:
1709:
1699:
1696:
1692:
1688:
1677:
1669:
1668:
1667:
1651:
1640:
1629:
1621:
1619:
1617:
1612:
1610:
1606:
1602:
1594:
1589:
1587:
1582:
1580:
1575:
1573:
1569:
1568:deterministic
1565:
1560:
1552:
1550:
1548:
1544:
1540:
1536:
1535:weakly mixing
1532:
1531:Chacon system
1528:
1524:
1520:
1516:
1512:
1508:
1505:Many chaotic
1500:
1498:
1496:
1492:
1487:
1479:
1471:
1469:
1467:
1463:
1455:
1446:
1444:
1436:
1431:
1413:
1408:
1405:
1402:
1398:
1394:
1389:
1378:
1372:
1361:
1360:
1359:
1354:
1335:
1331:
1322:
1319:
1316:
1313:
1310:
1303:
1300:
1297:
1293:
1287:
1283:
1278:
1274:
1271:
1268:
1263:
1259:
1255:
1249:
1246:
1241:
1237:
1233:
1228:
1224:
1220:
1215:
1212:
1208:
1204:
1201:
1194:
1190:
1185:
1173:
1172:
1171:
1169:
1159:
1155:
1126:
1122:
1113:
1110:
1107:
1104:
1101:
1094:
1091:
1088:
1084:
1078:
1074:
1069:
1065:
1062:
1059:
1054:
1050:
1046:
1040:
1037:
1032:
1028:
1024:
1019:
1015:
1007:
1003:
998:
993:
981:
980:
979:
976:
974:
970:
966:
960:
956:
950:
946:
938:
934:
930:
919:
915:
911:
901:
897:
882:
878:
874:
870:
862:
858:
854:
844:
820:
816:
812:
811:symbolic flow
808:
800:
789:
759:
732:
730:
726:
710:
707:
694:
690:
681:
675:
672:
650:
646:
625:
622:
619:
599:
596:
593:
584:
570:
567:
564:
544:
541:
538:
516:
512:
508:
503:
499:
495:
492:
470:
466:
462:
457:
453:
429:
425:
421:
418:
415:
411:
407:
404:
401:
397:
393:
387:
384:
362:
358:
354:
349:
345:
341:
338:
330:
321:
314:
312:
310:
294:
288:
279:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
179:
173:
167:
161:
152:
138:
135:
132:
129:
126:
123:
120:
117:
114:
111:
108:
105:
85:
82:
79:
76:
73:
61:
59:
57:
53:
49:
45:
41:
37:
33:
19:
3528:
3502:
3474:
3438:
3430:
3419:
3415:
3406:
3373:
3359:
3337:
3318:
3297:
3286:
3277:
3268:
3259:
3241:
3222:
3085:
2983:fixed points
2976:
2972:
2833:
2701:
2533:
2524:
2514:
2509:
2507:
2381:
2371:
2367:
2363:
2357:
2287:
2277:
2273:
2267:
2263:
2258:
2252:
2248:
2244:Markov chain
2239:
2229:
2213:-adic metric
2206:
2161:
2036:
1830:
1625:
1613:
1601:Ising models
1593:Potts models
1590:
1585:
1583:
1576:
1559:sofic system
1558:
1556:
1504:
1494:
1490:
1485:
1477:
1475:
1464:without the
1449:
1447:
1434:
1432:
1429:
1350:
1157:
1153:
1150:only if the
1141:
977:
972:
964:
958:
954:
948:
932:
928:
917:
913:
909:
899:
895:
880:
876:
872:
856:
852:
845:
814:
810:
793:. We endow
736:
727:
585:
326:
280:
153:
65:
56:shift spaces
35:
29:
3289:, Springer
2039:clopen sets
1609:Hamiltonian
1484:-shift. A
1472:Terminology
32:mathematics
3562:Categories
3551:1052.37003
3512:9810223986
3480:Providence
3462:1106.37301
3396:1014.11015
3330:References
2510:compatible
2197:Cantor set
2162:The space
2157:continuous
1435:transitive
933:admissible
929:admissible
733:Definition
3411:, (2000).
3251:0907.1858
3153:−
3136:−
3109:ζ
3063:−
3047:γ
3034:−
3020:γ
3016:∏
3000:ζ
2894:∞
2879:∑
2870:
2852:ζ
2801:
2765:∑
2755:π
2734:∑
2730:−
2722:μ
2667:−
2651:⋯
2605:π
2579:…
2547:μ
2522:whenever
2484:π
2458:π
2437:∑
2401:π
2397:∑
2387:≥ 0
2307:∑
2293:≥ 0
2112:countable
1987:…
1943:∈
1915:…
1808:∈
1802:∀
1795:∈
1776:…
1739:−
1728:…
1700:∈
1693:∏
1564:automaton
1323:∈
1269:∈
1250:…
1213:−
1202:…
1182:Σ
1114:∈
1060:∈
1041:…
990:Σ
973:two-sided
969:bilateral
965:one-sided
805:with the
797:with the
703:→
385:π
292:→
266:⋯
242:⋯
218:⋯
177:→
171:→
165:→
139:…
133:⋯
115:⋯
3472:(2012).
3364:, (2005)
3180:See also
2425:and has
2379:has all
2358:for all
2232:measures
1622:Topology
1537:but not
1501:Examples
1486:subshift
846:Now let
815:subshift
327:Given a
3201:Axiom A
2985:of the
2532:. The
2271:matrix
2226:Measure
2217:compact
2193:
2164:
2145:
2116:
2108:
2079:
2075:
2043:
1873:
1841:
1664:
1632:
1466:measure
943:be the
923:. Let
865:{0, 1}.
780:
751:
98:, like
3549:
3539:
3509:
3490:
3460:
3450:
3426:
3394:
3384:
3348:
3161:
3086:where
3071:
2973:where
2382:π
2372:π
2368:π
2362:. The
2203:Metric
1666:where
1529:, the
1525:, the
1454:-shift
850:be an
819:closed
3246:arXiv
3207:Notes
2261:, an
2151:is a
2110:is a
1478:shift
1450:full
885:with
817:is a
809:. A
3537:ISBN
3507:ISBN
3488:ISBN
3448:ISBN
3424:ISBN
3382:ISBN
3346:ISBN
2975:Fix(
2834:The
2702:The
2295:and
2255:, π)
1831:and
1607:and
1545:and
1351:The
937:walk
801:and
737:Let
46:and
3547:Zbl
3458:Zbl
3392:Zbl
3285:",
3127:det
3094:of
2908:Fix
2867:exp
2798:log
2530:= 0
2520:= 0
2370:= (
2276:= (
2041:in
1630:on
1562:an
1541:),
1517:of
1441:is
1437:if
921:= 1
903:in
875:= (
828:of
813:or
30:In
3564::
3545:.
3535:.
3486:.
3482::
3478:.
3456:.
3446:.
3442:.
3405:,
3390:.
3380:.
3344:.
3306:^
3244:,
3232:^
3215:^
3098::
2527:ij
2517:ij
2389:,
2290:ij
2280:ij
2266:Ă—
2222:.
2199:.
1618:.
1584:A
1581:.
1574:.
1557:A
1549:.
1513:,
1497:.
1468:.
1156:,
957:,
916:,
898:→
879:,
855:Ă—
843:.
583:.
34:,
3553:.
3515:.
3496:.
3464:.
3398:.
3354:.
3248::
3164:.
3156:1
3149:)
3145:)
3142:A
3139:z
3133:I
3130:(
3124:(
3121:=
3118:)
3115:z
3112:(
3096:z
3088:Îł
3066:1
3058:)
3051:|
3043:|
3038:z
3031:1
3027:(
3012:=
3009:)
3006:z
3003:(
2987:n
2979:)
2977:T
2958:,
2954:)
2948:n
2943:n
2939:z
2931:|
2926:)
2921:n
2917:T
2913:(
2901:|
2889:1
2886:=
2883:n
2874:(
2864:=
2861:)
2858:z
2855:(
2812:j
2809:i
2805:p
2793:j
2790:i
2786:p
2780:n
2775:1
2772:=
2769:j
2759:i
2749:n
2744:1
2741:=
2738:i
2727:=
2718:s
2683:s
2679:a
2675:,
2670:1
2664:s
2660:a
2655:p
2644:1
2640:a
2636:,
2631:0
2627:a
2622:p
2614:0
2610:a
2601:=
2598:)
2595:]
2590:s
2586:a
2582:,
2576:,
2571:0
2567:a
2563:[
2558:t
2554:C
2550:(
2525:A
2515:p
2493:.
2488:j
2480:=
2475:j
2472:i
2468:p
2462:i
2452:n
2447:1
2444:=
2441:i
2413:1
2410:=
2405:i
2384:i
2377:)
2374:i
2360:i
2343:1
2340:=
2335:j
2332:i
2328:p
2322:n
2317:1
2314:=
2311:j
2288:p
2283:)
2278:p
2274:P
2268:n
2264:n
2253:P
2251:(
2211:p
2178:Z
2173:V
2149:T
2130:Z
2125:V
2093:Z
2088:V
2063:.
2057:Z
2052:V
2022:}
2017:s
2013:a
2009:=
2004:s
2001:+
1998:t
1994:x
1990:,
1984:,
1979:0
1975:a
1971:=
1966:t
1962:x
1958::
1952:Z
1947:V
1940:x
1937:{
1934:=
1931:]
1926:s
1922:a
1918:,
1912:,
1907:0
1903:a
1899:[
1894:t
1890:C
1861:,
1855:Z
1850:V
1833:V
1816:}
1812:Z
1805:k
1798:V
1790:k
1786:x
1782::
1779:)
1773:,
1768:1
1764:x
1760:,
1755:0
1751:x
1747:,
1742:1
1735:x
1731:,
1725:(
1722:=
1719:x
1716:{
1713:=
1710:V
1704:Z
1697:n
1689:=
1683:Z
1678:V
1652:,
1646:Z
1641:V
1597:n
1595:(
1482:n
1458:n
1452:n
1439:G
1414:.
1409:1
1406:+
1403:j
1399:x
1395:=
1390:j
1386:)
1382:)
1379:x
1376:(
1373:T
1370:(
1356:T
1336:.
1332:}
1327:Z
1320:j
1317:,
1314:1
1311:=
1304:1
1301:+
1298:j
1294:x
1288:j
1284:x
1279:A
1275:,
1272:V
1264:j
1260:x
1256::
1253:)
1247:,
1242:1
1238:x
1234:,
1229:0
1225:x
1221:,
1216:1
1209:x
1205:,
1199:(
1195:{
1191:=
1186:A
1164:A
1160:)
1158:q
1154:p
1152:(
1148:q
1144:p
1127:.
1123:}
1118:N
1111:j
1108:,
1105:1
1102:=
1095:1
1092:+
1089:j
1085:x
1079:j
1075:x
1070:A
1066:,
1063:V
1055:j
1051:x
1047::
1044:)
1038:,
1033:1
1029:x
1025:,
1020:0
1016:x
1012:(
1008:{
1004:=
999:+
994:A
961:)
959:T
955:Y
953:(
941:T
925:Y
918:y
914:x
910:A
905:E
900:y
896:x
891:E
887:V
883:)
881:E
877:V
873:G
857:n
853:n
848:A
841:Y
836:Y
834:L
830:X
826:Y
822:T
803:X
795:V
791:T
784:V
765:Z
760:V
747:X
743:n
739:V
711:3
708:2
700:)
695:n
691:B
686:|
682:A
679:(
676:r
673:P
651:n
647:B
626:B
623:,
620:A
600:B
597:,
594:A
571:B
568:,
565:A
545:B
542:,
539:A
517:2
513:B
509:,
504:1
500:B
496:,
493:A
471:2
467:B
463:,
458:1
454:B
433:)
430:7
426:/
422:1
419:,
416:7
412:/
408:4
405:,
402:7
398:/
394:2
391:(
388:=
363:2
359:B
355:,
350:1
346:B
342:,
339:A
295:C
289:A
263:B
260:A
257:C
254:B
251:A
248:C
245:,
239:A
236:C
233:B
230:A
227:C
224:B
221:,
215:C
212:B
209:A
206:C
203:B
200:A
180:A
174:C
168:B
162:A
136:,
130:B
127:A
124:B
121:A
118:,
112:A
109:A
106:A
86:C
83:,
80:B
77:,
74:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
