Talk abstract:

Multiplicities of SFT Covers

Natasha Jonoska
Department of Mathematics
University of South Florida

Joint work with Doris Fiebig and Ulf Fiebig.

Given a finite directed labeled graph, there is a natural mapping f:S T from the system $S$ of all bi-infinite paths on the graph to the system T of all bi-infinite label sequences. T is called a sofic shift and $(S,f)$ is called an cover of T. We define the multiplicity of the cover $(S,f)$ to be the largest number of f-preimages of a point. The intrinsic multiplicity of of a sofic shift T is the minimum of the multiplicities over all covers of T, denoted by m(T). Is m(T) computable? We do not answer this question. However the attempt to solve this problem led us to find sharp estimates for the intrinsic multiplicity, sharpen a result of S.Williams, and solve a problem of P.Trow.

References:

M.Boyle, B. Kitchens, B. Marcus, A Note on Minimal Covers for Sofic systems, Proceedings fo the AMS, 95 No.3, (Nov. 1985), 403-411.

N.Jonoska: Sofic Systems with Synchronizing Representations, Theoretical Computer Science, 158 1-2 (1996) 81-115.

B.Kitchens: Symbolic Dynamics, Springer 1998

D.Lind, B.Marcus: An Introduction to Symbolic Dynamics, Cambridge University Press, New York (1995).

P.Trow: Lifting covers of sofic shifts, preprint.

S.Williams: A sofic system with infinitely many minimal covers, Proc. Amer. Math. Soc. 98, No. 3 (1986) 503-505.

S.Williams: Covers of non-almost-finite-type systems, Proc. Amer. Math. Soc. 104 (1988), 245-252.

Material used during the talk

Back to Codes, Systems and Graphical Models