Combinations of Context-Free Shifts and Shifts of Finite Type.
Hiroshi Kamabe · 2008
Abstract—A Dyck shift and a Motzkin shift are mathematical models for constraints on genetic sequences. In terms of the theory of symbolic dynamics, neither of the Dyck shift nor the Motzkin shift is sofic. In terms of the mathematical language theory, they are non-regular and context free languages. There-fore we can not use the Perron-Frobenius theory to calculate capacities of these constraints. O. Milenkovic has shown that the DSV (Delèst-Schẗzenberger-Viennot) theory for grammars gives us a method of calculating capacities of constraints modeled with context-free grammars. On the other hand, W. Krieger shown that the capacity of the Dyck shift with brackets of n kinds is log(n+1). Recently, K. Inoue has shown that the capacity of the Motzkin shift with brackets of n kinds and neutral symbols of m kinds is log(n+m+ 1). We give alternative proofs for these results by using the DSV theory. We also show that the DSV method allow us to calculate the capacity of a constraint given as a combinations of context free languages and shifts of finite type.