Descriptional Complexity of Bounded Regular Languages
Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt · Journal of automata, languages and combinatorics · 2017
We investigate the descriptional complexity of the subregular language classes of (strongly) bounded regular languages. In the first part, we study the costs for the determinization of nondeterministic finite automata accepting bounded and strongly bounded regular languages. In both cases the upper bound for the costs is larger than the costs for determinizing unary regular languages, but lower than the costs for determinizing arbitrary regular languages. In the second part, we study for (strongly) bounded languages the deterministic operational state complexity of the Boolean operations as well as the operations reversal, concatenation, and iteration. We present upper and lower bounds, where the lower bounds are obtained for automata with fixed alphabet size. Finally, we consider as a ``worst-case scenario'' deterministic finite automata having non-fixed alphabet sizes and present upper and lower bounds for this setting. For the proof of the lower bounds we develop a tool that exploits the number of different colorings of cycles occurring in deterministic finite automata accepting bounded languages. One application of this tool shows that the upper bound for iteration is tight.