Search

• Given an alphabet A , and an (anti-)automorphism θ , a set L ⊆ A ⁎ is θ -invariant if θ (L) = L. • In the framework of θ -invariant sets, a defect effect is highlighted. • Several non-trivial examples of finite complete θ -invariant codes are presented. • Over a finite alphabet, any regular non complete θ -invariant code can be embedded into a complete one. • Given a thin θ -invariant code, being a maximal code, or being maximal in the family of θ -invariant codes, or being complete are equivalent properties. Let A be an arbitrary alphabet and let θ be an (anti-)automorphism of 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 satisfying θ (L) ⊆ L. We establish an extension of the famous defect theorem. With regard 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. [ABSTRACT FROM AUTHOR]

Girod's encoding method has been introduced in order to efficiently decode from both directions messages encoded by using finite prefix codes. In the present paper, we generalize this method to finite codes with a finite deciphering delay. In particular, we show that our decoding algorithm can be realized by a deterministic finite transducer. We also investigate some properties of the underlying unlabeled graph. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the different notions of local topological density for subsets of the free monoid A*. We introduce the notion of weak completeness for a set X, relatively to an arbitrary submonoid M of A*. For the so-called strongly M-thin codes, we establish that weak completeness is equivalent to maximality in M. This constitutes a new generalization of a famous result due to Schützenberger. [ABSTRACT FROM AUTHOR]