Open and Closed Words

Abstract

Combinatorics on words aims at finding deep connections between properties 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.