Quotient complexity of ideal languages (Q1935811)

In this paper, regular languages generated by a set of words in four different ways are considered: as a left ideal, as a right ideal, as a two-sided ideal, and by inserting letters arbitrarily. Precise state complexity of the following operations is calculated: generating such a language from an arbitrary set and from the minimal generating set, computing the minimal generating set of such a language (with the exception of languages of the fourth type), and basic language-theoretic operations with languages of one of these types. The upper bounds are achieved by straightforward constructions, tightness of these bounds is proved by standard methods using languages over alphabets with varying number of letters.