On the magic number problem of the cut operation

Abstract

We investigate the state complexity of languages resulting from the cut operation of two regular languages represented by deterministic finite automata with m and n states, resp. We study the magic number problem of the cut operation and show that the entire range of complexities, up to the known upper bound, can be produced in case of binary alphabets. Moreover, we prove that in the unary case only complexities up to 2m-1 and between n and m+n-2 can be produced, while if 2m<=n-1, then complexities within the interval 2m up to n-1 cannot be reached---these non-producible numbers are called ´magic´.