The Library
The taming of the semi-linear set
Tools
Chistikov, Dmitry and Haase, Christoph (2016) The taming of the semi-linear set. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 55 (128). 128:1-128:13. ISBN 9783959770132. doi:10.4230/LIPIcs.ICALP.2016.128 ISSN 1868-8969.
|
PDF
WRAP-taming-semi-linear-set-Chistikov-2016.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (577Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.128
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.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Programming languages (Electronic computers), Computer programming, Computational complexity, Machine theory -- Mathematical models | ||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||
Publisher: | Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik | ||||||||
Place of Publication: | Dagstuhl, Germany | ||||||||
ISBN: | 9783959770132 | ||||||||
ISSN: | 1868-8969 | ||||||||
Official Date: | 2016 | ||||||||
Dates: |
|
||||||||
Volume: | 55 | ||||||||
Number: | 128 | ||||||||
Page Range: | 128:1-128:13 | ||||||||
DOI: | 10.4230/LIPIcs.ICALP.2016.128 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 16 May 2019 | ||||||||
Date of first compliant Open Access: | 17 May 2019 | ||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | ||||||||
Type of Event: | Conference | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year