Universal Partial Words over Non-Binary Alphabets

Preprint English OPEN
Goeckner, Bennet; Groothuis, Corbin; Hettle, Cyrus; Kell, Brian; Kirkpatrick, Pamela; Kirsch, Rachel; Solava, Ryan;
  • Related identifiers: doi: 10.1016/j.tcs.2017.12.022
  • Subject: 68R15 | Mathematics - Combinatorics
    arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) | Computer Science::Formal Languages and Automata Theory

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 alph... View more
  • References (6)

    [1] Emily Allen, Francine Blanchet-Sadri, Cameron Byrum, Mihai Cucuringu, and Robert Mercas. Counting bordered partial words by critical positions. the electronic journal of combinatorics, 18(P138):1, 2011.

    [2] Francine Blanchet-Sadri, Naomi C Brownstein, Andy Kalcic, Justin Palumbo, and Tracy Weyand. Unavoidable sets of partial words. Theory of Computing Systems, 45(2):381-406, 2009.

    [3] Francine Blanchet-Sadri, Michelle Cordier, and Rachel Kirsch. Border correlations, lattices, and the subgraph component polynomial. In Combinatorial Algorithms, volume 8986 of Lecture Notes in Comput. Sci., pages 62-73. Springer, Cham, 2015.

    [4] Herman ZQ Chen, Sergey Kitaev, Torsten Mu¨tze, and Brian Y Sun. On universal partial words over binary alphabets. arXiv preprint arXiv:1601.06456v2, 2016.

    [5] Herman ZQ Chen, Sergey Kitaev, and Brian Y Sun. On universal partial words over binary alphabets. arXiv preprint arXiv:1601.06456, 2016.

    [6] Fan Chung, Persi Diaconis, and Ron Graham. Universal cycles for combinatorial structures. Discrete Mathematics, 110(1-3):43-59, 1992.

  • Metrics
Share - Bookmark