On the Irreducibility of Certain Shifts of Finite Type
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.12 pp.2415-2421
- Publication Date
- 2013/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E96.A.2415
- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)
- Category
- Sequence
Authors
Tetsuya KOBAYASHI
The University of Electro-Communications
Akiko MANADA
The University of Electro-Communications
Takahiro OTA
Nagano Prefectural Institute of Technology
Hiroyoshi MORITA
The University of Electro-Communications
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tetsuya KOBAYASHI, Akiko MANADA, Takahiro OTA, Hiroyoshi MORITA, "On the Irreducibility of Certain Shifts of Finite Type" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 12, pp. 2415-2421, December 2013, doi: 10.1587/transfun.E96.A.2415.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.2415/_p
Copy
@ARTICLE{e96-a_12_2415,
author={Tetsuya KOBAYASHI, Akiko MANADA, Takahiro OTA, Hiroyoshi MORITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Irreducibility of Certain Shifts of Finite Type},
year={2013},
volume={E96-A},
number={12},
pages={2415-2421},
abstract={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.},
keywords={},
doi={10.1587/transfun.E96.A.2415},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - On the Irreducibility of Certain Shifts of Finite Type
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2415
EP - 2421
AU - Tetsuya KOBAYASHI
AU - Akiko MANADA
AU - Takahiro OTA
AU - Hiroyoshi MORITA
PY - 2013
DO - 10.1587/transfun.E96.A.2415
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2013
AB - 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.
ER -
English
