Document Open Access Logo

The Taming of the Semi-Linear Set

Authors Dmitry Chistikov, Christoph Haase

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.128.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • semi-linear sets
  • convex polyhedra
  • triangulations
  • integer linear programming
  • commutative grammars

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Dmitry Chistikov and Christoph Haase. The Taming of the Semi-Linear Set. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 128:1-128:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.128

Author Details

Dmitry Chistikov
Christoph Haase

References

  1. M. Beck and F. Sottile. Irrational proofs for three theorems of Stanley. Eur. J. Comb., 28(1):403-409, 2007. URL: http://dx.doi.org/10.1016/j.ejc.2005.06.003.
  2. E. Domenjoud. Solving systems of linear Diophantine equations: An algebraic approach. In Mathematical Foundations of Computer Science, MFCS, pages 141-150, 1991. URL: http://dx.doi.org/10.1007/3-540-54345-7_57.
  3. S. Eilenberg and M.P Schützenberger. Rational sets in commutative monoids. J. Algebra, 13(2):173-191, 1969. URL: http://dx.doi.org/10.1016/0021-8693(69)90070-2.
  4. J. Gallier. Notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi diagrams and Delaunay triangulations, 2012. Manuscript available at URL: http://www.cis.upenn.edu/~jean/gbooks/convexpoly.html.
  5. S. Ginsburg. The mathematical theory of context free languages. McGraw-Hill, 1966. Google Scholar
  6. S. Ginsburg and E.H. Spanier. Bounded ALGOL-like languages. T. Am. Math. Soc., pages 333-368, 1964. URL: http://dx.doi.org/10.2307/1994067.
  7. C. Haase and P. Hofman. Tightening the complexity of equivalence problems for commutative grammars. In Symposium on Theoretical Aspects of Computer Science, STACS, volume 47 of LIPIcs, pages 41:1-41:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.41.
  8. C. Haase, B. Nill, and A. Paffenholz. Lecture notes on lattice polytopes. Preliminary version of December 7, 2012, available at URL: http://polymake.org/polytopes/paffenholz/data/preprints/ln_lattice_polytopes.pdf.
  9. M. Hague and A.W. Lin. Model checking recursive programs with numeric data types. In Computer Aided Verification, CAV, volume 6806 of Lect. Notes Comp. Sci., pages 743-759. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22110-1_60.
  10. D.T. Huynh. The complexity of equivalence problems for commutative grammars. Information and Control, 66(1-2):103-121, 1985. URL: http://dx.doi.org/10.1016/S0019-9958(85)80015-2.
  11. D.T. Huynh. A simple proof for the Σ^p₂ upper bound of the inequivalence problem for semilinear sets. Elektron. Inf.verarb. Kybern., 22(4):147-156, 1986. Google Scholar
  12. T.-D. Huynh. The complexity of semilinear sets. Elektron. Inf.verarb. Kybern., 18(6):291-338, 1982. Google Scholar
  13. O.H. Ibarra. Reversal-bounded multicounter machines and their decision problems. J. ACM, 25(1):116-133, 1978. URL: http://dx.doi.org/10.1145/322047.322058.
  14. R. Ito. Every semilinear set is a finite union of disjoint linear sets. J. Comput. Syst. Sci., 3(2):221-231, 1969. URL: http://dx.doi.org/10.1016/S0022-0000(69)80014-0.
  15. E. Kopczyński. Complexity of problems of commutative grammars. Log. Meth. Comput. Sci., 11(1), 2015. URL: http://dx.doi.org/10.2168/lmcs-11(1:9)2015.
  16. M. Köppe and S. Verdoolaege. Computing parametric rational generating functions with a primal Barvinok algorithm. Electr. J. Comb., 15(1), 2008. Google Scholar
  17. J. Matoušek. Lectures on discrete geometry. Graduate texts in mathematics. Springer, 2002. URL: http://dx.doi.org/10.1007/978-1-4613-0039-7.
  18. E.W. Mayr and J. Weihmann. Completeness results for generalized communication-free Petri nets with arbitrary edge multiplicities. In Reachability Problems (RP'13), volume 8169 of LNCS, pages 209-221. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41036-9_19.
  19. A. Paffenholz. Polyhedral geometry and linear optimization. Preliminary version of July, 2010, available at URL: http://www.mathematik.tu-darmstadt.de/~paffenholz/daten/preprints/ln.pdf.
  20. R. Parikh. On context-free languages. J. ACM, 13(4):570-581, 1966. URL: http://dx.doi.org/10.1145/321356.321364.
  21. L. Pottier. Minimal solutions of linear Diophantine systems: Bounds and algorithms. In Rewriting Techniques and Applications, RTA, volume 488 of Lect. Notes Comp. Sci., pages 162-173. Springer, 1991. URL: http://dx.doi.org/10.1007/3-540-53904-2_94.
  22. R.T. Rockafellar. Convex Analysis. Princeton University Press, 1970. Google Scholar
  23. A. Schrijver. Theory of linear and integer programming. John Wiley &Sons, 1986. Google Scholar
  24. J. von zur Gathen and M. Sieveking. A bound on solutions of linear integer equalities and inequalities. P. Am. Math. Soc., 72(1):155-158, 1978. URL: http://dx.doi.org/10.1090/S0002-9939-1978-0500555-0.
  25. V. Weispfenning. The complexity of almost linear Diophantine problems. J. Symb. Comp., 10(5):395-403, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80051-X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact