On the magic number problem of the cut operation

dc.contributor.authorHolzer, Markus
dc.contributor.authorHospodár, Michal
dc.date.accessioned2022-09-12T09:38:41Z
dc.date.available2017-11-20T11:12:28Z
dc.date.available2022-09-12T09:38:41Z
dc.date.issued2017
dc.description.abstractWe 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.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-132716
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7549
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6983
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1703
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectfinite automataen
dc.subjectcut operationen
dc.subjectdescriptional complexityen
dc.subjectmagic number problemen
dc.subjectunary languagesen
dc.subject.ddcddc:004de_DE
dc.titleOn the magic number problem of the cut operationen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id13271
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
Ifig_Report1703.pdf
Größe:
963.16 KB
Format:
Adobe Portable Document Format