UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

The taming of the semi-linear set

Chistikov, D; Haase, C; (2016) The taming of the semi-linear set. In: Chatzigiannakis, I and Mitzenmacher, M and Rabani, Y and Sangiorgi, D, (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). (pp. 128:1-128:13). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany. Green open access

[img]
Preview
Text
LIPIcs-ICALP-2016-128.pdf - Published version

Download (591kB) | Preview

Abstract

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.

Type: Proceedings paper
Title: The taming of the semi-linear set
Event: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
ISBN-13: 978-3-95977-013-2
Open access status: An open access version is available from UCL Discovery
DOI: 10.4230/LIPIcs.ICALP.2016.128
Publisher version: https://doi.org/10.4230/LIPIcs.ICALP.2016.128
Language: English
Additional information: Copyright © Dmitry Chistikov and Christoph Haase; licensed under Creative Commons License CC-BY (http://creativecommons.org/licenses/by/3.0/).
Keywords: semi-linear sets, convex polyhedra, triangulations, integer linear programming, commutative grammars
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10088924
Downloads since deposit
6Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item