Simple and Efficient Algorithms for Octagons

Chawdhary, Aziem and Robbins, Ed and King, Andy (2014) Simple and Efficient Algorithms for Octagons. In: Garrigue, Jacques, ed. Twelfth Asian Symposium on Programming Languages and Systems. Lecture Notes in Computer Science, 8858 . Springer, pp. 296-313. ISBN 9783319127354. E-ISBN 9783319127361. (doi:https://doi.org/10.1007/978-3-319-12736-1_16) (Access to this publication is currently restricted. You may be able to access a copy if URLs are provided)

This is the latest version of this item.

PDF (Simple and Efficient Algorithms for Octagons) - Author's Accepted Manuscript
Restricted to Repository staff only
Contact us about this Publication Download (574kB)
[img]
Official URL
http://dx.doi.org/10.1007/978-3-319-12736-1_16

Abstract

The numerical domain of Octagons can be viewed as an exercise in simplicity: it trades expressiveness for efficiency and ease of implementation. The domain can represent unary and dyadic constraints where the coefficients are +1 or -1, so called octagonal constraints, and comes with operations that have cubic complexity. The central operation is closure which computes a canonical form by deriving all implied octagonal constraints from a given octagonal system. This paper investigates the role of incrementality, namely closing a system where only one constraint has been changed, which is a dominating use-case. We present two new incremental algorithms for closure both of which are conceptually simple and computationally efficient, and argue their correctness.

Item Type: Book section
Subjects: A General Works
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Andy King
Date Deposited: 03 Sep 2014 11:20 UTC
Last Modified: 10 Feb 2016 14:15 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/42815 (The current URI for this page, for reference purposes)

Available versions of this item

  • Simple and Efficient Algorithms for Octagons. (deposited 03 Sep 2014 11:20) [Currently Displayed]
  • Depositors only (login required):

Downloads

Downloads per month over past year