On the magic number problem of the cut operation
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
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´.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 1703