Narrow Results

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.

The purpose of this paper is to introduce the notion of several kinds of products of rough transformation semigroups. We establish relationship through coverings and investigate some algebraic properties with regard to these products.

We investigate the state complexity of languages resulting from the cascade product of two minimal deterministic finite automata with $n$ and $m$ states, respectively. More precisely we study the magic number problem of the cascade product operation and show what range of complexities can be produced in case the left automaton is unary, that is, has only a singleton letter alphabet. Here we distinguish the cases when the involved automata are reset automata, permutation automata, permutation-reset automata, or do not have any restriction on their structure. It turns out that the picture on the obtained state complexities of the cascade product is diverse, and for all cases, except where the left automaton is a unary permutation(-reset) or a deterministic finite automaton without structural restrictions, and the right one is a reset automaton or a deterministic finite automaton without structural restrictions, we are able to identify state sizes that cannot be reached — these numbers are called “magic.”