Operations on Boolean and Alternating Finite Automata

We investigate the descriptional complexity of basic regular operations on languages represented by Boolean and alternating finite automata. In particular, we consider the operations of difference, symmetric difference, star, reversal, left quotient, and right quotient, and get tight upper bounds m + n, m + n, 2(n), 2(n), m, and 2(m), respectively, for Boolean automata, and m + n + 1, m + n, 2(n), 2(n), m + 1, and 2(m) + 1, respectively, for alternating finite automata. To describe witnesses for symmetric difference, we use a ternary alphabet. All the remaining witnesses are defined over binary or unary alphabets that are shown to be optimal.