The taming of the semi-linear set

Conference item

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.

Authors: Chistikov, D; Haase, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
• Journal: International Colloquium on Automata, Languages, and Programming
• Volume: 55
• Pages: 128:1--128:13
• Series: Leibniz International Proceedings in Informatics
• Publication date: 2016-08-17
• Acceptance date: 2016-04-15
• DOI: 10.4230/LIPIcs.ICALP.2016.128
• ISSN: 1868-8969
• ISBN: 9783959770132
• Keywords: integer linear programming; triangulations; commutative grammars; convex polyhedra; semi-linear sets