Quotient complexity of closed languages

Abstract. A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by subword we mean sub-sequence. We study the quotient complexity (usually called state com-plexity) of operations on prefix-, suffix-, factor-, and subword-closed lan-guages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean oper-ations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated application of positive closure and complement to a closed language results in at most four distinct languages, while Kleene closure and complement gives at most eight