hh.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Polynomial Function Intervals for Floating-Point Software Verification
Högskolan i Halmstad, Sektionen för Informationsvetenskap, Data– och Elektroteknik (IDE), Halmstad Embedded and Intelligent Systems Research (EIS), Centrum för forskning om inbyggda system (CERES).
School of Engineering and Applied Science, Aston University, Birmingham, United Kingdom.
2014 (engelsk)Inngår i: Annals of Mathematics and Artificial Intelligence, ISSN 1012-2443, E-ISSN 1573-7470, Vol. 70, nr 4, s. 351-398Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

The focus of our work is the verification of tight functional properties of numerical programs, such as showing that a floating-point implementation of Riemann integration computes a close approximation of the exact integral. Programmers and engineers writing such programs will benefit from verification tools that support an expressive specification language and that are highly automated. Our work provides a new method for verification of numerical software, supporting a substantially more expressive language for specifications than other publicly available automated tools. The additional expressivity in the specification language is provided by two constructs. First, the specification can feature inclusions between interval arithmetic expressions. Second, the integral operator from classical analysis can be used in the specifications, where the integration bounds can be arbitrary expressions over real variables. To support our claim of expressivity, we outline the verification of four example programs, including the integration example mentioned earlier. A key component of our method is an algorithm for proving numerical theorems. This algorithm is based on automatic polynomial approximation of non-linear real and real-interval functions defined by expressions. The PolyPaver tool is our implementation of the algorithm and its source code is publicly available. In this paper we report on experiments using PolyPaver that indicate that the additional expressivity does not come at a performance cost when comparing with other publicly available state-of-the-art provers. We also include a scalability study that explores the limits of PolyPaver in proving tight functional specifications of progressively larger randomly generated programs.

sted, utgiver, år, opplag, sider
Dordrecht: Springer Netherlands, 2014. Vol. 70, nr 4, s. 351-398
Emneord [en]
Non-linear numerical constraint solving, Theorem proving, Floating-point software verification, Polynomial intervals, Validated computation, Interval arithmetic
HSV kategori
Identifikatorer
URN: urn:nbn:se:hh:diva-25657DOI: 10.1007/s10472-014-9409-7ISI: 000336365800003Scopus ID: 2-s2.0-84901188918OAI: oai:DiVA.org:hh-25657DiVA, id: diva2:725492
Merknad

This research has been sponsored by Altran Praxis Ltd and EPSRC (Engineering and Physical Sciences Research Council) grant EP/C01037X/1.

Tilgjengelig fra: 2014-06-16 Laget: 2014-06-16 Sist oppdatert: 2018-03-22bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Duracz, Jan

Søk i DiVA

Av forfatter/redaktør
Duracz, Jan
Av organisasjonen
I samme tidsskrift
Annals of Mathematics and Artificial Intelligence

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 181 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf