Operational Complexity in Subregular Classes
Michaela Bobeničová, Michal Hospodár, Galina Jirásková · International Journal of Foundations of Computer Science · 2025
We study the state complexity of regular operations on the classes of combinational, singleton, finitely generated left ideal, symmetric definite, star, comet, two-sided comet, ordered, star-free, and power-separating languages. For the operations of union, intersection, concatenation, cut, positive closure, star, and reversal, we get tight upper bounds for all considered classes. The complexity of all operations on combinational languages is given by a constant function, and on singleton languages by a linear function. In most of the remaining cases, the state complexity of considered operations is either the same as in the regular case, or just slightly smaller. On the other hand, the complexity of concatenation on finitely generated left ideals and of star and positive closure on symmetric definite and star languages is much smaller than in the regular case. All our witnesses are described over a small fixed alphabet, mostly a binary one, except for witnesses for reversal on finitely generated left ideals and ordered languages.