View in EDS PDF Full Text

On Unavoidable Sets of Word Patterns.

Saved in:
Bibliographic Details
Title: On Unavoidable Sets of Word Patterns.
Authors: Burstein, Alexander1 burstein@orion.math.iastate.edu, Kitaev, Sergey2 kitaev@ms.uky.edu
Source: SIAM Journal on Discrete Mathematics. 2005, Vol. 19 Issue 2, p371. 11p. 3 Diagrams, 1 Chart.
Subjects: Programming languages, Character sets (Data processing), Alphabet -- Data processing, Möbius function, Mathematical programming, Computer programming, Computational mathematics
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 the extensively studied universal cycles and prove that there exists a universal cycle for word patterns of any length over any alphabet. The Stirling numbers of the second kind and the Mobius function appear in our results. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 18907025
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On Unavoidable Sets of Word Patterns.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Burstein%2C+Alexander%22">Burstein, Alexander</searchLink><relatesTo>1</relatesTo><i> burstein@orion.math.iastate.edu</i><br /><searchLink fieldCode="AR" term="%22Kitaev%2C+Sergey%22">Kitaev, Sergey</searchLink><relatesTo>2</relatesTo><i> kitaev@ms.uky.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Discrete+Mathematics%22">SIAM Journal on Discrete Mathematics</searchLink>. 2005, Vol. 19 Issue 2, p371. 11p. 3 Diagrams, 1 Chart.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Programming+languages%22">Programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Character+sets+%28Data+processing%29%22">Character sets (Data processing)</searchLink><br /><searchLink fieldCode="DE" term="%22Alphabet+--+Data+processing%22">Alphabet -- Data processing</searchLink><br /><searchLink fieldCode="DE" term="%22Möbius+function%22">Möbius function</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+programming%22">Mathematical programming</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programming%22">Computer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+mathematics%22">Computational mathematics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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 the extensively studied universal cycles and prove that there exists a universal cycle for word patterns of any length over any alphabet. The Stirling numbers of the second kind and the Mobius function appear in our results. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=18907025
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/S0895480104445678
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 11
        StartPage: 371
    Subjects:
      – SubjectFull: Programming languages
        Type: general
      – SubjectFull: Character sets (Data processing)
        Type: general
      – SubjectFull: Alphabet -- Data processing
        Type: general
      – SubjectFull: Möbius function
        Type: general
      – SubjectFull: Mathematical programming
        Type: general
      – SubjectFull: Computer programming
        Type: general
      – SubjectFull: Computational mathematics
        Type: general
    Titles:
      – TitleFull: On Unavoidable Sets of Word Patterns.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Burstein, Alexander
      – PersonEntity:
          Name:
            NameFull: Kitaev, Sergey
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 22
              M: 11
              Text: 2005
              Type: published
              Y: 2005
          Identifiers:
            – Type: issn-print
              Value: 08954801
          Numbering:
            – Type: volume
              Value: 19
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: SIAM Journal on Discrete Mathematics
              Type: main
ResultId 1