Avoiding substrings in compositons

MaRDI QIDQ3015585zbMATH OpenFDO

Authors Silvia Heubach, Sergey Kitaev

Publication date 13 July 2011

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

zbMATH Keywords

(auto)correlationavoidancecompositionsgenerating functionsstrings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: A classical result by Guibas and Odlyzko obtained in 1981 gives the generating function for the number of strings that avoid a given set of substrings with the property that no substring is contained in any of the others. In this paper, we give an analogue of this result for the enumeration of compositions that avoid a given set of prohibited substrings, subject to the compositions' length (number of parts) and weight. We also give examples of families of strings to be avoided that allow for an explicit formula for the generating function. Our results extend recent results by Myers on avoidance of strings in compositions subject to weight, but not length.

Recommendations

• scientific article; zbMATH DE number 7695995
• String reconstruction from substring compositions
• The subsequence composition of a string
• Pattern Avoidance and Overlap in Strings
• String Noninclusion Optimization Problems
• Substring compression problems
• scientific article; zbMATH DE number 6003273
• Solving Not-Substring Constraint withFlat Abstraction
• scientific article; zbMATH DE number 2170423

Cited in

(5)

• Forbidden substrings on weighted alphabets
• Autocorrelation and the Enumeration of Strings Avoiding a Fixed String
• scientific article; zbMATH DE number 2170423 (Why is no real title available?)
• Counting \(l\)-letter subwords in compositions
• The distribution of run lengths in integer compositions

This page was built for publication: Avoiding substrings in compositons

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