On universal partial words

Herman Z.Q. Chen, Sergey Kitaev, Torsten Mutze, Brian Y. Sun

Research output: Contribution to journalConference Contribution

Abstract

A universal word for a finite alphabet A and some integer n≥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. 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 ◊  A, which can be substituted by any symbol from A. For example, u = 0◊011100 is a universal partial word for the binary alphabet A = {0,1} and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer. 

Fingerprint

Partial Words
Subword
Nonexistence
Consecutive
Binary
Integer
Arbitrary

Keywords

  • universal words
  • joker symbol
  • binary alphabet

Cite this

Chen, H. Z. Q., Kitaev, S., Mutze, T., & Sun, B. Y. (Accepted/In press). On universal partial words. Electronic Notes in Discrete Mathematics.
Chen, Herman Z.Q. ; Kitaev, Sergey ; Mutze, Torsten ; Sun, Brian Y. / On universal partial words. In: Electronic Notes in Discrete Mathematics. 2017.
@article{e6f768bac0994d0e8b98985aee165b51,
title = "On universal partial words",
abstract = "A universal word for a finite alphabet A and some integer n≥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. 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 ◊  A, which can be substituted by any symbol from A. For example, u = 0◊011100 is a universal partial word for the binary alphabet A = {0,1} and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer. ",
keywords = "universal words, joker symbol, binary alphabet",
author = "Chen, {Herman Z.Q.} and Sergey Kitaev and Torsten Mutze and Sun, {Brian Y.}",
year = "2017",
month = "4",
day = "29",
language = "English",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",

}

On universal partial words. / Chen, Herman Z.Q.; Kitaev, Sergey; Mutze, Torsten; Sun, Brian Y.

In: Electronic Notes in Discrete Mathematics, 29.04.2017.

Research output: Contribution to journalConference Contribution

TY - JOUR

T1 - On universal partial words

AU - Chen, Herman Z.Q.

AU - Kitaev, Sergey

AU - Mutze, Torsten

AU - Sun, Brian Y.

PY - 2017/4/29

Y1 - 2017/4/29

N2 - A universal word for a finite alphabet A and some integer n≥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. 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 ◊  A, which can be substituted by any symbol from A. For example, u = 0◊011100 is a universal partial word for the binary alphabet A = {0,1} and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer. 

AB - A universal word for a finite alphabet A and some integer n≥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. 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 ◊  A, which can be substituted by any symbol from A. For example, u = 0◊011100 is a universal partial word for the binary alphabet A = {0,1} and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer. 

KW - universal words

KW - joker symbol

KW - binary alphabet

UR - http://www.dmg.tuwien.ac.at/eurocomb2017/

UR - http://www.sciencedirect.com/science/journal/15710653

M3 - Conference Contribution

JO - Electronic Notes in Discrete Mathematics

T2 - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -