On the magic number problem of the cut operation
| dc.contributor.author | Holzer, Markus | |
| dc.contributor.author | Hospodár, Michal | |
| dc.date.accessioned | 2022-09-12T09:38:41Z | |
| dc.date.available | 2017-11-20T11:12:28Z | |
| dc.date.available | 2022-09-12T09:38:41Z | |
| dc.date.issued | 2017 | |
| dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-132716 | |
| dc.identifier.uri | https://jlupub.ub.uni-giessen.de//handle/jlupub/7549 | |
| dc.identifier.uri | http://dx.doi.org/10.22029/jlupub-6983 | |
| dc.description.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´. | en |
| dc.language.iso | en | de_DE |
| dc.relation.ispartofseries | IFIG Research Report; 1703 | |
| dc.rights | In Copyright | * |
| dc.rights.uri | http://rightsstatements.org/page/InC/1.0/ | * |
| dc.subject | finite automata | en |
| dc.subject | cut operation | en |
| dc.subject | descriptional complexity | en |
| dc.subject | magic number problem | en |
| dc.subject | unary languages | en |
| dc.subject.ddc | ddc:004 | de_DE |
| dc.title | On the magic number problem of the cut operation | en |
| dc.type | workingPaper | de_DE |
| local.affiliation | FB 07 - Mathematik und Informatik, Physik, Geographie | de_DE |
| local.opus.id | 13271 | |
| local.opus.institute | Institut für Informatik | de_DE |
| local.opus.fachgebiet | Informatik | de_DE |
Files in this item
This item appears in the following Collection(s)
In Copyright