State Complexity of the Minimal Star Basis

Let L be a regular language not containing \(\varepsilon \) . We determine the state complexity of the two operations \(L \rightarrow L L^+\) and \(L \rightarrow L \setminus L L^+\) . The latter is of interest because \(L \setminus L L^+\) is the “minimal star basis”, the set of all strings of L that cannot be written as the concatenation of shorter strings of L, a concept first studied by John Brzozowski in 1966.