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 language | English |
---|---|
Article number | 5 |
Number of pages | 14 |
Journal | RAIRO - Theoretical Informatics and Applications (RAIRO: ITA) |
Volume | 54 |
DOIs | |
Publication status | Published - 4 Jun 2020 |
Keywords
- universal word
- partial word
- set partition
- word-pattern
- De Bruijn graph
- Eulerian path
- Hamiltonian path