2012/07/09 by Janusz Brzozowski, David Liu, Brzozowski, Janusz +1
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.1982
openalex publication_date 2012/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the state complexity of boolean operations and product (concatenation, catenation) combined with star. We derive tight upper bounds for the symmetric differences and differences of two languages, one or both of which are starred, and for the product of two starred languages. We prove that the previously discovered bounds for the union and the intersection of languages with one or two starred arguments, for the product of two languages one of which is starred, and for the star of the product of two languages can all be met by the recently introduced universal witnesses and their variants.