Embedding a -invariant code into a complete one

DOI10.1016/J.TCS.2018.08.022zbMATH Open1436.68183arXiv1801.05164OpenAlexW2783291246MaRDI QIDQ2285122FDOQ2285122

Authors: J. Néraud, C. Selmi 

Publication date: 16 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1801.05164

Recommendations

• Invariance: a theoretical approach for coding sets of words modulo literal (anti)morphisms
• Completing codes
• scientific article; zbMATH DE number 3926268
• On codes defined by binary relations. I: Embedding problem
• Finite Completion of comma-free codes Part 2

zbMATH Keywords

Bernoulli distributionbifix codevariable-length codeanti-automorphismantimorphismdefect theoremcontext-freecomplete code\(\theta\)-code\(\theta\)-invariant code

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Prefix, length-variable, comma-free codes (94A45) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• On a special class of primitive words
• Title not available (Why is that?)
• Uniqueness Theorems for Periodic Functions
• Circular codes and synchronization
• Pseudopalindrome closure operators in free monoids
• Watson-Crick Conjugate and Commutative Words
• DNA Codes and Their Properties
• Codes and automata.
• On codes having no finite completions
• Finding pseudo-repetitions
• An extension of the Lyndon-Schützenberger result to pseudoperiodic words
• On \(\theta\)-episturmian words
• Title not available (Why is that?)
• Each regular code is included in a maximal regular code
• Completing codes
• Construction of a family of finite maximal codes
• Fine and Wilf's theorem and pseudo-repetitions
• Generalised Lyndon-Schützenberger Equations
• On a question concerning certain free submonoids
• Sur un algorithme donnant les codes bipréfixes finis
• Equations enforcing repetitions under permutations
• Invariance: a theoretical approach for coding sets of words modulo literal (anti)morphisms

Cited In (4)

• Variable-length codes independent or closed with respect to edit relations
• Topologies for error-detecting variable-length codes
• Invariance: a theoretical approach for coding sets of words modulo literal (anti)morphisms
• When variable-length codes meet the field of error detection

This page was built for publication: Embedding a \(\theta \)-invariant code into a complete one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285122)