The domain of convex polyhedra plays a special role in the collection of numerical domains considered for program analysis and verification. As far as precision is concerned, it would be the most natural choice in many contexts but, due to its worst case exponential complexity, it is sometimes considered an unaffordable option. This has led to a systematic quest for simpler domains that are capable of reasonable precision using less computational resources. There are anyway cases where the use of the domain of convex polyhedra turns out to be feasible, also due to recent progress in their implementation. After reviewing a few known approaches to decrease the amount of resources needed when computing on this domain, we will introduce a couple of novel techniques that can be used to further improve its efficiency, without incurring precision losses.

On the Efficiency of Convex Polyhedra / Zaffanella, Enea. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - 334:(2018), pp. 31-44. [10.1016/j.entcs.2018.03.004]

On the Efficiency of Convex Polyhedra

Zaffanella, Enea
2018-01-01

Abstract

The domain of convex polyhedra plays a special role in the collection of numerical domains considered for program analysis and verification. As far as precision is concerned, it would be the most natural choice in many contexts but, due to its worst case exponential complexity, it is sometimes considered an unaffordable option. This has led to a systematic quest for simpler domains that are capable of reasonable precision using less computational resources. There are anyway cases where the use of the domain of convex polyhedra turns out to be feasible, also due to recent progress in their implementation. After reviewing a few known approaches to decrease the amount of resources needed when computing on this domain, we will introduce a couple of novel techniques that can be used to further improve its efficiency, without incurring precision losses.
2018
On the Efficiency of Convex Polyhedra / Zaffanella, Enea. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - 334:(2018), pp. 31-44. [10.1016/j.entcs.2018.03.004]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2848040
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact