On the descriptional complexity of operations on semilinear sets

dc.contributor.authorBeier, Simon
dc.contributor.authorHolzer, Markus
dc.contributor.authorKutrib, Martin
dc.date.accessioned2022-09-12T09:38:40Z
dc.date.available2017-04-06T09:29:26Z
dc.date.available2022-09-12T09:38:40Z
dc.date.issued2017
dc.description.abstractWe investigate the descriptional complexity of operations on semilinear sets. Roughly speaking, a semilinear set is the finite union of linear sets, which are built by constant and period vectors. The interesting parameters of a semilinear set are: (i) the maximal value that appears in the vectors of periods and constants and (ii) the number of such sets of periods and constants necessary to describe the semilinear set under consideration. More precisely, we prove upper bounds on the union, intersection, complementation, and inverse homomorphism. In particular, our result on the complementation upper bound answers an open problem from [G. J. Lavado, G. Pighizzini, S. Seki: Operational State Complexity of Parikh Equivalence, 2014].en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-126075
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7547
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6981
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1701
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleOn the descriptional complexity of operations on semilinear setsen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id12607
local.opus.instituteInstitut für Informatikde_DE

Dateien

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