Academic literature on the topic 'Bifix code'

A cross-bifix-free set of words is a set in which no prefix of any length of any word is the suffix of any other word in the set. A construction of cross-bifix-free sets has recently been proposed in Cheeet al.(2013) within a constant factor of optimality. We propose a Gray code for these cross-bifix-free sets and a CAT algorithm generating it. Our Gray code list is trace partitioned, that is, words with zero in the same positions are consecutive in the list.

This paper deals with insertability and mainly extractablity of codes. A code C is called insertable (or extractable) if the free submonoid C* generated by C satisfies if z, [Formula: see text] implies [Formula: see text] (or z, [Formula: see text] implies [Formula: see text]). We show that a finite insertable code is a full uniform code. On the other hand there are many finite extractable codes which are not full uniform codes. We cannot still characterize the structures of infinite extractable codes. Here we give some results on the class of infix extractable codes. First, we consider a necessary and sufficient condition whether a given infix code C is extractable or not by using the syntactic graph of the code. Secondly, we investigate the extractability for the families of other related bifix codes. We newly define the bifix codes, called e(m)-codes and [Formula: see text]-codes, and refer to the extractability of them.

The purpose of this research was to show that ternary cross bifix free code CBFS3(2m+1) and CBFS3(2m+2) achieved the maximum for every natural number m. This research was a literature review. A cross bifix free codes was constructed by using Dyck path method which achieved the maximality, that was non-expandable on binary set sequences for appropriate length. This result is obtained by partitioning members of CBFS3(2m+1) and CBFS3(2m+2) and comparing them with the maximality of CBFS2(2m+1) and CBFS2(2m+2). For small length 3, the result also shows that the code CBFS3(3) is optimal.

We study the family of rational sets of words, called completely reducible and which are such that the syntactic representation of their characteristic series is completely reducible. This family contains, by a result of Reutenauer, the submonoids generated by bifix codes and, by a result of Berstel and Reutenauer, the cyclic sets. We study the closure properties of this family. We prove a result on linear representations of monoids which gives a generalization of the result concerning the complete reducibility of the submonoid generated by a bifix code to sets called birecurrent. We also give a new proof of the result concerning cyclic sets.

We consider five operators on a regular language. Each of them is a tool for constructing a code (respectively prefix, suffix, bifix, infix) and a hypercode out of a given regular language. We give the precise values of the (deterministic) state complexity of these operators: over a constant-size alphabet for the first four of them and over a quadratic-size alphabet for the hypercode operator.

AbstractWe give necessary and sufficient conditions for the group of a rational maximal bifix code Z to be isomorphic with the F-group of {Z\cap F}, when F is recurrent and {Z\cap F} is rational. The case where F is uniformly recurrent, which is known to imply the finiteness of {Z\cap F}, receives special attention. The proofs are done by exploring the connections with the structure of the free profinite monoid over the alphabet of F.

In order to guarantee the synchronization between a transmited data by transmitter and received data by receiver can be done by periodically inserting a fixed sequence into the transmited data. It is one of the main topic in digital communication systems which called Frame Synchronization. Study of Cross Bifix Free Codes arise to solve Synchronization’s problem via distributed sequence’s method which introducted first in 2000. A Cross Bifix Free Codes is a set of sequences in which no prefix of any length of less than to of any sequences is the sufix of any sequence in the set. In 2012, a Binary Cross Bifix Free Codes was constructed by using Dyck path. In 2017, a Ternary Cross Bifix Free Codes with odd lenght was constructed, , by generalize the construction of binary cross bifix free. In this paper, will be constructed Ternary Cross Bifix Free Codes for even length, , by expand the construction of Binary Cross Bifix Free Codes.

L'étude des ensembles de mots complexité linéaire joue un rôle très important dans la théorie de combinatoire des mots et dans la théorie des systèmes dynamiques symboliques.Cette famille d'ensembles comprend les ensembles de facteurs : d'un mot Sturmien ou d'un mot d'Arnoux-Rauzy, d'un codage d'échange d'intervalle, d'un point fixe d'un morphisme primitif, etc.L'enjeu principal de cette thèse est l'étude de systèmes dynamiques minimales, définis de façon équivalente comme ensembles factoriels de mots uniformément récurrents.Comme résultat principal nous considérons une hiérarchie naturelle de systèmes minimal contenante les ensembles neutres, les tree sets et les ensembles spéculaires.De plus, on va relier ces systèmes au groupe libre en utilisant les mots de retours et les bases de sous-groupes d'indice fini.L'on étude aussi les systèmes symboliques dynamiques engendrés par les échanges d'intervalle et les involutions linéaires, ce qui nous permet d'obtenir des exemples et des interprétations géométriques des familles d'ensembles que définis dans notre hiérarchie.L'un des principal outil utilisé ici est l'étude des extensions possibles d'un mot dans un ensemble, ce qui nous permet de déterminer des propriétés telles que la complexité factorielle.Dans ce manuscrit, nous définissons le graphe d'extension, un graphe non orienté associé à chaque mot $w$ dans un ensemble $S$ qui décrit les extensions possibles de $w$ dans $S$ à gauche et à droite.Dans cette thèse, nous présentons plusieurs classes d'ensembles de mots définis par les formes possibles que les graphes d'extensions des éléments dans l'ensemble peuvent avoir.L'une des conditions les plus faibles que nous allons étudier est la condition de neutralité: un mot $w$ est neutre si le nombre de paires $(a,b)$ de lettres telles que $awb in S$ est égal au nombre de lettres $a$ tel que $aw in S$ plus le nombre de lettres $b$ tel que $wb in S$ moins 1.Un ensemble tel que chaque mot non vide satisfait la condition de neutralité est appelé un ensemble neutre.Une condition plus forte est la condition de l'arbre: un mot $w$ satisfait cette condition si son graphe d'extension est à la fois acyclique et connecté.Un ensemble est appelé un tree set si tout mot non vide satisfait cette condition.La famille de tree sets récurrents apparaît comme fermeture naturelle de deux familles d'ensembles très importants : les facteurs d'un mot d'Arnoux-Rauzy et les ensembles d'échange d'intervalle.Nous présentons également les ensembles spéculaires, une sous-famille remarquable de tree sets.Il s'agit également de sous-ensembles de groupes qui forment une généralisation naturelle des groupes libres.Ces ensembles de mots sont une généralisation abstraite des codages naturelles d'échanges d'intervalle et d'involutions linéaires.Pour chaque classe d'ensembles considéré dans cette thèse, nous montrons plusieurs résultats concernant les propriétés de fermeture (sous décodage maximale bifixe ou par rapport aux mots dérivés), la cardinalité des codes bifixes et les de mots de retour, la connexion entre mots de retour et bases du groupe libre, ainsi qu'entre les codes bifixes et les sous-groupes du groupe libre.Chacun de ces résultats est prouvé en utilisant les hypothèses les plus faibles possibles
Sets of words of linear complexity play an important role in combinatorics on words and symbolic dynamics.This family of sets includes set of factors of Sturmian and Arnoux-Rauzy words, interval exchange sets and primitive morphic sets, that is, sets of factors of fixed points of primitive morphisms.The leading issue of this thesis is the study of minimal dynamical systems, also defined equivalently as uniformly recurrent sets of words.As a main result, we consider a natural hierarchy of minimal systems containing neutral sets, tree sets and specular sets.Moreover, we connect the minimal systems to the free group using the notions of return words and basis of subroups of finite index.Symbolic dynamical systems arising from interval exchanges and linear involutions provide us geometrical examples of this kind of sets.One of the main tool used here is the study of possible extensions of a word in a set, that allows us to determine properties such as the factor complexity.In this manuscript we define the extension graph, an undirected graph associated to each word $w$ in a set $S$ which describes the possible extensions of $w$ in $S$ on the left and the right.In this thesis we present several classes of sets of words defined by the possible shapes that the graphs of elements in the set can have.One of the weakest condition that we will study is the neutrality condition: a word $w$ is neutral if the number of pairs $(a, b)$ of letters such that $awb in S$ is equal to the number of letters $a$ such that $aw in S$ plus the number of letters $b$ such that $wb in S$ minus 1.A set such that every nonempty word satisfies the neutrality condition is called a neutral set.A stronger condition is the tree condition: a word $w$ satisfies this condition if its extension graph is both acyclic and connected.A set is called a tree set if any nonempty word satisfies this condition.The family of recurrent tree sets appears as a the natural closure of two known families, namely the Arnoux-Rauzy sets and the interval exchange sets.We also introduce specular sets, a remarkable subfamily of the tree sets.These are subsets of groups which form a natural generalization of free groups.These sets of words are an abstract generalization of the natural codings of interval exchanges and of linear involutions.For each class of sets considered in this thesis, we prove several results concerning closure properties (under maximal bifix decoding or under taking derived words), cardinality of the bifix codes and set of return words in these sets, connection between return words and basis of the free groups, as well as between bifix codes and subgroup of the free group.Each of these results is proved under the weakest possible assumptions

Let A be a finite alphabet and A be the set of all finite sequences of the elements of A. A word is any member of A . A prefix code X is a set of words satisfying the prefix property, i.e., no word in the set is a prefix of any other word in the set. If X is defined as the collection of all concatenations of the words of X, then it can be seen that each of its elements can be expressed as a concatenation of the words of X in a unique manner. Any subset of A possessing this property is called a uniquely decodable code and the prefix codes constitute an important subclass of uniquely decodable codes. In our work, we look into the following questions involving prefix codes: i) We first study a parameter associated with prefix codes. For a discrete source with source distribution P, the problem of constructing a prefix code over the alphabet A with the minimum expected length is one of the earliest problems addressed in information theory. Let LD(P) (D = jAj) denote the minimum expected length of a prefix code for this source. This LD(P) is the parameter of our interest and can be seen as a function—call it the minimum expected length function LD—over the set Pn of all probability mass functions (PMF) of the form (p1; p2; : : : ; pn). It is well known that LD attains its maximum value at the uniform distribution Un = (1=n; 1=n; : : : ; 1=n). However, a characterization of all the PMFs at which this function attains a maximum value has not been carried out before, which we do in this work. This characterization also suggests the following problem: do the restrictions of LD over certain subsets of Pn attain maximum values in their respective domains? If so, what are the PMFs at which these maximum values are attained? We give a partial solution to this problem for the binary case D = 2. ii) We introduce the problem of finding a minimum expected length binary prefix code (hereafter known as an optimal code) among the prefix codes that satisfy the following constraint: all the possible concatenations of the codewords must satisfy the (d; k) runlength-limited (RLL) constraint, i.e., the number of zeros between any two successive ones in them is at least d and the length of any run of consecutive zeros is at most k. For certain (d; k) pairs, we show that this problem can be reduced to a well-studied problem of finding a prefix code with the minimum expected cost when each letter of the alphabet has a non-negative cost associated with it. Also, for these (d; k) pairs, we examine if the optimal codes satisfy a certain maximality property defined with respect to the prefix condition and the RLL constraint. iii) We then study a property of prefix codes: of it being synchronous or not. A prefix code is said to be synchronous if there exists a word x 2 A such that for all w 2 A , we have wx 2 X . Capocelli et al. (1988) have given an algorithm to determine if a given prefix code is synchronous or not, which has subsequently been improved. In our work, we devise an algorithm based on the notion of dangling suffixes, similar to the classical Sardinas-Patterson test for determining whether or not a given code is uniquely decodable. We show that our algorithm has a much better worst-case performance when compared to that 2 of the improved version of the algorithm of Capocelli et al. In this process, we also slightly improve upon the known necessary and sufficient condition for a prefix code to be synchronous. iv) Finally we look into a class of prefix codes called the bifix codes. A bifix code is a prefix code in which no codeword is a suffix of another codeword. For a finite sequence of non-decreasing natural numbers L = (l1; l2; : : : ; ln), there is no known efficient algorithm to determine the existence of a bifix code whose sequence of codeword lengths is the same as L (henceforth referred to as a bifix code for L). For a finite sequence L taking only two distinct integer values (called a two-level sequence), we show that the problem of deciding the existence of a bifix code for L can be converted to a problem of finding a particular subset of vertices from certain graphs derived from de Bruijn graphs. We then conjecture an efficient way of finding these subsets. Ahlswede’s conjecture (1996) is another problem which has led to a lot of work in the field of bifix codes. It states that if a sequence L has a Kraft sum ( P i 2􀀀li ) less than or equal to 3=4, then there exists a binary bifix code for L. This conjecture has been proved when L is a two-level sequence. We give an alternate proof of this by pointing out a new general way of constructing a bifix code for a two-level sequence L with Kraft sum less than or equal to 3=4.

博士
中原大學
應用數學研究所
93
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.