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

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
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:	05 Nov 2024 10:27 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]

University of Kent Author Information

Chawdhary, Aziem.

Creator's ORCID:
CReDIT Contributor Roles:

Robbins, Ed.

Creator's ORCID:
CReDIT Contributor Roles:

King, Andy.

Creator's ORCID:	https://orcid.org/0000-0001-5806-4822
CReDIT Contributor Roles:

Depositors only (login required):

Altmetric

Download Statistics

Total unique views for this document in KAR since July 2020. For more details click on the image.