Jean Néraud

Jean Néraud

Given a finite alphabet $A$ and a binary relation $τ\subseteq A^*\times A^*$, a set $X$ is $τ$-{\it independent} if $ τ(X)\cap X=\emptyset$. Given a quasi-metric $d$ over $A^*$ (in the meaning of \cite{W31}) and $k\ge 1$, we associate the relation $τ_{d,k}$ defined by $(x,y)\inτ_{d,k}$ if, and only if, $d(x,y)\le k$ \cite{CP02}.In the spirit of \cite{JK97,N21}, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $τ_{d,k}$. With respect to the prefix metric, the factor one, and every quasi-metric associated to (anti-)automorphisms of the free monoid, we examine whether those conditions are decidable for a given regular code.

Jean Néraud

Given a word binary relation $τ$ we define a $τ$-Gray cycle over a finite language X to be a permutation w [i] 0$\le$i$\le$|X|--1 of X such that each word wi is an image of the previous word wi--1 by $τ$. In that framework, we introduce the complexity measure $λ$(n), equal to the largest cardinality of a language X having words of length at most n, and such that a $τ$-Gray cycle over X exists. The present paper is concerned with the relation $τ$ = $σ$ k , the so-called k-character substitution, where (u, v) belongs to $σ$ k if, and only if, the Hamming distance of u and v is k. We compute the bound $λ$(n) for all cases of the alphabet cardinality and the argument n.

Jean Néraud

We investigate inference of variable-length codes in other domains of computer science, such as noisy information transmission or information retrieval-storage: in such topics, traditionally mostly constant-length codewords act. The study is relied upon the two concepts of independent and closed sets. We focus to those word relations whose images are computed by applying some peculiar combinations of deletion, insertion, or substitution. In particular, characterizations of variable-length codes that are maximal in the families of $τ$-independent or $τ$-closed codes are provided.

Jean Néraud

Given an alphabet A and a binary relation $τ$ $\subseteq$ A * x A * , a language X $\subseteq$ A * is $τ$-independent if $τ$ (X) $\cap$ X = $\emptyset$; X is $τ$-closed if $τ$ (X) $\subseteq$ X. The language X is complete if any word over A is a factor of some concatenation of words in X. Given a family of languages F containing X, X is maximal in F if no other set of F can stricly contain X. A language X $\subseteq$ A * is a variable-length code if any equation among the words of X is necessarily trivial. The study discusses the relationship between maximality and completeness in the case of $τ$-independent or $τ$-closed variable-length codes. We focus to the binary relations by which the images of words are computed by deleting, inserting, or substituting some characters.

Jean Néraud, Carla Selmi

Let A be a finite or countable alphabet and let $θ$ be a literal (anti-)automorphism onto A * (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under $θ$ ($θ$-invariant for short) that is, languages L such that $θ$ (L) is a subset of L.We establish an extension of the famous defect theorem. With regards to the so-called notion of completeness, we provide a series of examples of finite complete $θ$-invariant codes. Moreover, we establish a formula which allows to embed any non-complete $θ$-invariant code into a complete one. As a consequence, in the family of the so-called thin $θ$--invariant codes, maximality and completeness are two equivalent notions.