On a structural property in the state complexity of projected regular languages (Q443744)

Finite automata are useful tools for modeling systems: input symbols represent events that can occur in a system and change its status. Usually ``real'' systems have a huge number of states and, hence, the corresponding automata, even if finite, cannot be depicted in a readable and useful way. Many times, however, people are interested in considering not all possible events, but to emphasize only some of them, considering the remaining as internal changes. This leads to the investigation of so-called projected regular languages: from a language \(L\) over an alphabet \(\Sigma\), the projected language over \(\Sigma_0\subseteq\Sigma\) is the language obtained by removing from each string of \(L\) the symbols not belonging to \(\Sigma_0\). Clearly, this operation preservers regularity. If \(L\) is accepted by a deterministic automaton with \(n\) states, what can be said about the states of the minimal deterministic automaton accepting the projection of~\(L\)? Using standard techniques it can be proved that this ``simplification'' in the alphabet can lead to an exponential increase in the number of states. In the paper under review, tight upper bounds for the state complexity of the projection are stated. In particular, these bounds are obtained by taking into account the number of states of the minimal deterministic automaton accepting the given language \(L\), together with the number of states which are incident with the transitions which become unobservable. The paper also present some interesting future lines of research on the topic.