On universal partial words

Preprint English OPEN
Chen, Herman Z. Q.; Kitaev, Sergey; Mütze, Torsten; Sun, Brian Y.; (2016)
  • Related identifiers: doi: 10.23638/DMTCS-19-1-16
  • Subject: Mathematics - Combinatorics | Computer Science - Information Theory | Computer Science - Formal Languages and Automata Theory
    arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) | Computer Science::Formal Languages and Automata Theory
A universal word for a finite alphabet $A$ and some integer $n\geq 1$ is a word over $A$ such that every word in $A^n$ appears exactly once as a subword (cyclically or linearly). It is well-known and easy to prove that universal words exist for any $A$ and $n$. In this ... View more
  • References (24)
    24 references, page 1 of 3

    Theoret. Comput. Sci., 218(1):135-141, 1999. WORDS (Rouen, 1997).

    [BBSGR10] B. Blakeley, F. Blanchet-Sadri, J. Gunter, and N. Rampersad. On the complexity of deciding avoidability of sets of partial words. Theoret. Comput. Sci., 411(49):4263-4271, 2010.

    [BJG08] J. Bang-Jensen and G. Z. Gutin. Digraphs: Theory, Algorithms and Applications. Springer, 2nd edition, 2008.

    [BS05] F. Blanchet-Sadri. Primitive partial words. Discrete Applied Mathematics, 148(3):195-213, 2005.

    [BS08] F. Blanchet-Sadri. Open problems on partial words. In G. Bel-Enguix, M. D. Jiménez-López, and C. Martín-Vide, editors, New Developments in Formal Languages and Applications, pages 11-58. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.

    [BSBK+09] F. Blanchet-Sadri, N. C. Brownstein, A. Kalcic, J. Palumbo, and T. Weyand. Unavoidable sets of partial words. Theory Comput. Syst., 45(2):381-406, 2009.

    [CDG92] F. Chung, P. Diaconis, and R. Graham. Universal cycles for combinatorial structures. Discrete Math., 110(1-3):43-59, 1992.

    [CJJK11] A. Claesson, V. Jelínek, E. Jelínková, and S. Kitaev. Pattern avoidance in partial permutations. Electron. J. Combin., 18(1):Paper 25, 41, 2011.

    [CPT11] P. E. C. Compeau, P. A. Pevzner, and G. Tesler. How to apply De Bruijn graphs to genome assembly. Nature biotechnology, 29(11):987-991, 2011.

    [dB46] N. G. de Bruijn. A Combinatorial Problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 49:758-764, 1946.

  • Metrics
    No metrics available
Share - Bookmark