雙置碼的分類

Classifications of Bifix Codes

李正竹(Zheng-Zhu Li)

指導教授 ： 蔡炎盛

中原大學/理學院/應用數學研究所/博士(2005年)

https://doi.org/10.6840/cycu200500095

摘要

在密碼學裡面雙置碼佔有非常重要和實用的地位，
這一篇論文最主要的是討論雙置碼的分類，
我們將雙置碼分成好幾類的 $m-$階嚴格內碼 (strict intercode of index $m$, $m geq 0$) 並用 $B_m(X)$ 代表所有 $m-$階嚴格內碼所成的集合.
我們研究每個 $B_m(X)$ 裡面的語言各種不同的特性.
我們也研究每個 $B_m(X)$ 裡面的語言關於零化子 (annihilator) 的特性.
對於一個雙置碼 $L$, 我們建構幾種方法來找出足碼 $m$ 使得雙置碼 $L$ 是一個 $m-$階嚴格內碼.
特別是當 $L$ 為有限語言時, 部分的方法會是一個演算法 (algorithm).
最後我們將提供許多演算法來判斷一個自動機 (automata) 能否接受各種不同的雙置碼。

關鍵字

演算法 ； 自動機 ； 雙置碼 ； 零化子 ； 密碼

並列摘要

Bifix codes are the most important and useful codes in the whole code theory.
In this dissertation we investigate the classifications of bifix codes.
We split the family of bifix codes into several subfamilies,
namely the strict intercode of index $m$ where $m geq 0$, denoted by $B_m(X)$.
We study some combinatorial properties of these languages in $B_m(X)$.
We also study the properties of annihilators of a given bifix code.
For a bifix code $L$, we constructs several methods to determine the index $m$ such that
$L$ is a strict intercode of index $m$.
Especially when $L$ is finite, some methods are algorithms.
Finally we provide some characterizations on automata
with different number of states which accept different types of codes,
such as bifix codes, infix codes, comma-codes and comma-free codes.

並列關鍵字

regular language ； algorithm ； automata ； comme-free code ； bifix code ； comma-code ； code ； intercode ； annihilator

參考文獻

[3] Clifford, A.H. and Preston, G.B., The Algebraic Theory of Semigroups,

Formal Languages and Their Relation to Automata,

Addison-Wesley, Massachusetts, (1976)

Outfix and Infix Codes and Related Classes of Languages,

Journal of Computer and System Sciences, Vol. 43, No. 3,