Multiplicities of covers for sofic shifts

Authors
Fiebig, D Fiebig, UR Jonoska, N
Citation
D. Fiebig et al., Multiplicities of covers for sofic shifts, THEOR COMP, 262(1-2), 2001, pp. 349-375
Citations number
7
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
262
Issue
1-2
Year of publication
2001
Pages
349 - 375
Database
ISI
SICI code
0304-3975(20010706)262:1-2<349:MOCFSS>2.0.ZU;2-C
Abstract
We consider a transitive sofic shift T and a SFT cover f : S --> T. We defi ne the multiplicity of the cover (S,f) to be the largest number of preimage s of a point. The intrinsic multiplicity of T is the minimum of the multipl icities over all covers of T, denoted by m(T). Is m(T) computable? We do no t answer this question. However the attempt to solve this problem led us to find sharp estimates for the intrinsic multiplicity, sharpen a result of W illiams, and solve a problem posed by Trow. (C) 2001 Elsevier Science B.V. All rights reserved.