On unavoidable sets of word patterns

Burstein, Alexander and Kitaev, Sergey (2005) On unavoidable sets of word patterns. SIAM Journal on Discrete Mathematics, 19 (2). pp. 371-381. ISSN 1095-7146 (https://doi.org/10.1137/S0895480104445678)

Abstract

We introduce the notion of unavoidable (complete) sets of word patterns, which is a refinement for that of words, and study certain numerical characteristics for unavoidable sets of patterns. In some cases we employ the graph of pattern overlaps introduced in this paper, which is a subgraph of the de Bruijn graph and which we prove to be Hamiltonian. In other cases we reduce a problem under consideration to known facts on unavoidable sets of words. We also give a relation between our problem and intensively studied universal cycles, and prove there exists a universal cycle for word patterns of any length over any alphabet.

• Share and Export
  

  RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomSimple MetadataReferMETSHTML CitationASCII CitationOpenURL ContextObjectEndNoteOpenURL ContextObject in SpanMODSMPEG-21 DIDLEP3 XMLData Cite XMLRIS (EndNote Online, Zotero, Ref manager, etc)RDF+N3Multiline CSV
• Item metadata

  Item type:	Article
  ID code:	49799
  Dates:	Date Event 2005 Published
  Subjects:	Science > Mathematics > Electronic computers. Computer science
  Department:	Faculty of Science > Computer and Information Sciences
  Depositing user:	Pure Administrator
  Date deposited:	14 Oct 2014 14:32
  Last modified:	08 Apr 2024 21:43
  Related URLs:	http://arxiv.org/abs/math/0311399
  URI:	https://strathprints.strath.ac.uk/id/eprint/49799