For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Irreducibility of Certain Shifts of Finite Type
Tetsuya KOBAYASHI Akiko MANADA Takahiro OTA Hiroyoshi MORITA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/12/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
irreducibility, shift of finite type, minimal forbidden word, antidictionary, sofic shift,
Full Text: PDF(580KB)>>
A shift of finite type (SFT) is a set of all bi-infinite sequences over some alphabet which is characterized by a finite set of forbidden words. It is a typical example of sofic shifts and has been used in media storage area, such as CD's or DVD's. The study of sofic shifts is based on graph theory, and the irreducibility of shifts is an important property to be considered for the study. In this paper, we will provide some sufficient conditions for an SFT to be irreducible from the perspective of the antidictionary of a word and the number of forbidden words. We also present a necessary and sufficient condition for an SFT to be irreducible when the number of forbidden words is one less than the alphabet size.