The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] shift of finite type(1hit)

1-1hit
  • On the Irreducibility of Certain Shifts of Finite Type

    Tetsuya KOBAYASHI  Akiko MANADA  Takahiro OTA  Hiroyoshi MORITA  

     
    PAPER-Sequence

      Vol:
    E96-A No:12
      Page(s):
    2415-2421

    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.