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]

Abstract: Let M be a submonoid of the free monoid , and let be a variable length code (for short a code). X is weakly M-complete if any word in M is a factor of some word in [J. Néraud, C. Selmi, Free monoid theory: maximality and completeness in arbitrary submonoids, Internat. J. Algorithms Comput. 13(5) (2003) 507–516]. Given a code , we are interested in the construction of a weakly M-complete code that contains X, if it exists. In the case where M and X are regular sets, the existence of such a code has been established [J. Néraud, Completing a code in a regular submonoid of the free monoid, in acts of MCU’2004, Lecture Notes in Computer Sciences, Vol. 3354, Springer, Berlin, 2005, pp. 281–291; J. Néraud, On the completion of codes in submonoids with finite rank, Fund. Inform., to appear]. Actually, this result lays upon a method of construction that preserves the regularity of sets. As well known, any regular (or finite) code may be embedded into a regular (finite) prefix code that is complete in . In the framework of the weak completeness, we prove that the following problem is decidable: Instance: A regular submonoid M of , and a regular (or finite) prefix code . Question: Does a weakly M-complete regular (finite) prefix code containing X exist? [Copyright &y& Elsevier]