Open and ClosedWords

Gabriele Fici, The Formal Language Theory Column by Giovanni Pighizzini


Combinatorics on words aims at finding deep connections between proper-
ties of sequences. The resulting theoretical findings are often used in the
design of efficient combinatorial algorithms for string processing, but may
also have independent interest, especially in connection with other areas of
discrete mathematics. The property we discuss here is, for a given finite
word, that of being closed. A finite word is called closed if it has length ≤ 1
or it contains a proper factor (substring) that occurs both as a prefix and as a
suffix but does not have internal occurrences. Otherwise the word is called
open. We illustrate several aspects of open and closed words and factors,
and propose some open problems.

Full Text:



  • There are currently no refbacks.