Quotient complexity of bifix-, factor-, and subword-free languages. http://arxiv.org/abs/1006.4843v3

A language L is prefix-free if, whenever words u and v are in L and u is a prefix of v, then u = v. Suffix-, factor-, and subword-free languages are defined similarly, where “subword ” means “subsequence”. A language is bifix-free if it is both prefix- and suffix-free. We study the quotient com-plexity, more commonly known as state complexity, of operations in the classes of bifix-, factor-, and subword-free regular languages. We find tight upper bounds on the quotient complexity of intersection, union, difference, symmetric difference, concatenation, star, and reversal in these three classes of languages.