Universal cycles of complementary classes

MaRDI QIDQ5405460zbMATH OpenFDO

Authors Michelle Champlin, Anant P. Godbole, Beverly Tomlinson

Publication date 2 April 2014

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

zbMATH Keywords

class-alternating wordsU-cycles

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: Universal Cycles, or U-cycles, as originally defined by de Bruijn, are an efficient method to exhibit a large class of combinatorial objects in a compressed fashion, and with no repeats. de Bruijn's theorem states that U-cycles for $n$ letter words on a $k$ letter alphabet exist for all $k$ and $n$. Much has already been proved about Universal Cycles for a variety of other objects. This work is intended to augment the current research in the area by exhibiting U-cycles for {it complementary classes}. Results will be presented that exhibit the existence of U-cycles for class-alternating words such as alternating vowel-consonant (VCVC) words; words with at least one repeated letter (non-injective functions); words with at least one letter of the alphabet missing (functions that are not onto); words that represent illegal tournament rankings; and words that do not constitute "strong" legal computer passwords. As with previous papers pertaining to U-cycles, connectedness proves to be a nontrivial step.

Recommendations

• Universal cycles of classes of restricted words
• Universal cycles for combinatorial structures
• Universal cycles for permutations
• On universal cycles for new classes of combinatorial structures
• Universal cycles of restriced words

Cited in

(10)

• Universal cycles for combinatorial structures
• Classifying rotationally-closed languages having greedy universal cycles
• On universal cycles of labeled graphs
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Universal and overlap cycles for posets, words, and juggling patterns
• scientific article; zbMATH DE number 3855267 (Why is no real title available?)
• Universal Cycles of Discrete Functions
• Universal cycles of restriced words
• Graph universal cycles: compression and connections to universal cycles
• Universal cycles of classes of restricted words

This page was built for publication: Universal cycles of complementary classes

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