More on the Descriptional Complexity of Products of Finite Automata
Markus Holzer, Christian Rauch · International Journal of Foundations of Computer Science · 2024
We investigate the descriptional complexity of the [Formula: see text]- and [Formula: see text]-products with [Formula: see text] 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 ([Formula: see text]) and the cascade product ([Formula: see text]) for certain types of automata operands, the whole range of state complexities, namely the interval [Formula: see text], 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 [Formula: see text], [Formula: see text], and a double sided [Formula: see text]-product.