2026-07-21T19:28:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6263 2024-03-06T10:37:55Z ddc:004 open_access

The Taming of the Semi-Linear Set Chistikov, Dmitry Haase, Christoph semi-linear sets convex polyhedra triangulations integer linear programming commutative grammars Semi-linear sets, which are rational subsets of the monoid (Z^d,+), have numerous applications in theoretical computer science. Although semi-linear sets are usually given implicitly, by formulas in Presburger arithmetic or by other means, the effect of Boolean operations on semi-linear sets in terms of the size of description has primarily been studied for explicit representations. In this paper, we develop a framework suitable for implicitly presented semi-linear sets, in which the size of a semi-linear set is characterized by its norm—the maximal magnitude of a generator. We put together a toolbox of operations and decompositions for semi-linear sets which gives bounds in terms of the norm (as opposed to just the bit-size of the description), a unified presentation, and simplified proofs. This toolbox, in particular, provides exponentially better bounds for the complement and set-theoretic difference. We also obtain bounds on unambiguous decompositions and, as an application of the toolbox, settle the complexity of the equivalence problem for exponent-sensitive commutative grammars. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Chistikov and Christoph Haase 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.128 urn:nbn:de:0030-drops-62636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.128 eng https://creativecommons.org/licenses/by/3.0/legalcode