2587:
2367:
3055:
4764:
6048:
5072:
2428:
197:
1791:
3556:
1281:
2243:
2238:
4393:
638:
2904:
4570:
1680:
4502:
2421:
6553:
5929:
4927:
2120:
2755:
4138:
1924:
3326:
3258:
769:
4071:
3922:
6643:
6332:
6251:
6192:
5468:
4920:
4430:
2679:
1853:
6367:
5277:
2582:{\displaystyle X_{F}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ \forall N\subset \mathbb {G} ,\forall g\in \mathbb {G} ,\ \left(\sigma ^{g}(\mathbf {x} )\right)_{N}=\mathbf {x} _{gN}\notin F\}.}
5228:
2850:
3865:
3801:
1556:
1133:
454:
6707:
219:
is a finite set, which is closed for the
Tychonov topology and invariant by translations. More generally one can define a shift space as the closed and translation-invariant subsets of
6501:
5104:
4796:
3972:
3831:
6991:
6939:
6557:
6426:
6290:
6465:
3133:
3105:
2707:
2158:
981:
666:
6764:
5186:
4543:
360:
3190:
1952:
1587:
6834:
6759:
6675:
5139:
as above, without to specify the index of where the words are forbidden, then we will just capture shift spaces which are invariant through the shift map, that is, such that
2801:
2001:
1882:
1623:
1487:
928:
879:
830:
801:
525:
246:
94:
3467:
3431:
6083:
5641:
5501:
5137:
4829:
955:
is countable, and, in any case, the base of this topology consists of a collection of open/closed sets (called cylinders), defined as follows: given a finite set of indices
5795:
5773:
5751:
5386:
5364:
5342:
4851:
4207:
4185:
4163:
3994:
3770:
3748:
3726:
3676:
3654:
3632:
953:
688:
567:
476:
322:
288:
5844:
3366:
1458:
1687:
1040:
6875:
4563:
2775:
5902:
5815:
5661:
5584:
3582:
3474:
3077:
2897:
1972:
1140:
89:
1315:
1007:
6794:
6608:
6585:
6114:
5689:
5413:
2877:
2616:
3395:
3162:
1388:
423:
7073:
6727:
6387:
6212:
6138:
5922:
5882:
5729:
5709:
5608:
5564:
5521:
5433:
5320:
5297:
4871:
4227:
4014:
3942:
3704:
3610:
2636:
2362:{\displaystyle {\mathcal {N}}_{A^{\mathbb {G} }}^{f}:=\bigcup _{k\in \mathbb {N} }{\mathcal {N}}_{k}=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }A^{N}}
1818:
1355:
1335:
1064:
899:
850:
708:
545:
496:
400:
380:
266:
217:
6563:
6117:
6086:
5668:
2163:
4234:
572:
3050:{\displaystyle W_{N}(\Lambda ):=\{(w_{i})_{i\in N}\in A^{N}:\ \exists \ \mathbf {x} \in \Lambda {\text{ s.t. }}x_{i}=w_{i}\ \forall i\in N\}.}
5538:
61:
7393:
Sobottka, M. (2022). "Some Notes on the
Classification of Shift Spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts".
4759:{\displaystyle W_{n}(\Lambda ):=\{((a_{i})_{i=0,..n}\in A^{n}:\ \exists \mathbf {x} \in \Lambda \ s.t.\ x_{i}=a_{i}\ \forall i=0,...,n\}.}
6085:. In this context of infinite alphabet, a sofic shift will be defined as the image of a shift of finite type under a particular class of
1628:
6043:{\displaystyle M_{F}:=\{g\in \mathbb {G} :\ \exists N\subset \mathbb {G} {\text{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},}
5067:{\displaystyle X_{F}=\{\mathbb {x} \in A^{\mathbb {Z} }:\ \forall i\in \mathbb {Z} ,\ \forall k\geq 0,\ (x_{i}...x_{i+k})\notin F\}.}
4437:
2375:
6506:
2006:
7290:
7147:
7112:
2712:
7263:. Weiss does not describe the origin of the word other than calling it a neologism; however, its Hebrew origin is stated by
4076:
1887:
3263:
3195:
713:
4019:
3870:
6613:
6302:
6217:
6162:
5438:
4876:
4400:
2649:
1823:
7339:
7309:
6337:
7172:"Some Notes on the Classification of Shift Spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts"
5233:
5191:
2806:
7451:
7364:
3836:
3775:
1492:
1069:
428:
6680:
6474:
5079:
4771:
3947:
3806:
6955:
6903:
6392:
6256:
6431:
6293:
3110:
3082:
2684:
2128:
958:
643:
5142:
4509:
5861:
word סופי meaning "finite", to refer to the fact that this is a generalization of a finiteness property.
331:
192:{\displaystyle A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}}
7446:
7441:
3167:
1929:
1564:
6810:
6732:
6648:
2780:
1977:
1858:
1599:
1463:
904:
855:
806:
777:
501:
222:
3996:
can be generated from the numbers {-1, 1}, it is sufficient to consider two shift maps given for all
3584:. In the general context stated here, the language of a shift space has not the same mean of that in
3436:
3400:
39:
7323:
6055:
5613:
5473:
5109:
4801:
1786:{\displaystyle \sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }}
57:
5778:
5756:
5734:
5369:
5347:
5325:
4834:
4190:
4168:
4146:
3977:
3753:
3731:
3709:
3659:
3637:
3615:
936:
671:
550:
459:
305:
271:
5820:
5532:
3551:{\displaystyle W(\Lambda ):=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }W_{N}(\Lambda )}
3331:
1396:
1276:{\displaystyle {\big }_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.}
1012:
6842:
5435:
is finite, which leads to classical definition of a shift of finite type as those shift spaces
4548:
3585:
2760:
5887:
5800:
5646:
5569:
3567:
3062:
2882:
1957:
74:
6468:
3867:
can be generated from the number 1, it is sufficient to consider a unique shift map given by
1288:
986:
7251:
7129:
6779:
6593:
6570:
6092:
5674:
5391:
2855:
2594:
3371:
3138:
1360:
8:
6729:-shift maps, i. e., maps which are generalized sliding block codes. The dynamical system
4229:), due to its algebraic structure, it is sufficient consider only cylinders in the form
2618:
is the set of all infinite patterns that do not contain any forbidden finite pattern of
405:
7420:
7402:
7381:
7328:
7255:
7209:
7183:
7171:
7058:
6772:
6712:
6372:
6197:
6123:
5907:
5867:
5714:
5694:
5593:
5549:
5506:
5418:
5305:
5282:
4856:
4212:
3999:
3927:
3689:
3595:
2621:
1803:
1340:
1320:
1049:
884:
835:
693:
530:
481:
385:
365:
251:
202:
7424:
7359:
7335:
7305:
7286:
7259:
7213:
7201:
7143:
7108:
6942:
6153:
6149:
2233:{\displaystyle {\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}}
48:
20:
7412:
7373:
7239:
7193:
7135:
5847:
4388:{\displaystyle :=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.}
7247:
5858:
43:
7416:
7227:
7197:
6994:
7139:
3686:
The classical framework for shift spaces consists of considering the alphabet
7435:
7355:
7205:
7011:
6894:
3678:
with the usual addition, the language of a shift space is a formal language.
6885:
is a sofic subshift, not of finite type. The set of all infinite words over
5884:
is infinite, it is possible to define shifts of finite type as shift spaces
633:{\displaystyle \mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }}
7319:
6893:
form blocks of prime length is not sofic (this can be shown by using the
6369:
are said to be topologically conjugate (or simply conjugate) if for each
3469:
contain the same configurations modulo translation. We will call the set
24:
7385:
7280:
7264:
7243:
6946:
832:
a
Hausdorff and totally disconnected topological space. In the case of
7016:
5531:
Among several types of shift spaces, the most widely studied are the
7377:
6677:, in symbolic dynamics it is usual to consider only continuous maps
7407:
7188:
7006:
36:
6804:
The first trivial example of shift space (of finite type) is the
5279:
it will be necessary to specify from which index on the words of
53:
7121:
7055:
for sets of infinite patterns that are just invariant under the
6143:
2369:. An equivalent way to define a shift space is to take a set of
1675:{\displaystyle \sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }}
7283:
Cellular automata and groups
Springer Monographs in Mathematics
7131:
Cellular automata and groups
Springer Monographs in Mathematics
7127:
4497:{\displaystyle W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),}
3772:) with the usual addition. In both cases, the identity element
325:
291:
4209:
with the usual addition (independently of the cardinality of
2416:{\displaystyle F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}}
6548:{\displaystyle \Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi }
6389:-shift map it follows that the topological dynamical systems
7079:
for those that are also closed for the prodiscrete topology.
7299:
2115:{\displaystyle {\big }_{\Lambda }:={\big }\cap \Lambda }
7134:. Springer Monographs in Mathematics. Springer Verlag.
3750:) with the usual addition, or the set of all integers (
2750:{\displaystyle W_{\emptyset }(\Lambda ):=\{\epsilon \}}
7230:(1973), "Subshifts of finite type and sofic systems",
4133:{\displaystyle \sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}}
7061:
6958:
6906:
6845:
6813:
6782:
6735:
6715:
6683:
6651:
6645:
to itself will define a topological dynamical system
6616:
6596:
6573:
6509:
6477:
6434:
6395:
6375:
6340:
6305:
6259:
6220:
6200:
6165:
6126:
6095:
6058:
5932:
5910:
5890:
5870:
5823:
5803:
5781:
5759:
5737:
5717:
5697:
5677:
5649:
5616:
5596:
5572:
5552:
5509:
5476:
5441:
5421:
5394:
5372:
5350:
5328:
5308:
5285:
5236:
5194:
5145:
5112:
5082:
4930:
4879:
4859:
4837:
4804:
4774:
4573:
4551:
4512:
4440:
4403:
4237:
4215:
4193:
4171:
4149:
4079:
4022:
4002:
3980:
3950:
3930:
3873:
3839:
3809:
3778:
3756:
3734:
3712:
3692:
3662:
3640:
3618:
3598:
3570:
3477:
3439:
3403:
3374:
3334:
3266:
3198:
3170:
3141:
3113:
3085:
3065:
2907:
2885:
2858:
2809:
2783:
2763:
2715:
2687:
2652:
2624:
2597:
2431:
2378:
2246:
2166:
2131:
2009:
1980:
1960:
1932:
1919:{\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda }
1890:
1861:
1826:
1806:
1690:
1631:
1602:
1567:
1495:
1466:
1399:
1363:
1343:
1323:
1291:
1143:
1072:
1052:
1015:
989:
961:
939:
907:
887:
858:
838:
809:
780:
716:
696:
674:
646:
575:
553:
533:
504:
498:(an alphabet) with the discrete topology, and define
484:
462:
431:
408:
388:
368:
334:
308:
274:
254:
225:
205:
97:
77:
803:, we consider the prodiscrete topology, which makes
5667:if it is the image of a shift of finite type under
3321:{\displaystyle (v_{i})_{i\in N}\in W_{N}(\Lambda )}
3253:{\displaystyle (w_{j})_{j\in M}\in W_{M}(\Lambda )}
7327:
7281:Ceccherini-Silberstein, T.; Coornaert, M. (2010).
7128:Ceccherini-Silberstein, T.; Coornaert, M. (2010).
7067:
6985:
6933:
6869:
6828:
6788:
6753:
6721:
6701:
6669:
6637:
6602:
6579:
6547:
6495:
6459:
6420:
6381:
6361:
6326:
6284:
6245:
6206:
6186:
6132:
6108:
6077:
6042:
5916:
5896:
5876:
5838:
5809:
5789:
5767:
5745:
5723:
5703:
5683:
5655:
5635:
5602:
5590:if we can take a finite set of forbidden patterns
5578:
5558:
5515:
5495:
5462:
5427:
5407:
5380:
5358:
5336:
5314:
5291:
5271:
5222:
5180:
5131:
5098:
5066:
4914:
4865:
4845:
4823:
4790:
4758:
4557:
4537:
4496:
4424:
4387:
4221:
4201:
4179:
4157:
4132:
4065:
4008:
3988:
3966:
3936:
3916:
3859:
3825:
3795:
3764:
3742:
3720:
3698:
3670:
3648:
3626:
3604:
3576:
3550:
3461:
3425:
3389:
3360:
3320:
3252:
3184:
3156:
3127:
3099:
3071:
3049:
2891:
2871:
2844:
2795:
2769:
2749:
2701:
2673:
2630:
2610:
2581:
2415:
2361:
2232:
2152:
2114:
1995:
1966:
1946:
1918:
1876:
1847:
1812:
1785:
1674:
1617:
1581:
1550:
1481:
1460:is the set of all set of all infinite patterns of
1452:
1382:
1349:
1329:
1309:
1275:
1127:
1058:
1034:
1001:
975:
947:
922:
893:
873:
844:
824:
795:
764:{\displaystyle \mathbf {x} _{N}:=(x_{i})_{i\in N}}
763:
702:
682:
660:
632:
561:
539:
519:
490:
470:
448:
417:
394:
374:
354:
316:
282:
260:
240:
211:
191:
83:
6952:The bi-infinite space of strings in two letters,
4066:{\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}
3917:{\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}
7433:
6638:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
6327:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
6246:{\displaystyle \sigma ^{g}:\Lambda \to \Lambda }
6187:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
5463:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
4915:{\displaystyle F\subset \bigcup _{n\geq 1}A^{n}}
4425:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
2674:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
1848:{\displaystyle \Lambda \subset A^{\mathbb {G} }}
933:This topology will be metrizable if and only if
7302:An Introduction to Symbolic Dynamics and Coding
7105:An introduction to symbolic dynamics and coding
6997:, or rather is homomorphic to the Baker's map.
6362:{\displaystyle \Gamma \subset B^{\mathbb {G} }}
3803:corresponds to the number 0. Furthermore, when
56:. The most widely studied shift spaces are the
7395:Bulletin of the Brazilian Mathematical Society
7176:Bulletin of the Brazilian Mathematical Society
6900:The space of infinite strings in two letters,
5272:{\displaystyle \sigma (X_{F})\subsetneq X_{F}}
6144:Topological dynamical systems on shift spaces
5526:
5302:In particular, in the classical framework of
5223:{\displaystyle X_{F}\subset A^{\mathbb {N} }}
2101:
2065:
2049:
2012:
2003:, which has as basic open sets the cylinders
1741:
1703:
1439:
1402:
1183:
1146:
7354:
7334:. Cambridge UK: Cambridge University Press.
7304:. Cambridge UK: Cambridge University Press.
6972:
6959:
6920:
6907:
6864:
6852:
6471:, that is, if there exists a continuous map
6034:
5946:
5058:
4944:
4873:are defined, that is, we can just consider
4768:In the same way, for the particular case of
4750:
4596:
4532:
4526:
4379:
4286:
3854:
3848:
3041:
2930:
2845:{\displaystyle W_{N}(\Lambda )\subset A^{N}}
2744:
2738:
2573:
2445:
1304:
1298:
1267:
1197:
186:
113:
3860:{\displaystyle \mathbb {N} \setminus \{0\}}
3796:{\displaystyle \mathbf {1} _{\mathbb {G} }}
2852:be the set of all finite configurations of
1551:{\displaystyle (a_{i})_{i\in D}\in A^{|D|}}
1317:, we denote the cylinder fixing the symbol
1128:{\displaystyle (a_{i})_{i\in D}\in A^{|D|}}
449:{\displaystyle \mathbf {1} _{\mathbb {G} }}
7102:
6702:{\displaystyle \Phi :\Lambda \to \Lambda }
4798:, it follows that to define a shift space
2641:
7406:
7187:
7107:. Cambridge: Cambridge University press.
6977:
6925:
6820:
6629:
6496:{\displaystyle \Phi :\Lambda \to \Gamma }
6353:
6318:
6178:
5976:
5956:
5783:
5761:
5739:
5691:that is continuous and invariant for all
5454:
5388:with the usual addition, it follows that
5374:
5352:
5330:
5214:
5099:{\displaystyle \mathbb {G} =\mathbb {N} }
5092:
5084:
4983:
4961:
4948:
4839:
4791:{\displaystyle \mathbb {G} =\mathbb {Z} }
4784:
4776:
4416:
4397:Moreover, the language of a shift space
4314:
4195:
4173:
4151:
3982:
3967:{\displaystyle \mathbb {G} =\mathbb {Z} }
3960:
3952:
3841:
3826:{\displaystyle \mathbb {G} =\mathbb {N} }
3819:
3811:
3787:
3758:
3736:
3714:
3664:
3642:
3620:
3507:
3178:
3121:
3093:
2695:
2665:
2501:
2484:
2462:
2400:
2327:
2290:
2262:
2198:
2140:
1987:
1940:
1868:
1839:
1777:
1733:
1666:
1651:
1609:
1575:
1473:
1214:
969:
941:
914:
865:
816:
787:
654:
624:
609:
555:
511:
464:
440:
348:
310:
276:
232:
182:
141:
104:
7392:
7318:
7169:
7103:Lind, Douglas A.; Marcus, Brian (1995).
5797:with the usual addition, then the shift
3589:
1884:and invariant under translations, i.e.,
68:
4831:we do not need to specify the index of
7434:
7047:. However, some authors use the terms
6986:{\displaystyle \{0,1\}^{\mathbb {Z} }}
6934:{\displaystyle \{0,1\}^{\mathbb {N} }}
6421:{\displaystyle (\Lambda ,\sigma ^{g})}
6285:{\displaystyle (\Lambda ,\sigma ^{g})}
3681:
7300:Lind, Douglas; Marcus, Brian (1995).
7226:
6877:. The set of all infinite words over
6460:{\displaystyle (\Gamma ,\sigma ^{g})}
5854:
3944:. On the other hand, for the case of
3728:as the set of non-negative integers (
3128:{\displaystyle N\subset \mathbb {G} }
3100:{\displaystyle M\subset \mathbb {G} }
2702:{\displaystyle N\subset \mathbb {G} }
2153:{\displaystyle k\in \mathbb {N} ^{*}}
1855:that is closed under the topology of
976:{\displaystyle D\subset \mathbb {G} }
661:{\displaystyle N\subset \mathbb {G} }
7170:Sobottka, Marcelo (September 2022).
7165:
7163:
7161:
7159:
7098:
7096:
5181:{\displaystyle \sigma (X_{F})=X_{F}}
4538:{\displaystyle W_{0}:=\{\epsilon \}}
2423:and define a shift space as the set
6120:, are trivially satisfied whenever
5188:. In fact, to define a shift space
2777:stands for the empty word, and for
355:{\displaystyle g,h\in \mathbb {G} }
13:
7274:
7075:-shift maps, and reserve the term
6783:
6745:
6739:
6696:
6690:
6684:
6661:
6655:
6617:
6597:
6574:
6542:
6510:
6490:
6484:
6478:
6438:
6399:
6341:
6306:
6263:
6240:
6234:
6166:
6116:and the additional conditions the
6059:
5966:
5891:
5830:
5804:
5678:
5650:
5617:
5573:
5477:
5442:
5113:
4993:
4973:
4805:
4720:
4673:
4662:
4587:
4485:
4447:
4404:
4352:
3571:
3542:
3522:
3513:
3498:
3484:
3453:
3417:
3312:
3244:
3066:
3029:
2995:
2981:
2921:
2886:
2823:
2790:
2729:
2721:
2653:
2491:
2474:
2388:
2342:
2333:
2318:
2299:
2250:
2204:
2189:
2170:
2109:
2055:
1961:
1913:
1904:
1827:
1255:
172:
78:
42:that represent the evolution of a
14:
7463:
7156:
7093:
3845:
3185:{\displaystyle g\in \mathbb {G} }
1954:. We consider in the shift space
1947:{\displaystyle g\in \mathbb {G} }
1582:{\displaystyle g\in \mathbb {G} }
1489:which contain the finite pattern
7330:Algebraic Combinatorics on Words
6829:{\displaystyle A^{\mathbb {N} }}
6754:{\displaystyle (\Lambda ,\Phi )}
6670:{\displaystyle (\Lambda ,\Phi )}
5817:is a sofic shift if and only if
4853:on which the forbidden words of
4666:
4097:
4030:
3881:
3781:
2988:
2879:that appear in some sequence of
2796:{\displaystyle N\neq \emptyset }
2554:
2531:
2449:
1996:{\displaystyle A^{\mathbb {G} }}
1877:{\displaystyle A^{\mathbb {G} }}
1618:{\displaystyle A^{\mathbb {G} }}
1482:{\displaystyle A^{\mathbb {G} }}
1201:
923:{\displaystyle A^{\mathbb {G} }}
874:{\displaystyle A^{\mathbb {G} }}
825:{\displaystyle A^{\mathbb {G} }}
796:{\displaystyle A^{\mathbb {G} }}
719:
676:
577:
527:as the set of all patterns over
520:{\displaystyle A^{\mathbb {G} }}
434:
241:{\displaystyle A^{\mathbb {G} }}
7365:American Journal of Mathematics
6558:generalized sliding block codes
5853:The name "sofic" was coined by
4565:stands for the empty word, and
3462:{\displaystyle W_{N}(\Lambda )}
3426:{\displaystyle W_{M}(\Lambda )}
668:, we denote the restriction of
7220:
7029:
6765:generalized cellular automaton
6748:
6736:
6693:
6664:
6652:
6487:
6454:
6435:
6415:
6396:
6279:
6260:
6237:
6078:{\displaystyle \Lambda =X_{F}}
6013:
5999:
5833:
5827:
5636:{\displaystyle \Lambda =X_{F}}
5546:In the case when the alphabet
5496:{\displaystyle \Lambda =X_{F}}
5253:
5240:
5162:
5149:
5132:{\displaystyle \Lambda =X_{F}}
5049:
5011:
4824:{\displaystyle \Lambda =X_{F}}
4616:
4602:
4599:
4590:
4584:
4488:
4482:
4450:
4444:
4303:
4289:
4280:
4238:
4102:
4093:
4035:
4026:
3886:
3877:
3545:
3539:
3487:
3481:
3456:
3450:
3420:
3414:
3315:
3309:
3281:
3267:
3247:
3241:
3213:
3199:
2947:
2933:
2924:
2918:
2826:
2820:
2732:
2726:
2535:
2527:
2084:
2070:
2031:
2017:
1907:
1901:
1766:
1749:
1722:
1708:
1657:
1542:
1534:
1510:
1496:
1421:
1407:
1371:
1364:
1165:
1151:
1119:
1111:
1087:
1073:
852:being finite, it follows that
746:
732:
598:
584:
130:
116:
1:
7362:(1938). "Symbolic Dynamics".
7086:
5924:of forbidden words such that
5904:for those one can take a set
5106:, if we define a shift space
3592:which considers the alphabet
930:is not even locally compact.
297:
7022:
6590:Although any continuous map
6294:topological dynamical system
5790:{\displaystyle \mathbb {Z} }
5768:{\displaystyle \mathbb {N} }
5746:{\displaystyle \mathbb {G} }
5381:{\displaystyle \mathbb {Z} }
5359:{\displaystyle \mathbb {N} }
5337:{\displaystyle \mathbb {G} }
4846:{\displaystyle \mathbb {G} }
4202:{\displaystyle \mathbb {Z} }
4180:{\displaystyle \mathbb {N} }
4158:{\displaystyle \mathbb {G} }
3989:{\displaystyle \mathbb {Z} }
3765:{\displaystyle \mathbb {Z} }
3743:{\displaystyle \mathbb {N} }
3721:{\displaystyle \mathbb {G} }
3671:{\displaystyle \mathbb {Z} }
3649:{\displaystyle \mathbb {N} }
3627:{\displaystyle \mathbb {G} }
3260:if and only if there exists
2681:and a finite set of indices
948:{\displaystyle \mathbb {G} }
683:{\displaystyle \mathbf {x} }
562:{\displaystyle \mathbb {G} }
471:{\displaystyle \mathbb {G} }
317:{\displaystyle \mathbb {G} }
283:{\displaystyle \mathbb {G} }
71:a shift space is any subset
46:. In fact, shift spaces and
7:
7324:"Finite and Infinite Words"
7035:It is common to refer to a
7000:
6945:. It is isomorphic to the
6799:
5839:{\displaystyle W(\Lambda )}
3361:{\displaystyle w_{j}=v_{i}}
2591:Intuitively, a shift space
1453:{\displaystyle {\big }_{D}}
1393:In other words, a cylinder
478:. Consider a non-empty set
10:
7468:
7417:10.1007/s00574-022-00292-x
7198:10.1007/s00574-022-00292-x
7039:using just the expression
6796:is uniformly continuous).
6154:symbolic dynamical systems
6089:. Both, the finiteness of
5527:Some types of shift spaces
1974:the induced topology from
1035:{\displaystyle a_{i}\in A}
362:, denote the operation of
49:symbolic dynamical systems
7140:10.1007/978-3-642-14034-1
6993:is commonly known as the
6870:{\displaystyle A=\{a,b\}}
6587:is uniformly continuous.
6555:. Such maps are known as
6253:it follows that the pair
5566:is finite, a shift space
5415:is finite if and only if
4558:{\displaystyle \epsilon }
2770:{\displaystyle \epsilon }
268:is any non-empty set and
5897:{\displaystyle \Lambda }
5810:{\displaystyle \Lambda }
5656:{\displaystyle \Lambda }
5579:{\displaystyle \Lambda }
3577:{\displaystyle \Lambda }
3072:{\displaystyle \Lambda }
2892:{\displaystyle \Lambda }
1967:{\displaystyle \Lambda }
1337:at the entry indexed by
881:is compact. However, if
84:{\displaystyle \Lambda }
58:subshifts of finite type
23:and related branches of
6881:containing at most one
6709:which commute with all
6469:topologically conjugate
2642:Language of shift space
1310:{\displaystyle D=\{g\}}
456:denote the identity of
7452:Combinatorics on words
7069:
6987:
6935:
6871:
6830:
6790:
6755:
6723:
6703:
6671:
6639:
6604:
6581:
6549:
6497:
6461:
6422:
6383:
6363:
6328:
6286:
6247:
6208:
6188:
6134:
6110:
6079:
6044:
5918:
5898:
5878:
5840:
5811:
5791:
5769:
5747:
5725:
5705:
5685:
5657:
5637:
5604:
5580:
5560:
5517:
5497:
5464:
5429:
5409:
5382:
5360:
5338:
5316:
5293:
5273:
5224:
5182:
5133:
5100:
5068:
4916:
4867:
4847:
4825:
4792:
4760:
4559:
4539:
4498:
4426:
4389:
4223:
4203:
4181:
4159:
4143:Furthermore, whenever
4134:
4067:
4010:
3990:
3968:
3938:
3918:
3861:
3827:
3797:
3766:
3744:
3722:
3700:
3672:
3650:
3628:
3606:
3586:Formal Language Theory
3578:
3552:
3463:
3427:
3391:
3362:
3322:
3254:
3186:
3158:
3129:
3101:
3073:
3051:
2893:
2873:
2846:
2797:
2771:
2751:
2703:
2675:
2632:
2612:
2583:
2417:
2363:
2234:
2154:
2116:
1997:
1968:
1948:
1920:
1878:
1849:
1814:
1787:
1676:
1619:
1583:
1552:
1483:
1454:
1384:
1351:
1331:
1311:
1277:
1129:
1060:
1036:
1003:
1002:{\displaystyle i\in D}
977:
949:
924:
895:
875:
846:
826:
797:
765:
704:
684:
662:
634:
563:
541:
521:
492:
472:
450:
419:
396:
376:
356:
318:
284:
262:
242:
213:
193:
85:
7267:reviewer R. L. Adler.
7070:
6988:
6936:
6872:
6831:
6791:
6789:{\displaystyle \Phi }
6756:
6724:
6704:
6672:
6640:
6605:
6603:{\displaystyle \Phi }
6582:
6580:{\displaystyle \Phi }
6550:
6498:
6462:
6423:
6384:
6364:
6329:
6287:
6248:
6209:
6189:
6156:are usually defined.
6148:Shift spaces are the
6135:
6111:
6109:{\displaystyle M_{F}}
6080:
6045:
5919:
5899:
5879:
5841:
5812:
5792:
5770:
5748:
5726:
5706:
5686:
5684:{\displaystyle \Phi }
5658:
5638:
5605:
5581:
5561:
5534:shifts of finite type
5518:
5498:
5465:
5430:
5410:
5408:{\displaystyle M_{F}}
5383:
5361:
5339:
5317:
5294:
5274:
5225:
5183:
5134:
5101:
5069:
4917:
4868:
4848:
4826:
4793:
4761:
4560:
4540:
4499:
4427:
4390:
4224:
4204:
4182:
4160:
4135:
4068:
4011:
3991:
3969:
3939:
3919:
3862:
3828:
3798:
3767:
3745:
3723:
3701:
3673:
3651:
3629:
3607:
3579:
3553:
3464:
3428:
3392:
3363:
3323:
3255:
3187:
3159:
3130:
3102:
3079:is a shift space, if
3074:
3052:
2894:
2874:
2872:{\displaystyle A^{N}}
2847:
2798:
2772:
2752:
2704:
2676:
2633:
2613:
2611:{\displaystyle X_{F}}
2584:
2418:
2364:
2235:
2155:
2117:
1998:
1969:
1949:
1921:
1879:
1850:
1815:
1788:
1677:
1620:
1584:
1553:
1484:
1455:
1385:
1352:
1332:
1312:
1278:
1130:
1061:
1037:
1004:
978:
950:
925:
896:
876:
847:
827:
798:
766:
705:
685:
663:
635:
564:
542:
522:
493:
473:
451:
420:
397:
377:
357:
319:
285:
263:
243:
214:
194:
86:
52:are often considered
16:Set of infinite words
7059:
6956:
6904:
6843:
6811:
6780:
6733:
6713:
6681:
6649:
6614:
6594:
6571:
6507:
6475:
6432:
6393:
6373:
6338:
6303:
6257:
6218:
6198:
6163:
6159:Given a shift space
6124:
6093:
6056:
5930:
5908:
5888:
5868:
5821:
5801:
5779:
5757:
5735:
5715:
5695:
5675:
5647:
5614:
5594:
5588:shift of finite type
5570:
5550:
5507:
5474:
5439:
5419:
5392:
5370:
5348:
5326:
5306:
5283:
5234:
5192:
5143:
5110:
5080:
4928:
4877:
4857:
4835:
4802:
4772:
4571:
4549:
4510:
4438:
4401:
4235:
4213:
4191:
4169:
4147:
4077:
4020:
4000:
3978:
3948:
3928:
3871:
3837:
3807:
3776:
3754:
3732:
3710:
3690:
3660:
3638:
3616:
3596:
3568:
3475:
3437:
3401:
3390:{\displaystyle j=gi}
3372:
3332:
3264:
3196:
3168:
3157:{\displaystyle M=gN}
3139:
3111:
3107:is a translation of
3083:
3063:
2905:
2883:
2856:
2807:
2781:
2761:
2713:
2685:
2650:
2646:Given a shift space
2622:
2595:
2429:
2376:
2244:
2164:
2129:
2007:
1978:
1958:
1930:
1888:
1859:
1824:
1804:
1688:
1629:
1600:
1565:
1493:
1464:
1397:
1383:{\displaystyle _{g}}
1361:
1341:
1321:
1289:
1141:
1070:
1050:
1013:
987:
959:
937:
905:
901:is not finite, then
885:
856:
836:
807:
778:
714:
694:
672:
644:
573:
551:
531:
502:
482:
460:
429:
406:
386:
366:
332:
306:
272:
252:
223:
203:
95:
75:
7285:. Springer Verlag.
6564:sliding block codes
6118:sliding block codes
6087:sliding block codes
3682:Classical framework
3590:classical framework
2412:
2274:
69:classical framework
7360:Hedlund, Gustav A.
7244:10.1007/bf01295322
7065:
6983:
6931:
6867:
6826:
6786:
6773:cellular automaton
6751:
6719:
6699:
6667:
6635:
6600:
6577:
6545:
6493:
6457:
6418:
6379:
6359:
6324:
6282:
6243:
6204:
6184:
6150:topological spaces
6130:
6106:
6075:
6040:
5914:
5894:
5874:
5836:
5807:
5787:
5765:
5743:
5721:
5711:-shift maps ). If
5701:
5681:
5669:sliding block code
5653:
5633:
5600:
5576:
5556:
5513:
5493:
5460:
5425:
5405:
5378:
5356:
5334:
5322:being finite, and
5312:
5289:
5269:
5220:
5178:
5129:
5096:
5064:
4912:
4901:
4863:
4843:
4821:
4788:
4756:
4555:
4535:
4494:
4471:
4422:
4385:
4219:
4199:
4177:
4155:
4130:
4063:
4006:
3986:
3964:
3934:
3914:
3857:
3823:
3793:
3762:
3740:
3718:
3696:
3668:
3646:
3624:
3612:being finite, and
3602:
3574:
3548:
3528:
3459:
3423:
3397:. In other words,
3387:
3358:
3318:
3250:
3182:
3154:
3125:
3097:
3069:
3047:
2889:
2869:
2842:
2793:
2767:
2747:
2699:
2671:
2628:
2608:
2579:
2413:
2385:
2371:forbidden patterns
2359:
2348:
2295:
2247:
2230:
2219:
2150:
2112:
1993:
1964:
1944:
1916:
1874:
1845:
1810:
1800:over the alphabet
1783:
1672:
1615:
1579:
1548:
1479:
1450:
1380:
1347:
1327:
1307:
1273:
1125:
1056:
1032:
999:
973:
945:
920:
891:
871:
842:
822:
793:
761:
700:
690:to the indices of
680:
658:
630:
559:
537:
517:
488:
468:
446:
418:{\displaystyle gh}
415:
392:
372:
352:
314:
280:
258:
238:
209:
189:
81:
7447:Dynamical systems
7442:Symbolic dynamics
7292:978-3-642-14034-1
7149:978-3-642-14033-4
7114:978-0-521-55900-3
7068:{\displaystyle g}
6943:Bernoulli process
6722:{\displaystyle g}
6382:{\displaystyle g}
6299:Two shift spaces
6207:{\displaystyle g}
6133:{\displaystyle A}
5997:
5983:
5965:
5917:{\displaystyle F}
5877:{\displaystyle A}
5724:{\displaystyle A}
5704:{\displaystyle g}
5603:{\displaystyle F}
5559:{\displaystyle A}
5516:{\displaystyle F}
5428:{\displaystyle F}
5315:{\displaystyle A}
5292:{\displaystyle F}
5010:
4992:
4972:
4886:
4866:{\displaystyle F}
4719:
4693:
4678:
4661:
4456:
4432:will be given by
4351:
4325:
4222:{\displaystyle A}
4009:{\displaystyle n}
3937:{\displaystyle n}
3699:{\displaystyle A}
3605:{\displaystyle A}
3526:
3493:
3059:Note that, since
3028:
3001:
2986:
2980:
2631:{\displaystyle F}
2510:
2473:
2346:
2313:
2278:
2217:
2184:
1813:{\displaystyle A}
1350:{\displaystyle g}
1330:{\displaystyle b}
1254:
1225:
1059:{\displaystyle D}
894:{\displaystyle A}
845:{\displaystyle A}
703:{\displaystyle N}
540:{\displaystyle A}
491:{\displaystyle A}
395:{\displaystyle h}
375:{\displaystyle g}
261:{\displaystyle A}
212:{\displaystyle A}
171:
152:
21:symbolic dynamics
7459:
7428:
7410:
7389:
7351:
7349:
7348:
7333:
7315:
7296:
7268:
7262:
7224:
7218:
7217:
7191:
7167:
7154:
7153:
7125:
7119:
7118:
7100:
7080:
7074:
7072:
7071:
7066:
7033:
6992:
6990:
6989:
6984:
6982:
6981:
6980:
6940:
6938:
6937:
6932:
6930:
6929:
6928:
6876:
6874:
6873:
6868:
6835:
6833:
6832:
6827:
6825:
6824:
6823:
6795:
6793:
6792:
6787:
6760:
6758:
6757:
6752:
6728:
6726:
6725:
6720:
6708:
6706:
6705:
6700:
6676:
6674:
6673:
6668:
6644:
6642:
6641:
6636:
6634:
6633:
6632:
6609:
6607:
6606:
6601:
6586:
6584:
6583:
6578:
6554:
6552:
6551:
6546:
6538:
6537:
6525:
6524:
6502:
6500:
6499:
6494:
6466:
6464:
6463:
6458:
6453:
6452:
6427:
6425:
6424:
6419:
6414:
6413:
6388:
6386:
6385:
6380:
6368:
6366:
6365:
6360:
6358:
6357:
6356:
6333:
6331:
6330:
6325:
6323:
6322:
6321:
6291:
6289:
6288:
6283:
6278:
6277:
6252:
6250:
6249:
6244:
6230:
6229:
6213:
6211:
6210:
6205:
6193:
6191:
6190:
6185:
6183:
6182:
6181:
6139:
6137:
6136:
6131:
6115:
6113:
6112:
6107:
6105:
6104:
6084:
6082:
6081:
6076:
6074:
6073:
6049:
6047:
6046:
6041:
6027:
6026:
6011:
6010:
5998:
5995:
5984:
5982: s.t.
5981:
5979:
5963:
5959:
5942:
5941:
5923:
5921:
5920:
5915:
5903:
5901:
5900:
5895:
5883:
5881:
5880:
5875:
5848:regular language
5845:
5843:
5842:
5837:
5816:
5814:
5813:
5808:
5796:
5794:
5793:
5788:
5786:
5774:
5772:
5771:
5766:
5764:
5752:
5750:
5749:
5744:
5742:
5730:
5728:
5727:
5722:
5710:
5708:
5707:
5702:
5690:
5688:
5687:
5682:
5671:(that is, a map
5662:
5660:
5659:
5654:
5642:
5640:
5639:
5634:
5632:
5631:
5609:
5607:
5606:
5601:
5585:
5583:
5582:
5577:
5565:
5563:
5562:
5557:
5522:
5520:
5519:
5514:
5503:for some finite
5502:
5500:
5499:
5494:
5492:
5491:
5469:
5467:
5466:
5461:
5459:
5458:
5457:
5434:
5432:
5431:
5426:
5414:
5412:
5411:
5406:
5404:
5403:
5387:
5385:
5384:
5379:
5377:
5365:
5363:
5362:
5357:
5355:
5343:
5341:
5340:
5335:
5333:
5321:
5319:
5318:
5313:
5298:
5296:
5295:
5290:
5278:
5276:
5275:
5270:
5268:
5267:
5252:
5251:
5229:
5227:
5226:
5221:
5219:
5218:
5217:
5204:
5203:
5187:
5185:
5184:
5179:
5177:
5176:
5161:
5160:
5138:
5136:
5135:
5130:
5128:
5127:
5105:
5103:
5102:
5097:
5095:
5087:
5073:
5071:
5070:
5065:
5048:
5047:
5023:
5022:
5008:
4990:
4986:
4970:
4966:
4965:
4964:
4951:
4940:
4939:
4921:
4919:
4918:
4913:
4911:
4910:
4900:
4872:
4870:
4869:
4864:
4852:
4850:
4849:
4844:
4842:
4830:
4828:
4827:
4822:
4820:
4819:
4797:
4795:
4794:
4789:
4787:
4779:
4765:
4763:
4762:
4757:
4717:
4716:
4715:
4703:
4702:
4691:
4676:
4669:
4659:
4655:
4654:
4642:
4641:
4614:
4613:
4583:
4582:
4564:
4562:
4561:
4556:
4544:
4542:
4541:
4536:
4522:
4521:
4503:
4501:
4500:
4495:
4481:
4480:
4470:
4431:
4429:
4428:
4423:
4421:
4420:
4419:
4394:
4392:
4391:
4386:
4349:
4348:
4347:
4335:
4334:
4323:
4319:
4318:
4317:
4301:
4300:
4279:
4278:
4260:
4259:
4250:
4249:
4228:
4226:
4225:
4220:
4208:
4206:
4205:
4200:
4198:
4186:
4184:
4183:
4178:
4176:
4164:
4162:
4161:
4156:
4154:
4139:
4137:
4136:
4131:
4129:
4128:
4110:
4109:
4100:
4092:
4091:
4072:
4070:
4069:
4064:
4062:
4061:
4043:
4042:
4033:
4015:
4013:
4012:
4007:
3995:
3993:
3992:
3987:
3985:
3973:
3971:
3970:
3965:
3963:
3955:
3943:
3941:
3940:
3935:
3923:
3921:
3920:
3915:
3913:
3912:
3894:
3893:
3884:
3866:
3864:
3863:
3858:
3844:
3832:
3830:
3829:
3824:
3822:
3814:
3802:
3800:
3799:
3794:
3792:
3791:
3790:
3784:
3771:
3769:
3768:
3763:
3761:
3749:
3747:
3746:
3741:
3739:
3727:
3725:
3724:
3719:
3717:
3705:
3703:
3702:
3697:
3677:
3675:
3674:
3669:
3667:
3655:
3653:
3652:
3647:
3645:
3633:
3631:
3630:
3625:
3623:
3611:
3609:
3608:
3603:
3583:
3581:
3580:
3575:
3557:
3555:
3554:
3549:
3538:
3537:
3527:
3525:
3511:
3510:
3468:
3466:
3465:
3460:
3449:
3448:
3432:
3430:
3429:
3424:
3413:
3412:
3396:
3394:
3393:
3388:
3367:
3365:
3364:
3359:
3357:
3356:
3344:
3343:
3327:
3325:
3324:
3319:
3308:
3307:
3295:
3294:
3279:
3278:
3259:
3257:
3256:
3251:
3240:
3239:
3227:
3226:
3211:
3210:
3191:
3189:
3188:
3183:
3181:
3163:
3161:
3160:
3155:
3134:
3132:
3131:
3126:
3124:
3106:
3104:
3103:
3098:
3096:
3078:
3076:
3075:
3070:
3056:
3054:
3053:
3048:
3026:
3025:
3024:
3012:
3011:
3002:
3000: s.t.
2999:
2991:
2984:
2978:
2974:
2973:
2961:
2960:
2945:
2944:
2917:
2916:
2898:
2896:
2895:
2890:
2878:
2876:
2875:
2870:
2868:
2867:
2851:
2849:
2848:
2843:
2841:
2840:
2819:
2818:
2802:
2800:
2799:
2794:
2776:
2774:
2773:
2768:
2756:
2754:
2753:
2748:
2725:
2724:
2708:
2706:
2705:
2700:
2698:
2680:
2678:
2677:
2672:
2670:
2669:
2668:
2637:
2635:
2634:
2629:
2617:
2615:
2614:
2609:
2607:
2606:
2588:
2586:
2585:
2580:
2566:
2565:
2557:
2548:
2547:
2542:
2538:
2534:
2526:
2525:
2508:
2504:
2487:
2471:
2467:
2466:
2465:
2452:
2441:
2440:
2422:
2420:
2419:
2414:
2411:
2406:
2405:
2404:
2403:
2392:
2391:
2368:
2366:
2365:
2360:
2358:
2357:
2347:
2345:
2331:
2330:
2309:
2308:
2303:
2302:
2294:
2293:
2273:
2268:
2267:
2266:
2265:
2254:
2253:
2239:
2237:
2236:
2231:
2229:
2228:
2218:
2216:
2202:
2201:
2180:
2179:
2174:
2173:
2159:
2157:
2156:
2151:
2149:
2148:
2143:
2121:
2119:
2118:
2113:
2105:
2104:
2098:
2097:
2082:
2081:
2069:
2068:
2059:
2058:
2053:
2052:
2045:
2044:
2029:
2028:
2016:
2015:
2002:
2000:
1999:
1994:
1992:
1991:
1990:
1973:
1971:
1970:
1965:
1953:
1951:
1950:
1945:
1943:
1925:
1923:
1922:
1917:
1900:
1899:
1883:
1881:
1880:
1875:
1873:
1872:
1871:
1854:
1852:
1851:
1846:
1844:
1843:
1842:
1819:
1817:
1816:
1811:
1792:
1790:
1789:
1784:
1782:
1781:
1780:
1764:
1763:
1745:
1744:
1738:
1737:
1736:
1720:
1719:
1707:
1706:
1700:
1699:
1682:and defined as
1681:
1679:
1678:
1673:
1671:
1670:
1669:
1656:
1655:
1654:
1641:
1640:
1624:
1622:
1621:
1616:
1614:
1613:
1612:
1588:
1586:
1585:
1580:
1578:
1557:
1555:
1554:
1549:
1547:
1546:
1545:
1537:
1524:
1523:
1508:
1507:
1488:
1486:
1485:
1480:
1478:
1477:
1476:
1459:
1457:
1456:
1451:
1449:
1448:
1443:
1442:
1435:
1434:
1419:
1418:
1406:
1405:
1389:
1387:
1386:
1381:
1379:
1378:
1356:
1354:
1353:
1348:
1336:
1334:
1333:
1328:
1316:
1314:
1313:
1308:
1282:
1280:
1279:
1274:
1252:
1248:
1247:
1235:
1234:
1223:
1219:
1218:
1217:
1204:
1193:
1192:
1187:
1186:
1179:
1178:
1163:
1162:
1150:
1149:
1134:
1132:
1131:
1126:
1124:
1123:
1122:
1114:
1101:
1100:
1085:
1084:
1065:
1063:
1062:
1057:
1041:
1039:
1038:
1033:
1025:
1024:
1008:
1006:
1005:
1000:
982:
980:
979:
974:
972:
954:
952:
951:
946:
944:
929:
927:
926:
921:
919:
918:
917:
900:
898:
897:
892:
880:
878:
877:
872:
870:
869:
868:
851:
849:
848:
843:
831:
829:
828:
823:
821:
820:
819:
802:
800:
799:
794:
792:
791:
790:
770:
768:
767:
762:
760:
759:
744:
743:
728:
727:
722:
709:
707:
706:
701:
689:
687:
686:
681:
679:
667:
665:
664:
659:
657:
639:
637:
636:
631:
629:
628:
627:
614:
613:
612:
596:
595:
580:
568:
566:
565:
560:
558:
546:
544:
543:
538:
526:
524:
523:
518:
516:
515:
514:
497:
495:
494:
489:
477:
475:
474:
469:
467:
455:
453:
452:
447:
445:
444:
443:
437:
424:
422:
421:
416:
401:
399:
398:
393:
381:
379:
378:
373:
361:
359:
358:
353:
351:
323:
321:
320:
315:
313:
289:
287:
286:
281:
279:
267:
265:
264:
259:
247:
245:
244:
239:
237:
236:
235:
218:
216:
215:
210:
198:
196:
195:
190:
185:
169:
162:
161:
150:
146:
145:
144:
128:
127:
109:
108:
107:
90:
88:
87:
82:
7467:
7466:
7462:
7461:
7460:
7458:
7457:
7456:
7432:
7431:
7401:(3): 981–1031.
7378:10.2307/2371264
7346:
7344:
7342:
7312:
7293:
7277:
7275:Further reading
7272:
7271:
7228:Weiss, Benjamin
7225:
7221:
7182:(3): 981–1031.
7168:
7157:
7150:
7126:
7122:
7115:
7101:
7094:
7089:
7084:
7083:
7060:
7057:
7056:
7034:
7030:
7025:
7003:
6976:
6975:
6971:
6957:
6954:
6953:
6924:
6923:
6919:
6905:
6902:
6901:
6844:
6841:
6840:
6819:
6818:
6814:
6812:
6809:
6808:
6802:
6781:
6778:
6777:
6761:is known as a '
6734:
6731:
6730:
6714:
6711:
6710:
6682:
6679:
6678:
6650:
6647:
6646:
6628:
6627:
6623:
6615:
6612:
6611:
6595:
6592:
6591:
6572:
6569:
6568:
6533:
6529:
6520:
6516:
6508:
6505:
6504:
6476:
6473:
6472:
6448:
6444:
6433:
6430:
6429:
6409:
6405:
6394:
6391:
6390:
6374:
6371:
6370:
6352:
6351:
6347:
6339:
6336:
6335:
6317:
6316:
6312:
6304:
6301:
6300:
6273:
6269:
6258:
6255:
6254:
6225:
6221:
6219:
6216:
6215:
6199:
6196:
6195:
6177:
6176:
6172:
6164:
6161:
6160:
6146:
6125:
6122:
6121:
6100:
6096:
6094:
6091:
6090:
6069:
6065:
6057:
6054:
6053:
6050:
6016:
6012:
6006:
6002:
5996: and
5994:
5980:
5975:
5955:
5937:
5933:
5931:
5928:
5927:
5909:
5906:
5905:
5889:
5886:
5885:
5869:
5866:
5865:
5857:, based on the
5822:
5819:
5818:
5802:
5799:
5798:
5782:
5780:
5777:
5776:
5760:
5758:
5755:
5754:
5738:
5736:
5733:
5732:
5716:
5713:
5712:
5696:
5693:
5692:
5676:
5673:
5672:
5648:
5645:
5644:
5627:
5623:
5615:
5612:
5611:
5595:
5592:
5591:
5571:
5568:
5567:
5551:
5548:
5547:
5529:
5508:
5505:
5504:
5487:
5483:
5475:
5472:
5471:
5453:
5452:
5448:
5440:
5437:
5436:
5420:
5417:
5416:
5399:
5395:
5393:
5390:
5389:
5373:
5371:
5368:
5367:
5351:
5349:
5346:
5345:
5329:
5327:
5324:
5323:
5307:
5304:
5303:
5299:are forbidden.
5284:
5281:
5280:
5263:
5259:
5247:
5243:
5235:
5232:
5231:
5213:
5212:
5208:
5199:
5195:
5193:
5190:
5189:
5172:
5168:
5156:
5152:
5144:
5141:
5140:
5123:
5119:
5111:
5108:
5107:
5091:
5083:
5081:
5078:
5077:
5074:
5037:
5033:
5018:
5014:
4982:
4960:
4959:
4955:
4947:
4935:
4931:
4929:
4926:
4925:
4906:
4902:
4890:
4878:
4875:
4874:
4858:
4855:
4854:
4838:
4836:
4833:
4832:
4815:
4811:
4803:
4800:
4799:
4783:
4775:
4773:
4770:
4769:
4766:
4711:
4707:
4698:
4694:
4665:
4650:
4646:
4619:
4615:
4609:
4605:
4578:
4574:
4572:
4569:
4568:
4550:
4547:
4546:
4517:
4513:
4511:
4508:
4507:
4504:
4476:
4472:
4460:
4439:
4436:
4435:
4415:
4414:
4410:
4402:
4399:
4398:
4395:
4343:
4339:
4330:
4326:
4313:
4306:
4302:
4296:
4292:
4274:
4270:
4255:
4251:
4245:
4241:
4236:
4233:
4232:
4214:
4211:
4210:
4194:
4192:
4189:
4188:
4172:
4170:
4167:
4166:
4150:
4148:
4145:
4144:
4118:
4114:
4105:
4101:
4096:
4084:
4080:
4078:
4075:
4074:
4051:
4047:
4038:
4034:
4029:
4021:
4018:
4017:
4001:
3998:
3997:
3981:
3979:
3976:
3975:
3959:
3951:
3949:
3946:
3945:
3929:
3926:
3925:
3902:
3898:
3889:
3885:
3880:
3872:
3869:
3868:
3840:
3838:
3835:
3834:
3818:
3810:
3808:
3805:
3804:
3786:
3785:
3780:
3779:
3777:
3774:
3773:
3757:
3755:
3752:
3751:
3735:
3733:
3730:
3729:
3713:
3711:
3708:
3707:
3706:as finite, and
3691:
3688:
3687:
3684:
3663:
3661:
3658:
3657:
3641:
3639:
3636:
3635:
3619:
3617:
3614:
3613:
3597:
3594:
3593:
3569:
3566:
3565:
3558:
3533:
3529:
3512:
3506:
3499:
3497:
3476:
3473:
3472:
3444:
3440:
3438:
3435:
3434:
3408:
3404:
3402:
3399:
3398:
3373:
3370:
3369:
3352:
3348:
3339:
3335:
3333:
3330:
3329:
3303:
3299:
3284:
3280:
3274:
3270:
3265:
3262:
3261:
3235:
3231:
3216:
3212:
3206:
3202:
3197:
3194:
3193:
3177:
3169:
3166:
3165:
3140:
3137:
3136:
3120:
3112:
3109:
3108:
3092:
3084:
3081:
3080:
3064:
3061:
3060:
3057:
3020:
3016:
3007:
3003:
2998:
2987:
2969:
2965:
2950:
2946:
2940:
2936:
2912:
2908:
2906:
2903:
2902:
2884:
2881:
2880:
2863:
2859:
2857:
2854:
2853:
2836:
2832:
2814:
2810:
2808:
2805:
2804:
2782:
2779:
2778:
2762:
2759:
2758:
2720:
2716:
2714:
2711:
2710:
2694:
2686:
2683:
2682:
2664:
2663:
2659:
2651:
2648:
2647:
2644:
2623:
2620:
2619:
2602:
2598:
2596:
2593:
2592:
2589:
2558:
2553:
2552:
2543:
2530:
2521:
2517:
2516:
2512:
2511:
2500:
2483:
2461:
2460:
2456:
2448:
2436:
2432:
2430:
2427:
2426:
2407:
2399:
2398:
2394:
2393:
2387:
2386:
2377:
2374:
2373:
2353:
2349:
2332:
2326:
2319:
2317:
2304:
2298:
2297:
2296:
2289:
2282:
2269:
2261:
2260:
2256:
2255:
2249:
2248:
2245:
2242:
2241:
2224:
2220:
2203:
2197:
2190:
2188:
2175:
2169:
2168:
2167:
2165:
2162:
2161:
2144:
2139:
2138:
2130:
2127:
2126:
2100:
2099:
2087:
2083:
2077:
2073:
2064:
2063:
2054:
2048:
2047:
2046:
2034:
2030:
2024:
2020:
2011:
2010:
2008:
2005:
2004:
1986:
1985:
1981:
1979:
1976:
1975:
1959:
1956:
1955:
1939:
1931:
1928:
1927:
1895:
1891:
1889:
1886:
1885:
1867:
1866:
1862:
1860:
1857:
1856:
1838:
1837:
1833:
1825:
1822:
1821:
1805:
1802:
1801:
1794:
1776:
1769:
1765:
1756:
1752:
1740:
1739:
1732:
1725:
1721:
1715:
1711:
1702:
1701:
1695:
1691:
1689:
1686:
1685:
1665:
1664:
1660:
1650:
1649:
1645:
1636:
1632:
1630:
1627:
1626:
1608:
1607:
1603:
1601:
1598:
1597:
1574:
1566:
1563:
1562:
1541:
1533:
1532:
1528:
1513:
1509:
1503:
1499:
1494:
1491:
1490:
1472:
1471:
1467:
1465:
1462:
1461:
1444:
1438:
1437:
1436:
1424:
1420:
1414:
1410:
1401:
1400:
1398:
1395:
1394:
1374:
1370:
1362:
1359:
1358:
1342:
1339:
1338:
1322:
1319:
1318:
1290:
1287:
1286:
1283:
1243:
1239:
1230:
1226:
1213:
1212:
1208:
1200:
1188:
1182:
1181:
1180:
1168:
1164:
1158:
1154:
1145:
1144:
1142:
1139:
1138:
1118:
1110:
1109:
1105:
1090:
1086:
1080:
1076:
1071:
1068:
1067:
1051:
1048:
1047:
1020:
1016:
1014:
1011:
1010:
988:
985:
984:
983:, and for each
968:
960:
957:
956:
940:
938:
935:
934:
913:
912:
908:
906:
903:
902:
886:
883:
882:
864:
863:
859:
857:
854:
853:
837:
834:
833:
815:
814:
810:
808:
805:
804:
786:
785:
781:
779:
776:
775:
749:
745:
739:
735:
723:
718:
717:
715:
712:
711:
695:
692:
691:
675:
673:
670:
669:
653:
645:
642:
641:
623:
622:
618:
608:
601:
597:
591:
587:
576:
574:
571:
570:
554:
552:
549:
548:
532:
529:
528:
510:
509:
505:
503:
500:
499:
483:
480:
479:
463:
461:
458:
457:
439:
438:
433:
432:
430:
427:
426:
407:
404:
403:
402:by the product
387:
384:
383:
367:
364:
363:
347:
333:
330:
329:
309:
307:
304:
303:
300:
275:
273:
270:
269:
253:
250:
249:
231:
230:
226:
224:
221:
220:
204:
201:
200:
181:
157:
153:
140:
133:
129:
123:
119:
103:
102:
98:
96:
93:
92:
76:
73:
72:
44:discrete system
17:
12:
11:
5:
7465:
7455:
7454:
7449:
7444:
7430:
7429:
7397:. New Series.
7390:
7372:(4): 815–866.
7356:Morse, Marston
7352:
7340:
7316:
7310:
7297:
7291:
7276:
7273:
7270:
7269:
7238:(5): 462–474,
7232:Monatsh. Math.
7219:
7178:. New Series.
7155:
7148:
7120:
7113:
7091:
7090:
7088:
7085:
7082:
7081:
7064:
7027:
7026:
7024:
7021:
7020:
7019:
7014:
7009:
7002:
6999:
6979:
6974:
6970:
6967:
6964:
6961:
6941:is called the
6927:
6922:
6918:
6915:
6912:
6909:
6866:
6863:
6860:
6857:
6854:
6851:
6848:
6822:
6817:
6801:
6798:
6785:
6770:(or just as a
6750:
6747:
6744:
6741:
6738:
6718:
6698:
6695:
6692:
6689:
6686:
6666:
6663:
6660:
6657:
6654:
6631:
6626:
6622:
6619:
6599:
6576:
6544:
6541:
6536:
6532:
6528:
6523:
6519:
6515:
6512:
6492:
6489:
6486:
6483:
6480:
6456:
6451:
6447:
6443:
6440:
6437:
6417:
6412:
6408:
6404:
6401:
6398:
6378:
6355:
6350:
6346:
6343:
6320:
6315:
6311:
6308:
6281:
6276:
6272:
6268:
6265:
6262:
6242:
6239:
6236:
6233:
6228:
6224:
6203:
6180:
6175:
6171:
6168:
6145:
6142:
6129:
6103:
6099:
6072:
6068:
6064:
6061:
6052:is finite and
6039:
6036:
6033:
6030:
6025:
6022:
6019:
6015:
6009:
6005:
6001:
5993:
5990:
5987:
5978:
5974:
5971:
5968:
5962:
5958:
5954:
5951:
5948:
5945:
5940:
5936:
5926:
5913:
5893:
5873:
5835:
5832:
5829:
5826:
5806:
5785:
5763:
5741:
5731:is finite and
5720:
5700:
5680:
5652:
5630:
5626:
5622:
5619:
5599:
5575:
5555:
5528:
5525:
5512:
5490:
5486:
5482:
5479:
5456:
5451:
5447:
5444:
5424:
5402:
5398:
5376:
5354:
5332:
5311:
5288:
5266:
5262:
5258:
5255:
5250:
5246:
5242:
5239:
5216:
5211:
5207:
5202:
5198:
5175:
5171:
5167:
5164:
5159:
5155:
5151:
5148:
5126:
5122:
5118:
5115:
5094:
5090:
5086:
5063:
5060:
5057:
5054:
5051:
5046:
5043:
5040:
5036:
5032:
5029:
5026:
5021:
5017:
5013:
5007:
5004:
5001:
4998:
4995:
4989:
4985:
4981:
4978:
4975:
4969:
4963:
4958:
4954:
4950:
4946:
4943:
4938:
4934:
4924:
4909:
4905:
4899:
4896:
4893:
4889:
4885:
4882:
4862:
4841:
4818:
4814:
4810:
4807:
4786:
4782:
4778:
4755:
4752:
4749:
4746:
4743:
4740:
4737:
4734:
4731:
4728:
4725:
4722:
4714:
4710:
4706:
4701:
4697:
4690:
4687:
4684:
4681:
4675:
4672:
4668:
4664:
4658:
4653:
4649:
4645:
4640:
4637:
4634:
4631:
4628:
4625:
4622:
4618:
4612:
4608:
4604:
4601:
4598:
4595:
4592:
4589:
4586:
4581:
4577:
4567:
4554:
4534:
4531:
4528:
4525:
4520:
4516:
4493:
4490:
4487:
4484:
4479:
4475:
4469:
4466:
4463:
4459:
4455:
4452:
4449:
4446:
4443:
4434:
4418:
4413:
4409:
4406:
4384:
4381:
4378:
4375:
4372:
4369:
4366:
4363:
4360:
4357:
4354:
4346:
4342:
4338:
4333:
4329:
4322:
4316:
4312:
4309:
4305:
4299:
4295:
4291:
4288:
4285:
4282:
4277:
4273:
4269:
4266:
4263:
4258:
4254:
4248:
4244:
4240:
4231:
4218:
4197:
4175:
4153:
4127:
4124:
4121:
4117:
4113:
4108:
4104:
4099:
4095:
4090:
4087:
4083:
4060:
4057:
4054:
4050:
4046:
4041:
4037:
4032:
4028:
4025:
4005:
3984:
3962:
3958:
3954:
3933:
3911:
3908:
3905:
3901:
3897:
3892:
3888:
3883:
3879:
3876:
3856:
3853:
3850:
3847:
3843:
3821:
3817:
3813:
3789:
3783:
3760:
3738:
3716:
3695:
3683:
3680:
3666:
3644:
3622:
3601:
3573:
3547:
3544:
3541:
3536:
3532:
3524:
3521:
3518:
3515:
3509:
3505:
3502:
3496:
3492:
3489:
3486:
3483:
3480:
3471:
3458:
3455:
3452:
3447:
3443:
3422:
3419:
3416:
3411:
3407:
3386:
3383:
3380:
3377:
3355:
3351:
3347:
3342:
3338:
3317:
3314:
3311:
3306:
3302:
3298:
3293:
3290:
3287:
3283:
3277:
3273:
3269:
3249:
3246:
3243:
3238:
3234:
3230:
3225:
3222:
3219:
3215:
3209:
3205:
3201:
3180:
3176:
3173:
3153:
3150:
3147:
3144:
3123:
3119:
3116:
3095:
3091:
3088:
3068:
3046:
3043:
3040:
3037:
3034:
3031:
3023:
3019:
3015:
3010:
3006:
2997:
2994:
2990:
2983:
2977:
2972:
2968:
2964:
2959:
2956:
2953:
2949:
2943:
2939:
2935:
2932:
2929:
2926:
2923:
2920:
2915:
2911:
2901:
2888:
2866:
2862:
2839:
2835:
2831:
2828:
2825:
2822:
2817:
2813:
2792:
2789:
2786:
2766:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2723:
2719:
2697:
2693:
2690:
2667:
2662:
2658:
2655:
2643:
2640:
2627:
2605:
2601:
2578:
2575:
2572:
2569:
2564:
2561:
2556:
2551:
2546:
2541:
2537:
2533:
2529:
2524:
2520:
2515:
2507:
2503:
2499:
2496:
2493:
2490:
2486:
2482:
2479:
2476:
2470:
2464:
2459:
2455:
2451:
2447:
2444:
2439:
2435:
2425:
2410:
2402:
2397:
2390:
2384:
2381:
2356:
2352:
2344:
2341:
2338:
2335:
2329:
2325:
2322:
2316:
2312:
2307:
2301:
2292:
2288:
2285:
2281:
2277:
2272:
2264:
2259:
2252:
2227:
2223:
2215:
2212:
2209:
2206:
2200:
2196:
2193:
2187:
2183:
2178:
2172:
2147:
2142:
2137:
2134:
2111:
2108:
2103:
2096:
2093:
2090:
2086:
2080:
2076:
2072:
2067:
2062:
2057:
2051:
2043:
2040:
2037:
2033:
2027:
2023:
2019:
2014:
1989:
1984:
1963:
1942:
1938:
1935:
1915:
1912:
1909:
1906:
1903:
1898:
1894:
1870:
1865:
1841:
1836:
1832:
1829:
1809:
1779:
1775:
1772:
1768:
1762:
1759:
1755:
1751:
1748:
1743:
1735:
1731:
1728:
1724:
1718:
1714:
1710:
1705:
1698:
1694:
1684:
1668:
1663:
1659:
1653:
1648:
1644:
1639:
1635:
1625:is denoted by
1611:
1606:
1577:
1573:
1570:
1544:
1540:
1536:
1531:
1527:
1522:
1519:
1516:
1512:
1506:
1502:
1498:
1475:
1470:
1447:
1441:
1433:
1430:
1427:
1423:
1417:
1413:
1409:
1404:
1377:
1373:
1369:
1366:
1346:
1326:
1306:
1303:
1300:
1297:
1294:
1272:
1269:
1266:
1263:
1260:
1257:
1251:
1246:
1242:
1238:
1233:
1229:
1222:
1216:
1211:
1207:
1203:
1199:
1196:
1191:
1185:
1177:
1174:
1171:
1167:
1161:
1157:
1153:
1148:
1137:
1121:
1117:
1113:
1108:
1104:
1099:
1096:
1093:
1089:
1083:
1079:
1075:
1055:
1031:
1028:
1023:
1019:
998:
995:
992:
971:
967:
964:
943:
916:
911:
890:
867:
862:
841:
818:
813:
789:
784:
758:
755:
752:
748:
742:
738:
734:
731:
726:
721:
699:
678:
656:
652:
649:
626:
621:
617:
611:
607:
604:
600:
594:
590:
586:
583:
579:
557:
536:
513:
508:
487:
466:
442:
436:
414:
411:
391:
371:
350:
346:
343:
340:
337:
312:
299:
296:
278:
257:
234:
229:
208:
188:
184:
180:
177:
174:
168:
165:
160:
156:
149:
143:
139:
136:
132:
126:
122:
118:
115:
112:
106:
101:
80:
15:
9:
6:
4:
3:
2:
7464:
7453:
7450:
7448:
7445:
7443:
7440:
7439:
7437:
7426:
7422:
7418:
7414:
7409:
7404:
7400:
7396:
7391:
7387:
7383:
7379:
7375:
7371:
7367:
7366:
7361:
7357:
7353:
7343:
7341:0-521-81220-8
7337:
7332:
7331:
7325:
7321:
7317:
7313:
7311:0-521-55900-6
7307:
7303:
7298:
7294:
7288:
7284:
7279:
7278:
7266:
7261:
7257:
7253:
7249:
7245:
7241:
7237:
7233:
7229:
7223:
7215:
7211:
7207:
7203:
7199:
7195:
7190:
7185:
7181:
7177:
7173:
7166:
7164:
7162:
7160:
7151:
7145:
7141:
7137:
7133:
7132:
7124:
7116:
7110:
7106:
7099:
7097:
7092:
7078:
7062:
7054:
7050:
7046:
7042:
7038:
7032:
7028:
7018:
7015:
7013:
7012:Bit shift map
7010:
7008:
7005:
7004:
6998:
6996:
6968:
6965:
6962:
6950:
6948:
6944:
6916:
6913:
6910:
6898:
6896:
6895:pumping lemma
6892:
6888:
6884:
6880:
6861:
6858:
6855:
6849:
6846:
6837:
6815:
6807:
6797:
6775:
6774:
6769:
6768:
6766:
6742:
6716:
6687:
6658:
6624:
6620:
6588:
6566:
6565:
6560:
6559:
6539:
6534:
6530:
6526:
6521:
6517:
6513:
6481:
6470:
6449:
6445:
6441:
6410:
6406:
6402:
6376:
6348:
6344:
6313:
6309:
6297:
6295:
6274:
6270:
6266:
6231:
6226:
6222:
6201:
6173:
6169:
6157:
6155:
6151:
6141:
6127:
6119:
6101:
6097:
6088:
6070:
6066:
6062:
6037:
6031:
6028:
6023:
6020:
6017:
6007:
6003:
5991:
5988:
5985:
5972:
5969:
5960:
5952:
5949:
5943:
5938:
5934:
5925:
5911:
5871:
5862:
5860:
5856:
5851:
5849:
5824:
5718:
5698:
5670:
5666:
5628:
5624:
5620:
5597:
5589:
5553:
5544:
5542:
5541:
5536:
5535:
5524:
5510:
5488:
5484:
5480:
5449:
5445:
5422:
5400:
5396:
5309:
5300:
5286:
5264:
5260:
5256:
5248:
5244:
5237:
5209:
5205:
5200:
5196:
5173:
5169:
5165:
5157:
5153:
5146:
5124:
5120:
5116:
5088:
5061:
5055:
5052:
5044:
5041:
5038:
5034:
5030:
5027:
5024:
5019:
5015:
5005:
5002:
4999:
4996:
4987:
4979:
4976:
4967:
4956:
4952:
4941:
4936:
4932:
4923:
4907:
4903:
4897:
4894:
4891:
4887:
4883:
4880:
4860:
4816:
4812:
4808:
4780:
4753:
4747:
4744:
4741:
4738:
4735:
4732:
4729:
4726:
4723:
4712:
4708:
4704:
4699:
4695:
4688:
4685:
4682:
4679:
4670:
4656:
4651:
4647:
4643:
4638:
4635:
4632:
4629:
4626:
4623:
4620:
4610:
4606:
4593:
4579:
4575:
4566:
4552:
4529:
4523:
4518:
4514:
4491:
4477:
4473:
4467:
4464:
4461:
4457:
4453:
4441:
4433:
4411:
4407:
4382:
4376:
4373:
4370:
4367:
4364:
4361:
4358:
4355:
4344:
4340:
4336:
4331:
4327:
4320:
4310:
4307:
4297:
4293:
4283:
4275:
4271:
4267:
4264:
4261:
4256:
4252:
4246:
4242:
4230:
4216:
4141:
4125:
4122:
4119:
4115:
4111:
4106:
4088:
4085:
4081:
4058:
4055:
4052:
4048:
4044:
4039:
4023:
4003:
3956:
3931:
3909:
3906:
3903:
3899:
3895:
3890:
3874:
3851:
3815:
3693:
3679:
3599:
3591:
3588:, but in the
3587:
3563:
3534:
3530:
3519:
3516:
3503:
3500:
3494:
3490:
3478:
3470:
3445:
3441:
3409:
3405:
3384:
3381:
3378:
3375:
3353:
3349:
3345:
3340:
3336:
3304:
3300:
3296:
3291:
3288:
3285:
3275:
3271:
3236:
3232:
3228:
3223:
3220:
3217:
3207:
3203:
3174:
3171:
3151:
3148:
3145:
3142:
3117:
3114:
3089:
3086:
3044:
3038:
3035:
3032:
3021:
3017:
3013:
3008:
3004:
2992:
2975:
2970:
2966:
2962:
2957:
2954:
2951:
2941:
2937:
2927:
2913:
2909:
2900:
2864:
2860:
2837:
2833:
2829:
2815:
2811:
2787:
2784:
2764:
2741:
2735:
2717:
2691:
2688:
2660:
2656:
2639:
2625:
2603:
2599:
2576:
2570:
2567:
2562:
2559:
2549:
2544:
2539:
2522:
2518:
2513:
2505:
2497:
2494:
2488:
2480:
2477:
2468:
2457:
2453:
2442:
2437:
2433:
2424:
2408:
2395:
2382:
2379:
2372:
2354:
2350:
2339:
2336:
2323:
2320:
2314:
2310:
2305:
2286:
2283:
2279:
2275:
2270:
2257:
2225:
2221:
2213:
2210:
2207:
2194:
2191:
2185:
2181:
2176:
2145:
2135:
2132:
2123:
2106:
2094:
2091:
2088:
2078:
2074:
2060:
2041:
2038:
2035:
2025:
2021:
1982:
1936:
1933:
1910:
1896:
1892:
1863:
1834:
1830:
1807:
1799:
1773:
1770:
1760:
1757:
1753:
1746:
1729:
1726:
1716:
1712:
1696:
1692:
1683:
1661:
1646:
1642:
1637:
1633:
1604:
1595:
1593:
1571:
1568:
1559:
1538:
1529:
1525:
1520:
1517:
1514:
1504:
1500:
1468:
1445:
1431:
1428:
1425:
1415:
1411:
1391:
1375:
1367:
1344:
1324:
1301:
1295:
1292:
1270:
1264:
1261:
1258:
1249:
1244:
1240:
1236:
1231:
1227:
1220:
1209:
1205:
1194:
1189:
1175:
1172:
1169:
1159:
1155:
1136:
1115:
1106:
1102:
1097:
1094:
1091:
1081:
1077:
1053:
1045:
1029:
1026:
1021:
1017:
996:
993:
990:
965:
962:
931:
909:
888:
860:
839:
811:
782:
772:
756:
753:
750:
740:
736:
729:
724:
697:
650:
647:
640:and a subset
619:
615:
605:
602:
592:
588:
581:
534:
506:
485:
412:
409:
389:
369:
344:
341:
338:
335:
327:
295:
293:
255:
227:
206:
178:
175:
166:
163:
158:
154:
147:
137:
134:
124:
120:
110:
99:
70:
65:
63:
59:
55:
51:
50:
45:
41:
38:
34:
30:
26:
22:
7398:
7394:
7369:
7363:
7345:. Retrieved
7329:
7320:Lothaire, M.
7301:
7282:
7235:
7231:
7222:
7179:
7175:
7130:
7123:
7104:
7076:
7052:
7048:
7044:
7040:
7036:
7031:
6951:
6899:
6890:
6886:
6882:
6878:
6838:
6805:
6803:
6771:
6763:
6762:
6589:
6562:
6556:
6298:
6158:
6147:
6051:
5863:
5855:Weiss (1973)
5852:
5664:
5587:
5545:
5540:sofic shifts
5539:
5533:
5530:
5301:
5076:However, if
5075:
4767:
4505:
4396:
4142:
3974:, since all
3833:, since all
3685:
3561:
3559:
3058:
2645:
2590:
2370:
2124:
1797:
1795:
1591:
1590:
1560:
1392:
1284:
1043:
932:
773:
328:, and given
301:
66:
62:sofic shifts
47:
35:is a set of
32:
28:
18:
7077:shift space
7037:shift space
6995:Baker's map
6561:or just as
6503:such that
6214:-shift map
6140:is finite.
5665:sofic shift
1798:shift space
1135:is the set
547:indexed by
29:shift space
25:mathematics
7436:Categories
7408:2010.10595
7347:2008-01-29
7265:MathSciNet
7189:2010.10595
7087:References
6947:Cantor set
6806:full shift
5610:such that
5470:such that
5230:such that
3328:such that
1594:-shift map
1357:simply as
298:Definition
7425:254048586
7260:123440583
7214:254048586
7206:1678-7544
7023:Footnotes
7017:Gray code
6784:Φ
6776:whenever
6746:Φ
6740:Λ
6697:Λ
6694:→
6691:Λ
6685:Φ
6662:Φ
6656:Λ
6621:⊂
6618:Λ
6598:Φ
6575:Φ
6567:whenever
6543:Φ
6540:∘
6531:σ
6518:σ
6514:∘
6511:Φ
6491:Γ
6488:→
6485:Λ
6479:Φ
6446:σ
6439:Γ
6407:σ
6400:Λ
6345:⊂
6342:Γ
6310:⊂
6307:Λ
6271:σ
6264:Λ
6241:Λ
6238:→
6235:Λ
6223:σ
6170:⊂
6167:Λ
6152:on which
6060:Λ
6029:∈
6021:∈
5989:∈
5973:⊂
5967:∃
5953:∈
5892:Λ
5831:Λ
5805:Λ
5679:Φ
5651:Λ
5618:Λ
5574:Λ
5478:Λ
5446:⊂
5443:Λ
5257:⊊
5238:σ
5206:⊂
5147:σ
5114:Λ
5053:∉
5000:≥
4994:∀
4980:∈
4974:∀
4953:∈
4922:and then
4895:≥
4888:⋃
4884:⊂
4806:Λ
4721:∀
4674:Λ
4671:∈
4663:∃
4644:∈
4588:Λ
4553:ϵ
4530:ϵ
4486:Λ
4465:≥
4458:⋃
4448:Λ
4408:⊂
4405:Λ
4353:∀
4311:∈
4123:−
4086:−
4082:σ
4024:σ
3875:σ
3846:∖
3572:Λ
3543:Λ
3523:∞
3514:#
3504:⊂
3495:⋃
3485:Λ
3454:Λ
3418:Λ
3313:Λ
3297:∈
3289:∈
3245:Λ
3229:∈
3221:∈
3175:∈
3164:for some
3118:⊂
3090:⊂
3067:Λ
3036:∈
3030:∀
2996:Λ
2993:∈
2982:∃
2963:∈
2955:∈
2922:Λ
2887:Λ
2830:⊂
2824:Λ
2791:∅
2788:≠
2765:ϵ
2742:ϵ
2730:Λ
2722:∅
2692:⊂
2657:⊂
2654:Λ
2568:∉
2519:σ
2498:∈
2492:∀
2481:⊂
2475:∀
2454:∈
2383:⊂
2343:∞
2334:#
2324:⊂
2315:⋃
2287:∈
2280:⋃
2205:#
2195:⊂
2186:⋃
2160:, define
2146:∗
2136:∈
2125:For each
2110:Λ
2107:∩
2092:∈
2056:Λ
2039:∈
1962:Λ
1937:∈
1914:Λ
1911:⊂
1905:Λ
1893:σ
1831:⊂
1828:Λ
1820:is a set
1774:∈
1730:∈
1693:σ
1658:→
1634:σ
1572:∈
1526:∈
1518:∈
1429:∈
1262:∈
1256:∀
1206:∈
1173:∈
1103:∈
1095:∈
1046:given by
1027:∈
994:∈
966:⊂
754:∈
651:⊂
616:∈
606:∈
345:∈
179:∈
173:∀
164:∈
138:∈
79:Λ
7322:(2002).
7053:subshift
7045:subshift
7007:Tent map
7001:See also
6800:Examples
5537:and the
3924:for all
3562:language
3135:, i.e.,
2899:, i.e.,
2757:, where
1926:for all
1044:cylinder
248:, where
199:, where
60:and the
54:synonyms
37:infinite
33:subshift
7386:2371264
7252:0340556
4073:and by
3192:, then
290:is any
67:In the
7423:
7384:
7338:
7308:
7289:
7258:
7250:
7212:
7204:
7146:
7111:
6889:whose
6194:and a
5964:
5859:Hebrew
5643:, and
5344:being
5009:
4991:
4971:
4718:
4692:
4677:
4660:
4506:where
4350:
4324:
3634:being
3027:
2985:
2979:
2709:, let
2509:
2472:
2240:, and
1589:, the
1561:Given
1253:
1224:
1042:. The
1009:, let
569:. For
425:. Let
326:monoid
292:monoid
170:
151:
7421:S2CID
7403:arXiv
7382:JSTOR
7256:S2CID
7210:S2CID
7184:arXiv
7049:shift
7041:shift
6610:from
6292:is a
5864:When
5846:is a
5663:is a
5586:is a
5366:) or
2803:let
1285:When
382:with
324:be a
40:words
7336:ISBN
7306:ISBN
7287:ISBN
7202:ISSN
7144:ISBN
7109:ISBN
7051:and
6839:Let
6467:are
6428:and
6334:and
4545:and
3560:the
3520:<
3433:and
2340:<
1066:and
302:Let
27:, a
7413:doi
7374:doi
7240:doi
7194:doi
7136:doi
7043:or
6897:).
5775:or
5753:is
4187:or
4165:is
4016:by
3656:or
3564:of
3368:if
1596:on
774:On
710:as
91:of
31:or
19:In
7438::
7419:.
7411:.
7399:53
7380:.
7370:60
7368:.
7358:;
7326:.
7254:,
7248:MR
7246:,
7236:77
7234:,
7208:.
7200:.
7192:.
7180:53
7174:.
7158:^
7142:.
7095:^
6949:.
6836:.
6296:.
5944::=
5850:.
5543:.
5523:.
4594::=
4524::=
4454::=
4284::=
4140:.
3491::=
2928::=
2736::=
2638:.
2443::=
2276::=
2182::=
2122:.
2061::=
1796:A
1793:.
1558:.
1390:.
1195::=
771:.
730::=
294:.
111::=
64:.
7427:.
7415::
7405::
7388:.
7376::
7350:.
7314:.
7295:.
7242::
7216:.
7196::
7186::
7152:.
7138::
7117:.
7063:g
6978:Z
6973:}
6969:1
6966:,
6963:0
6960:{
6926:N
6921:}
6917:1
6914:,
6911:0
6908:{
6891:b
6887:A
6883:b
6879:A
6865:}
6862:b
6859:,
6856:a
6853:{
6850:=
6847:A
6821:N
6816:A
6767:'
6749:)
6743:,
6737:(
6717:g
6688::
6665:)
6659:,
6653:(
6630:G
6625:A
6535:g
6527:=
6522:g
6482::
6455:)
6450:g
6442:,
6436:(
6416:)
6411:g
6403:,
6397:(
6377:g
6354:G
6349:B
6319:G
6314:A
6280:)
6275:g
6267:,
6261:(
6232::
6227:g
6202:g
6179:G
6174:A
6128:A
6102:F
6098:M
6071:F
6067:X
6063:=
6038:,
6035:}
6032:F
6024:N
6018:i
6014:)
6008:i
6004:w
6000:(
5992:N
5986:g
5977:G
5970:N
5961::
5957:G
5950:g
5947:{
5939:F
5935:M
5912:F
5872:A
5834:)
5828:(
5825:W
5784:Z
5762:N
5740:G
5719:A
5699:g
5629:F
5625:X
5621:=
5598:F
5554:A
5511:F
5489:F
5485:X
5481:=
5455:G
5450:A
5423:F
5401:F
5397:M
5375:Z
5353:N
5331:G
5310:A
5287:F
5265:F
5261:X
5254:)
5249:F
5245:X
5241:(
5215:N
5210:A
5201:F
5197:X
5174:F
5170:X
5166:=
5163:)
5158:F
5154:X
5150:(
5125:F
5121:X
5117:=
5093:N
5089:=
5085:G
5062:.
5059:}
5056:F
5050:)
5045:k
5042:+
5039:i
5035:x
5031:.
5028:.
5025:.
5020:i
5016:x
5012:(
5006:,
5003:0
4997:k
4988:,
4984:Z
4977:i
4968::
4962:Z
4957:A
4949:x
4945:{
4942:=
4937:F
4933:X
4908:n
4904:A
4898:1
4892:n
4881:F
4861:F
4840:G
4817:F
4813:X
4809:=
4785:Z
4781:=
4777:G
4754:.
4751:}
4748:n
4745:,
4742:.
4739:.
4736:.
4733:,
4730:0
4727:=
4724:i
4713:i
4709:a
4705:=
4700:i
4696:x
4689:.
4686:t
4683:.
4680:s
4667:x
4657::
4652:n
4648:A
4639:n
4636:.
4633:.
4630:,
4627:0
4624:=
4621:i
4617:)
4611:i
4607:a
4603:(
4600:(
4597:{
4591:)
4585:(
4580:n
4576:W
4533:}
4527:{
4519:0
4515:W
4492:,
4489:)
4483:(
4478:n
4474:W
4468:0
4462:n
4451:)
4445:(
4442:W
4417:G
4412:A
4383:.
4380:}
4377:n
4374:,
4371:.
4368:.
4365:,
4362:0
4359:=
4356:i
4345:i
4341:a
4337:=
4332:i
4328:x
4321::
4315:G
4308:i
4304:)
4298:i
4294:x
4290:(
4287:{
4281:]
4276:n
4272:a
4268:.
4265:.
4262:.
4257:1
4253:a
4247:0
4243:a
4239:[
4217:A
4196:Z
4174:N
4152:G
4126:1
4120:n
4116:x
4112:=
4107:n
4103:)
4098:x
4094:(
4089:1
4059:1
4056:+
4053:n
4049:x
4045:=
4040:n
4036:)
4031:x
4027:(
4004:n
3983:Z
3961:Z
3957:=
3953:G
3932:n
3910:1
3907:+
3904:n
3900:x
3896:=
3891:n
3887:)
3882:x
3878:(
3855:}
3852:0
3849:{
3842:N
3820:N
3816:=
3812:G
3788:G
3782:1
3759:Z
3737:N
3715:G
3694:A
3665:Z
3643:N
3621:G
3600:A
3546:)
3540:(
3535:N
3531:W
3517:N
3508:G
3501:N
3488:)
3482:(
3479:W
3457:)
3451:(
3446:N
3442:W
3421:)
3415:(
3410:M
3406:W
3385:i
3382:g
3379:=
3376:j
3354:i
3350:v
3346:=
3341:j
3337:w
3316:)
3310:(
3305:N
3301:W
3292:N
3286:i
3282:)
3276:i
3272:v
3268:(
3248:)
3242:(
3237:M
3233:W
3224:M
3218:j
3214:)
3208:j
3204:w
3200:(
3179:G
3172:g
3152:N
3149:g
3146:=
3143:M
3122:G
3115:N
3094:G
3087:M
3045:.
3042:}
3039:N
3033:i
3022:i
3018:w
3014:=
3009:i
3005:x
2989:x
2976::
2971:N
2967:A
2958:N
2952:i
2948:)
2942:i
2938:w
2934:(
2931:{
2925:)
2919:(
2914:N
2910:W
2865:N
2861:A
2838:N
2834:A
2827:)
2821:(
2816:N
2812:W
2785:N
2745:}
2739:{
2733:)
2727:(
2718:W
2696:G
2689:N
2666:G
2661:A
2626:F
2604:F
2600:X
2577:.
2574:}
2571:F
2563:N
2560:g
2555:x
2550:=
2545:N
2540:)
2536:)
2532:x
2528:(
2523:g
2514:(
2506:,
2502:G
2495:g
2489:,
2485:G
2478:N
2469::
2463:G
2458:A
2450:x
2446:{
2438:F
2434:X
2409:f
2401:G
2396:A
2389:N
2380:F
2355:N
2351:A
2337:N
2328:G
2321:N
2311:=
2306:k
2300:N
2291:N
2284:k
2271:f
2263:G
2258:A
2251:N
2226:N
2222:A
2214:k
2211:=
2208:N
2199:G
2192:N
2177:k
2171:N
2141:N
2133:k
2102:]
2095:D
2089:i
2085:)
2079:i
2075:a
2071:(
2066:[
2050:]
2042:D
2036:i
2032:)
2026:i
2022:a
2018:(
2013:[
1988:G
1983:A
1941:G
1934:g
1908:)
1902:(
1897:g
1869:G
1864:A
1840:G
1835:A
1808:A
1778:G
1771:i
1767:)
1761:i
1758:g
1754:x
1750:(
1747:=
1742:)
1734:G
1727:i
1723:)
1717:i
1713:x
1709:(
1704:(
1697:g
1667:G
1662:A
1652:G
1647:A
1643::
1638:g
1610:G
1605:A
1592:g
1576:G
1569:g
1543:|
1539:D
1535:|
1530:A
1521:D
1515:i
1511:)
1505:i
1501:a
1497:(
1474:G
1469:A
1446:D
1440:]
1432:D
1426:i
1422:)
1416:i
1412:a
1408:(
1403:[
1376:g
1372:]
1368:b
1365:[
1345:g
1325:b
1305:}
1302:g
1299:{
1296:=
1293:D
1271:.
1268:}
1265:D
1259:i
1250:,
1245:i
1241:a
1237:=
1232:i
1228:x
1221::
1215:G
1210:A
1202:x
1198:{
1190:D
1184:]
1176:D
1170:i
1166:)
1160:i
1156:a
1152:(
1147:[
1120:|
1116:D
1112:|
1107:A
1098:D
1092:i
1088:)
1082:i
1078:a
1074:(
1054:D
1030:A
1022:i
1018:a
997:D
991:i
970:G
963:D
942:G
915:G
910:A
889:A
866:G
861:A
840:A
817:G
812:A
788:G
783:A
757:N
751:i
747:)
741:i
737:x
733:(
725:N
720:x
698:N
677:x
655:G
648:N
625:G
620:A
610:G
603:i
599:)
593:i
589:x
585:(
582:=
578:x
556:G
535:A
512:G
507:A
486:A
465:G
441:G
435:1
413:h
410:g
390:h
370:g
349:G
342:h
339:,
336:g
311:G
277:G
256:A
233:G
228:A
207:A
187:}
183:Z
176:i
167:A
159:i
155:x
148::
142:Z
135:i
131:)
125:i
121:x
117:(
114:{
105:Z
100:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.