More on the Descriptional Complexity of Products of Finite Automata

We investigate the descriptional complexity of the ${\nu }_i$- and ${\alpha }_i$-products with $0\le i\le 2$ of two automata, for reset, permutation, permutation-reset, and finite automata in general. This is a continuation of the recent studies on the state complexity of the well-known cascade product undertaken in [7, 8]. Here we show that in almost all cases, except for the direct product (${\nu }_0$) and the cascade product (${\alpha }_0$) for certain types of automata operands, the whole range of state complexities, namely the interval $[1,nm]$, where $n$ is the state complexity of the left operand and $m$ that of the right one, is attainable. To this end we prove a simulation result on products of automata that allows us to reduce the products of automata in question to the ${\nu }_0$, ${\alpha }_0$, and a double sided ${\alpha }_0$-product.