Embedding a -invariant code into a complete one

DOI10.1016/J.TCS.2018.08.022MaRDI QIDQ2285122zbMATHOpenAlexFDO

Publication date 16 January 2020

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

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

Bernoulli distribution bifix code variable-length code anti-automorphism antimorphism defect theorem context-free complete 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)

Abstract: Let A be a finite or countable alphabet and let

h e t a

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

h e t a

(

h e t a

-invariant for short) that is, languages L such that

h e t a

(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

h e t a

-invariant codes. Moreover, we establish a formula which allows to embed any non-complete

h e t a

-invariant code into a complete one. As a consequence, in the family of the so-called thin

h e t a

--invariant codes, maximality and completeness are two equivalent notions.

Recommendations

Cites work

Cited in

(4)

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)