On the Irreducibility of Certain Shifts of Finite Type
スポンサーリンク
概要
- 論文の詳細を見る
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.
- The Institute of Electronics, Information and Communication Engineersの論文
著者
-
Morita Hiroyoshi
Graduate School Of Information Systems The University Of Electro-communications
-
Kobayashi Tetsuya
Graduate School Nihon University
-
MANADA Akiko
Graduate School of Information Systems, The University of Electro-Communications
-
OTA Takahiro
Department of Computer and System Engineering, Nagano Prefectural Institute of Technology
関連論文
- Transcoding-after-Smoothing System for VBR MPEG Video Streaming
- Evaluation of mutual anonymity in P2P networks (情報セキュリティ)
- Evaluation of mutual anonymity in P2P networks (情報処理)
- Evaluation of mutual anonymity in P2P networks (ワイドバンドシステム)
- Multicast Communication for Video Broadcasting Service over IPv4 Network Using IP Option(Internet)
- Derivation on Bit Error Probability of Coded QAM Using Integer Codes(Communication Theory and Signals)
- Integer Codes Correcting Single Errors of Specific Types (±e_1, ±e_2,..., ±e_s)(Communication Theory and Signals)
- Codes over the Ring of Integers Modulo m (Special Section on Information Theory and Its Applications)
- On Analysis of Acceptable Region of a Statistical Multiplexer Based on Fractional Brownian Traffic Models
- On Construction of Reversible Variable-Length Codes Including Resynchronization Markers as Codewords
- On Multiple Smoothed Transmission of MPEG4 Video Stream
- On Multiple Smoothed Transmission of MPEG Video Streams(Image Coding, Information Theory and Its Applications)
- On Trimming Codewords of Arithmetic Codes
- Reversible Distribution Converter with Finite Precision Arithmetic
- Special Section on Information Theory and Its Applications
- On Increasing the Number of Users in (t, n) Threshold Secret Sharing Schemes
- On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree(Algorithms and Data Structures)
- Perfect (2, n) Threshold Secret Sharing Systems Based on Matrices with Constant Column Weight
- Soft Decoding of Integer Codes and Their Application to Coded Modulation
- On (±1) Error Correctable Integer Codes
- B309 An Influence of Corona Discharge on Premixed Combustion in Constant Volume Vessel(Turbulent flame-2)
- On-Line Electrocardiogram Lossless Compression Using Antidictionary Codes for a Finite Alphabet
- Linear Complexity Construction of Antidictionaries
- An Upper Bound on Size of Antidictionary
- Construction of q-ary (2,n) Threshold Secret Sharing Systems
- On the Zeta Function of a Periodic-Finite-Type Shift
- On the Irreducibility of Certain Shifts of Finite Type
- Real-Time and Memory-Efficient Arrhythmia Detection in ECG Monitors Using Antidictionary Coding
- A Geographic Location-Based Distributed Routing System