publication . Preprint . Article . Other literature type . 2017

On universal partial words

Brian Y. Sun; Sergey Kitaev; Torsten Mütze; Herman Z.Q. Chen;
Open Access English
  • Published: 05 May 2017
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 , 10.1016/j.endm.2017.06.043
Subjects
arXiv: Computer Science::Formal Languages and Automata TheoryComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
free text keywords: Mathematics - Combinatorics, Computer Science - Formal Languages and Automata Theory, Computer Science - Information Theory, Applied Mathematics, Discrete Mathematics and Combinatorics, QA, QA75, Partial word, De Bruijn graph, symbols.namesake, symbols, Eulerian path, Alphabet, Discrete mathematics, Symbol, media_common.quotation_subject, media_common, Binary alphabet, Integer, Combinatorics, Hamiltonian path, Mathematics
Related Organizations
View more
Download fromView all 5 versions
arXiv.org e-Print Archive
Preprint . 2016
Provider: arXiv.org e-Print Archive
Strathprints
Article . 2017
Provider: CORE (RIOXX-UK Aggregator)
Strathprints
Article . 2017
Provider: CORE (RIOXX-UK Aggregator)
http://dx.doi.org/10.23638/dmt...
Other literature type . 2017
Provider: Datacite
View more
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. [OpenAIRE]

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

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

[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 Research Graph
Any information missing or wrong?Report an Issue