1. Operations on Boolean and Alternating Finite Automata
- Author
-
Jirásková, Galina
- Subjects
Computer Science - Formal Languages and Automata Theory - Abstract
We examine the complexity of basic regular operations on languages represented by Boolean and alternating finite automata. We get tight upper bounds m+n and m+n+1 for union, intersection, and difference, 2^m+n and 2^m+n+1 for concatenation, 2^n+n and 2^n+n+1 for square, m and m+1 for left quotient, 2^m and 2^m+1 for right quotient. We also show that in both models, the complexity of complementation and symmetric difference is n and m+n, respectively, while the complexity of star and reversal is 2^n. All our witnesses are described over a unary or binary alphabets, and whenever we use a binary alphabet, it is always optimal., Comment: In Proceedings AFL 2023, arXiv:2309.01126
- Published
- 2023
- Full Text
- View/download PDF