Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

On the descriptional complexity of operations on semilinear sets

Beier, Simon ; Holzer, Markus ; Kutrib, Martin


Zum Volltext im pdf-Format: Dokument 1.pdf (1.012 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-126075
URL: http://geb.uni-giessen.de/geb/volltexte/2017/12607/

Bookmark bei del.icio.us


Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1701
Sprache: Englisch
Erstellungsjahr: 2017
Publikationsdatum: 06.04.2017
Kurzfassung auf Englisch: We 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 con- stant 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].
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand