On the magic number problem of the cut operation
Dateien zu dieser Ressource
Datum
2017Autor
Holzer, Markus
Hospodár, Michal
Zitierlink
http://dx.doi.org/10.22029/jlupub-6983Zusammenfassung
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´.