Combinatorics on partial word borders
type: Item
instance of: scholarly article
title: Combinatorics on partial word borders
zbMATH Open document ID: 1347.68287
author: Emily Allen
author: F. Blanchet-Sadri
author: M. Bodnar
author: Brian Bowers
author: Joe Hidakatsu
author: John Lensmire
published in: Theoretical Computer Science
publication date: 2015-12-08T00:00:00Z
review text: A partial word contains holes that can be filled with any character of the alphabet, a border is a non-empty proper prefix that is also a suffix, and the border array contains the length of the longest border of each prefix of the word. The authors determine the maximal number of holes with specified longest border, in particular in an unbordered partial word. They also compute the number of partial words with given border array and describe the sets of possible hole positions in such words. Finally, they count the number of partial words with specified border lengths (or arrays), and they count the number of border arrays. These formulas involve the Bell numbers and the Stirling numbers of the second kind. The main tools are certain graphs: constraint graph, compatibility graph, incompatibility graph, etc. In Theorem 3.3, the formula for \(\mathrm{HSB}_k(2\ell)\) can be simplified to \(2\ell - \lceil 2 \sqrt{\ell} \rceil\).
reviewed by: Wolfgang Steiner
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6517461
zbMATH Keywords: combinatorics on words
zbMATH Keywords: partial words
zbMATH Keywords: borders
zbMATH Keywords: border arrays
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.11.006
OpenAlex ID: W2208672067
cites work: Counting bordered partial words by critical positions
cites work: The structural border array
cites work: Q3527014
cites work: How Many Holes Can an Unbordered Partial Word Contain?
cites work: New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
cites work: Border correlations of partial words
cites work: Unbordered partial words
cites work: Combinatorics on partial word correlations
cites work: Abelian borders in binary words
cites work: Algorithms on Strings
cites work: Efficient validation and construction of border arrays and validation of string matching automata
cites work: Periods in strings
cites work: Border correlation of binary words
cites work: Q4529547
cites work: Counting distinct strings
cites work: On the Number of Abelian Bordered Words
cites work: Combinatorics of periods in strings.
cites work: The enumeration of vertex induced subgraphs with respect to the number of components
cites work: Counting Parameterized Border Arrays for a Binary Alphabet
cites work: Verifying and enumerating parameterized border arrays
cites work: Q5781249
cites work: Self-describing sequences and the Catalan family tree
DOI: 10.1016/J.TCS.2015.11.006
description: scientific article; zbMATH DE number 6517461