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 |
