Universal partial words over non-binary alphabets

DOI10.1016/J.TCS.2017.12.022MaRDI QIDQ1694683zbMATH OpenOpenAlexWikidataFDO

Authors Bennet Goeckner, Corbin Groothuis, Cyrus Hettle, Brian Kell, Pamela Kirkpatrick, Ryan Solava, Rachel Kirsch

Publication date 6 February 2018

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

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

zbMATH Keywords

combinatorics on wordsuniversal cyclespartial word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: Chen, Kitaev, M"{u}tze, and Sun recently introduced the notion of universal partial words, a generalization of universal words and de Bruijn sequences. Universal partial words allow for a wild-card character $diamond$, which is a placeholder for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic $diamond$ structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size.

Recommendations

• On universal partial words
• On universal partial words
• Minimum number of holes in unavoidable sets of partial words of size three
• On universal partial words for word-patterns and set partitions
• Periodicity properties on partial words

Cites work

• Border correlations, lattices, and the subgraph component polynomial
• Counting bordered partial words by critical positions
• On universal partial words
• Unavoidable sets of partial words
• Universal cycles for combinatorial structures

Cited in

(12)

• On shortening u-cycles and u-words for permutations
• On quasi-universal word functions
• Binary de Bruijn partial words with one hole
• Absent Subsequences in Words
• Matching patterns with variables under Simon's congruence
• On universal partial words for word-patterns and set partitions
• On universal partial words
• On universal partial words
• scientific article; zbMATH DE number 3972221 (Why is no real title available?)
• Graph universal cycles: compression and connections to universal cycles
• Scattered Factor-Universality of Words
• Shortened universal cycles for permutations

This page was built for publication: Universal partial words over non-binary alphabets

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