Search

Given a finite alphabet $A$, a quasi-metric $d$ over $A^*$, and a non-negative integer $k$, we introduce the relation $\tau_{d,k}\subseteq A^*\times A^*$ such that $(x,y)\in\tau_{d,k}$ holds whenever $d(x,y)\le k$. The error detection capability of variable-length codes is expressed in term of conditions over $\tau_{d,k}$. With respect to the prefix metric, the factor one, and any quasi-metric associated with some free monoid (anti-)automorphism, we prove that one can decide whether a given regular variable-length code satisfies any of those error detection constraints., Comment: arXiv admin note: text overlap with arXiv:2208.14681

Given a binary word relation $\tau$ onto A * and a finite language X $\subseteq$ A * , a $\tau$-Gray cycle over X consists in a permutation w [i] 0$\le$i$\le$|X|--1 of X such that each word w [i] is an image under $\tau$ of the previous word w [i--1]. We define the complexity measure $\lambda$A,$\tau$ (n), equal to the largest cardinality of a language X having words of length at most n, and st. some $\tau$-Gray cycle over X exists. The present paper is concerned with $\tau$ = $\sigma$ k , the so-called k-character substitution, st. (u, v) $\in$ $\sigma$ k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length $\sigma$ k-Gray cycles., Comment: arXiv admin note: text overlap with arXiv:2108.13659

Given a finite alphabet $A$ and a binary relation $\tau\subseteq A^*\times A^*$, a set $X$ is $\tau$-{\it independent} if $ \tau(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 $\tau_{d,k}$ defined by $(x,y)\in\tau_{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 $\tau_{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.

Given a word binary relation $\tau$ we define a $\tau$-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 $\tau$. In that framework, we introduce the complexity measure $\lambda$(n), equal to the largest cardinality of a language X having words of length at most n, and such that a $\tau$-Gray cycle over X exists. The present paper is concerned with the relation $\tau$ = $\sigma$ k , the so-called k-character substitution, where (u, v) belongs to $\sigma$ k if, and only if, the Hamming distance of u and v is k. We compute the bound $\lambda$(n) for all cases of the alphabet cardinality and the argument n.

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 $\tau$-independent or $\tau$-closed codes are provided.

Given an alphabet A and a binary relation $\tau$ $\subseteq$ A * x A * , a language X $\subseteq$ A * is $\tau$-independent if $\tau$ (X) $\cap$ X = $\emptyset$; X is $\tau$-closed if $\tau$ (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 $\tau$-independent or $\tau$-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.

Let A be a finite or countable alphabet and let $\theta$ 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 $\theta$ ($\theta$-invariant for short) that is, languages L such that $\theta$ (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 $\theta$-invariant codes. Moreover, we establish a formula which allows to embed any non-complete $\theta$-invariant code into a complete one. As a consequence, in the family of the so-called thin $\theta$--invariant codes, maximality and completeness are two equivalent notions., Comment: arXiv admin note: text overlap with arXiv:1705.05564

Let $A$ be a finite or countable alphabet and let $\theta$ be literal (anti)morphism onto $A^*$ (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under $\theta$ ($\theta$-invariant for short).We establish an extension of the famous defect theorem. Moreover, we prove that for the so-called thin $\theta$-invariant codes, maximality and completeness are two equivalent notions. We prove that a similar property holds in the framework of some special families of $\theta$-invariant codes such as prefix (bifix) codes, codes with a finite deciphering delay, uniformly synchronized codes and circular codes. For a special class of involutive antimorphisms, we prove that any regular $\theta$-invariant code may be embedded into a complete one., Comment: To appear in Acts of WORDS 2017

In connection to the development of the field of Combinatorics on Words, we present a list of open problems and conjectures that were stated during the ten last meetings WORDS. We wish to continually update the present document by adding informations concerning advances in problems solving.