### Efficiency of automata in semi-commutation verification techniques

Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani et al. [IEEE Comput. Soc. (2001) 399–408] proved that the class of regular languages $L$ – called APC – of the form ${\cup}_{j}$ ${L}_{0,j}$ ${L}_{1,j}$ ${L}_{2,j}$ $...$ ${L}_{{k}_{j},j}$, where the union is finite and each ${L}_{i,j}$ is either a single symbol or a language of the form ${B}^{*}$ with $B$ a subset of the alphabet, is closed under...