On universal partial words for word-patterns and set partitions

Herman Z. Q. Chen, Sergey Kitaev

Research output: Contribution to journalArticle

3 Downloads (Pure)

Abstract

Universal words are words containing exactly once each element from a given set of combinatorial structures admiting encoding by words. Universal partial words (u-p-words) contain, in addition to the letters from the alphabet in question, any number of occurrences of a special ``joker'' symbol. We initiate the study of u-p-words for word-patterns (essentially, surjective functions) and (2-)set partitions by proving a number of existence/non-existence results and thus extending the results in the literature on u-p-words and u-p-cycles for words and permutations. We apply methods of graph theory and combinatorics on words to obtain our results.
Original languageEnglish
Article number5
Number of pages14
JournalRAIRO - Theoretical Informatics and Applications
Volume54
DOIs
Publication statusPublished - 4 Jun 2020

Keywords

  • universal word
  • partial word
  • set partition
  • word-pattern
  • De Bruijn graph
  • Eulerian path
  • Hamiltonian path

Fingerprint Dive into the research topics of 'On universal partial words for word-patterns and set partitions'. Together they form a unique fingerprint.

  • Cite this

    Chen, H. Z. Q., & Kitaev, S. (2020). On universal partial words for word-patterns and set partitions. RAIRO - Theoretical Informatics and Applications, 54, [5]. https://doi.org/10.1051/ita/2020004