publication . Other literature type . Preprint . 2016

On universal partial words

Chen, Herman Z. Q.; Kitaev, Sergey; Mütze, Torsten; Sun, Brian Y.;
Open Access English
  • Published: 24 Jan 2016
  • Publisher: Episciences.org
Abstract
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 work we initiate the systematic study of universal partial words. These are words that in addition to the letters from $A$ may contain an arbitrary number of occurrences of a special `joker' symbol $\Diamond\notin A$, which can be substituted by any symbol from $A$. For example, $u=0\Diamond 011100$ is a linear partial word for the binary alphabet $A=\{0,1\}$ and for $n=3$ (e.g., the first three l...
Read more
doi: 10.23638/DMTCS-19-1-16
Subjects
arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science::Formal Languages and Automata Theory
free text keywords: Mathematics - Combinatorics, Computer Science - Information Theory, Computer Science - Formal Languages and Automata Theory
Related Organizations
View more
Download fromView all 2 versions
arXiv.org e-Print Archive
Preprint . 2016
Provider: arXiv.org e-Print Archive
http://dx.doi.org/10.23638/dmt...
Other literature type . 2017
Provider: Datacite
Episciences.org
24 references, page 1 of 2

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. [OpenAIRE]

[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. [OpenAIRE]

[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. [OpenAIRE]

[Eul36] L. Euler. Solutio problematis ad geometriam situs pertinentis. Comment. Academiae Sci. I. Petropolitanae, 8:128-140, 1736.

[Fle83] M. Fleury. Deux problemes de geometrie de situation. Journal de mathematiques elementaires, pages 257-261, 1883.

[GGG+16] B. Goeckner, N. Graber, C. Groothuis, C. Hettle, B. Kell, R. Kirsch, P. Kirkpatrick, and R. Solava. Personal communication, 2016.

[HHK08] V. Halava, T. Harju, and T. Kärki. Square-free partial words. Inform. Process. Lett., 108(5):290-292, 2008.

[HHKS09] V. Halava, T. Harju, T. Kärki, and P. Séébold. Overlap-freeness in infinite partial words. Theoret. Comput. Sci., 410(8-10):943-948, 2009. [OpenAIRE]

24 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue

publication . Other literature type . Preprint . 2016

On universal partial words

Chen, Herman Z. Q.; Kitaev, Sergey; Mütze, Torsten; Sun, Brian Y.;

Projects
Research outcomes
Communities