Counting bordered partial words by critical positions
Summary: A partial word, a sequence over a finite alphabet that may have some undefined positions or holes, is bordered if one of its proper prefixes is compatible with one of its suffixes. The number-theoretical problem of enumerating all bordered full words (the ones without holes) of a fixed length \(n\) over an alphabet of a fixed size \(k\) is well-known. It turns out that all borders of a full word are simple, and so every bordered full word has a unique minimal border no longer than half its length. Counting bordered partial words having \(h\) holes with the parameters \(k\), \(n\) is made extremely more difficult by the failure of that combinatorial property since there is now the possibility of a minimal border that is non-simple. Here, we give recursive formulas based on our approach of the so-called simple and non-simple critical positions.
- Border correlations, lattices, and the subgraph component polynomial
- Universal partial words over non-binary alphabets
- The hardness of counting full words compatible with partial words
- Fully bordered words
- Counting bordered and primitive words with a fixed weight
- Border correlations, lattices, and the subgraph component polynomial
- How Many Holes Can an Unbordered Partial Word Contain?
- Counting Parameterized Border Arrays for a Binary Alphabet
- Enumeration of bordered words, le langage de la vache-qui-rit
- Dyck Words, Lattice Paths, and Abelian Borders
- A connection between unbordered partial words and sparse rulers
- Combinatorics on partial word borders
This page was built for publication: Counting bordered partial words by critical positions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551232)
