Completing prefix codes in submonoids.

DOI10.1016/J.TCS.2006.01.027MaRDI QIDQ2490823zbMATH OpenOpenAlexFDO

Authors J. Néraud

Publication date 18 May 2006

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

Full work available at URL https://doi.org/10.1016/j.tcs.2006.01.027

zbMATH Keywords

completion of codesdecidabilityformal languagemonoidprefix coderegular codessubmonoidvariable length codes

Mathematics Subject Classification ID

Algebraic combinatorics (05E99) Formal languages and automata (68Q45) Combinatorics on words (68R15) Prefix, length-variable, comma-free codes (94A45)

Review text

The paper deals with some aspect of the weak completeness of prefix codes, defined in the work of Jean Névand and Carla Selmi [Int. J. Algebra Comput. 13, No.~5, 507--516 (2003; Zbl 1064.68076)]. For a given submonoid \(M\) of a free monoid \(A^*\), a code \(X\) is said to be weakly \(M\)-complete if and only if \(X\subseteq M\) and each word in \(M\) is a factor of some word in \(X^*\). It has been proved that for a regular submonoid \(M\)of \(A^*\) and a regular prefix code \(X\subseteq M\) the problem \textit{`Does a weakly \(M\)-complete regular prefix code containing \(X\) exist?'} is decidable. If such code exists then it is constructed by the algorithm that computes the solution of this problem.

Recommendations

• scientific article; zbMATH DE number 2143015
• Machines, Computations, and Universality
• scientific article; zbMATH DE number 5117090
• Completing circular codes in regular submonoids
• On codes having no finite completions

Cites work

• A universal algorithm for sequential data compression
• Finitely generated \(\omega\)-languages
• Finitely generated sofic systems
• FREE MONOID THEORY: MAXIMALITY AND COMPLETENESS IN ARBITRARY SUBMONOIDS
• scientific article; zbMATH DE number 5643878 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 2143015 (Why is no real title available?)
• Machines, Computations, and Universality
• Prefix-free languages as \(\omega\)-generators
• Systèmes codés. (Coded systems)

Cited in

(11)

• Description of special submonoids of the global supermonoid of a free monoid
• Completing circular codes in regular submonoids
• The completion of very thin prefix codes with degree n
• On the maximality of languages with combined types of code properties
• scientific article; zbMATH DE number 2143015 (Why is no real title available?)
• scientific article; zbMATH DE number 6453254 (Why is no real title available?)
• Completion of d-L prefix codes
• Machines, Computations, and Universality
• Three-word codes \(\{a,aba,u\}\) having a finite completion
• Three-word codes \(\{a, aba, u\}\) and \(\{a, ab, v\}\) having finite completions
• Codes and maximal monoids

This page was built for publication: Completing prefix codes in submonoids.

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