2009/08/14 by Janusz Brzozowski, Brzozowski, J., Galina Jirásková +3
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0908.2083
openalex publication_date 2009/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the state complexity of regular operations in the class of ideal languages. A language L over an alphabet Sigma is a right (left) ideal if it satisfies L = L Sigma* (L = Sigma* L). It is a two-sided ideal if L = Sigma* L Sigma *, and an all-sided ideal if it is the shuffle of Sigma* with L. We prefer the term "quotient complexity" instead of "state complexity", and we use derivatives to calculate upper bounds on quotient complexity, whenever it is convenient. We find tight upper bounds on the quotient complexity of each type of ideal language in terms of the complexity of an arbitrary generator and of its minimal generator, the complexity of the minimal generator, and also on the operations union, intersection, set difference, symmetric difference, concatenation, star and reversal of ideal languages.