Irina Gheorghiciuc ; Mark Daniel Ward - On Correlation Polynomials and Subword Complexity

dmtcs:3553 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3553
On Correlation Polynomials and Subword ComplexityArticle

Authors: Irina Gheorghiciuc 1; Mark Daniel Ward 2

  • 1 Department of Mathematical Sciences
  • 2 Department of Mathematics [Philadelphia]

We consider words with letters from a $q-ary$ alphabet $\mathcal{A}$. The kth subword complexity of a word $w ∈\mathcal{A}^*$ is the number of distinct subwords of length $k$ that appear as contiguous subwords of $w$. We analyze subword complexity from both combinatorial and probabilistic viewpoints. Our first main result is a precise analysis of the expected $kth$ subword complexity of a randomly-chosen word $w ∈\mathcal{A}^n$. Our other main result describes, for $w ∈\mathcal{A}^*$, the degree to which one understands the set of all subwords of $w$, provided that one knows only the set of all subwords of some particular length $k$. Our methods rely upon a precise characterization of overlaps between words of length $k$. We use three kinds of correlation polynomials of words of length $k$: unweighted correlation polynomials; correlation polynomials associated to a Bernoulli source; and generalized multivariate correlation polynomials. We survey previously-known results about such polynomials, and we also present some new results concerning correlation polynomials.


Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: combinatorics on words,average-case analysis,autocorrelation,asymptotics,Analytic methods,correlation polynomial,de \\Bruijn graph,depth,subword complexity,suffix trees.,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • Asymptotic enumeration, reinforcement, and effective limit theory; Funder: National Science Foundation; Code: 0603821

3 Documents citing this article

Consultation statistics

This page has been seen 245 times.
This article's PDF has been downloaded 197 times.