Squares and primitivity in partial words

DOI10.1016/j.dam.2014.12.003zbMath1311.05087MaRDI QIDQ2341712

Xufan Zhang, Michelle Bodnar, Jordan Nikkel, J. D. Quigley, Francine Blanchet-Sadri

Publication date: 28 April 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.12.003

zbMATH Keywords

combinatorics on words; partial words; primitive partial words; subgraph component polynomial; primitively-rooted squares

Mathematics Subject Classification ID

05C31: Graph polynomials

05A15: Exact enumeration problems, generating functions

68R15: Combinatorics on words

68R10: Graph theory (including graph drawing) in computer science

Related Items

Constructing Words with High Distinct Square Densities, Efficient enumeration of non-equivalent squares in partial words with few holes, The square density of words having a sequence of FS-double squares, Border correlations, lattices, and the subgraph component polynomial, Computing primitively-rooted squares and runs in partial words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The enumeration of vertex induced subgraphs with respect to the number of components
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Repetitions in strings: algorithms and combinatorics
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• The exact number of squares in Fibonacci words
• On the language of primitive words
• Squares in partial words
• Primitive partial words
• An O(n log n) algorithm for finding all repetitions in a string
• A note on the number of squares in a partial word with one hole
• Generalized String Matching
• A Graph Polynomial Approach to Primitivity
• On the number of squares in partial words
• Algorithmic Combinatorics on Partial Words