Skip to main content

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 978-3-319-12735-4. E-ISBN 978-3-319-12736-1. (doi: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) (KAR id:42815)

This is the latest version of this item.

PDF (Simple and Efficient Algorithms for Octagons) Author's Accepted Manuscript
Language: English

Restricted to Repository staff only
[thumbnail of Simple and Efficient Algorithms for Octagons]
Official URL:


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
DOI/Identification number: 10.1007/978-3-319-12736-1_16
Subjects: A General Works
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 03 Sep 2014 11:20 UTC
Last Modified: 17 Aug 2022 10:57 UTC
Resource URI: (The current URI for this page, for reference purposes)
King, Andy:

Available versions of this item

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


Downloads per month over past year