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   Vol.E96-A   No.12   pp.2415-2421
Publication Date: 2013/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.2415
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Sequence
irreducibility,  shift of finite type,  minimal forbidden word,  antidictionary,  sofic shift,  

Full Text: PDF(580KB)>>
Buy this Article

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.