Counting Bordered Partial Words by Critical Positions


Emily Allen, F.Blanchet-Sadri, Cameron Byrum,

Mihai Cucuringu, and Robert MercaƟ

A partial word, 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. In this paper, we investigate the number of bordered partial words having h holes with the parameters k, n. 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 is made extremely more difficult by the failure of that combinatorial property since there is now the possibility of a minimal border that is nonsimple. Here we give elegant recursive formulas based on our approach of the so-called simple and nonsimple critical positions.

Keywords:  Theory of formal languages; Number theory; Combinatorics on words; Partial words; Bordered partial words; Simple border; Simply bordered partial words; Critical positions.

Implementations and web pages by Jonathan T. Britton and Yuan Kong.

Valid XHTML 1.0! Valid CSS!

This Page Has Been Accessed  counter Times Since...