Source author record

Assalé Adjé

Assalé Adjé appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.OC Logic in Computer Science Computer Science and Game Theory Formal Languages and Automata Theory Numerical Analysis Programming Languages Software Engineering

Catalog footprint

What is connected

10works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Fast and Efficient Bit-Level Precision Tuning

In this article, we introduce a new technique for precision tuning. This problem consists of finding the least data types for numerical values such that the result of the computation satisfies some accuracy requirement. State of the art techniques for precision tuning use a try and fail approach. They change the data types of some variables of the program and evaluate the accuracy of the result. Depending on what is obtained, they change more or less data types and repeat the process. Our technique is radically different. Based on semantic equations, we generate an Integer Linear Problem (ILP) from the program source code. Basically, this is done by reasoning on the most significant bit and the number of significant bits of the values which are integer quantities. The integer solution to this problem, computed in polynomial time by a (real) linear programming solver, gives the optimal data types at the bit level. A finer set of semantic equations is also proposed which does not reduce directly to an ILP problem. So we use policy iteration to find the solution. Both techniques have been implemented and we show that our results encompass the results of state of the art tools.

preprint2020arXiv

Fixed Points of the Set-Based Bellman Operator

Motivated by uncertain parameters encountered in Markov decision processes (MDPs), we study the effect of parameter uncertainty on Bellman operator-based methods. Specifically, we consider a family of MDPs where the cost parameters are from a given compact set. We then define a Bellman operator acting on an input set of value functions to produce a new set of value functions as the output under all possible variations in the cost parameters. Finally we prove the existence of a fixed point of this set-based Bellman operator by showing that it is a contractive operator on a complete metric space.

preprint2020arXiv

Quadratic Maximization over the Reachable Values Set of a Convergent Discrete-time Affine System : The diagonalizable case

In this paper, we solve a maximization problem where the objective function is quadratic and convex or concave and the constraints set is the reachable value set of a convergent discrete-time affine system. Moreover, we assume that the matrix defining the system is diagonalizable. The difficulty of the problem lies in the infinite sequence to handle in the constraint set. Equivalently, the problem requires to solve an infinite number of quadratic programs. Therefore, the main idea is to extract a finite of them and to guarantee that the resolution of the extracted problems provides the optimal value and a maximizer for the initial problem. The number of quadratic programs to solve has to be the smallest possible. Actually, we construct a family of integers that over-approximate the exact number of quadratic programs to solve using basic ideas of linear algebra. This family of integers is used in the final algorithm. A new computation of an integer of the family within the algorithm ensures a reduction of the number of loop iterations. The method proposed in the paper is illustrated on small academic examples. Finally, the algorithm is experimented on randomly generated instances of the problem.

preprint2016arXiv

A Sums-of-Squares Extension of Policy Iterations

In order to address the imprecision often introduced by widening operators in static analysis, policy iteration based on min-computations amounts to considering the characterization of reachable value set of a program as an iterative computation of policies, starting from a post-fixpoint. Computing each policy and the associated invariant relies on a sequence of numerical optimizations. While the early research efforts relied on linear programming (LP) to address linear properties of linear programs, the current state of the art is still limited to the analysis of linear programs with at most quadratic invariants, relying on semidefinite programming (SDP) solvers to compute policies, and LP solvers to refine invariants. We propose here to extend the class of programs considered through the use of Sums-of-Squares (SOS) based optimization. Our approach enables the precise analysis of switched systems with polynomial updates and guards. The analysis presented has been implemented in Matlab and applied on existing programs coming from the system control literature, improving both the range of analyzable systems and the precision of previously handled ones.

preprint2016arXiv

Overapproximating the Reachable Values Set of Piecewise Affine Systems Coupling Policy Iterations with Piecewise Quadratic Lyapunov Functions

We have recently constructed a piecewise quadratic Lyapunov function to prove the boundedness of the reachable values set of piecewise affine discrete-time systems. The method developed also provided an overapproximation of the reachable values set. In this paper, we refine the latter overapproximation extending previous works combining policy iterations with quadratic Lyapunov functions.

preprint2015arXiv

Property-based Polynomial Invariant Generation using Sums-of-Squares Optimization

While abstract interpretation is not theoretically restricted to specific kinds of properties, it is, in practice, mainly developed to compute linear over-approximations of reachable sets, aka. the collecting semantics of the program. The verification of user-provided properties is not easily compatible with the usual forward fixpoint computation using numerical abstract domains. We propose here to rely on sums-of-squares programming to characterize a property-driven polynomial invariant. This invariant generation can be guided by either boundedness, or in contrary, a given zone of the state space to avoid. While the target property is not necessarily inductive with respect to the program semantics, our method identifies a stronger inductive polynomial invariant using numerical optimization. Our method applies to a wide set of programs: a main while loop composed of a disjunction (if-then-else) of polynomial updates e.g. piecewise polynomial controllers. It has been evaluated on various programs.

preprint2015arXiv

Quadratic Zonotopes:An extension of Zonotopes to Quadratic Arithmetics

Affine forms are a common way to represent convex sets of $\mathbb{R}$ using a base of error terms $ε\in [-1, 1]^m$. Quadratic forms are an extension of affine forms enabling the use of quadratic error terms $ε_i ε_j$. In static analysis, the zonotope domain, a relational abstract domain based on affine forms has been used in a wide set of settings, e.g. set-based simulation for hybrid systems, or floating point analysis, providing relational abstraction of functions with a cost linear in the number of errors terms. In this paper, we propose a quadratic version of zonotopes. We also present a new algorithm based on semi-definite programming to project a quadratic zonotope, and therefore quadratic forms, to intervals. All presented material has been implemented and applied on representative examples.

preprint2014arXiv

Polynomial Template Generation using Sum-of-Squares Programming

Template abstract domains allow to express more interesting properties than classical abstract domains. However, template generation is a challenging problem when one uses template abstract domains for program analysis. In this paper, we relate template generation with the program properties that we want to prove. We focus on one-loop programs with nested conditional branches. We formally define the notion of well-representative template basis with respect to such programs and a given property. The definition relies on the fact that template abstract domains produce inductive invariants. We show that these invariants can be obtained by solving certain systems of functional inequalities. Then, such systems can be strengthened using a hierarchy of sum-of-squares (SOS) problems when we consider programs written in polynomial arithmetic. Each step of the SOS hierarchy can possibly provide a solution which in turn yields an invariant together with a certificate that the desired property holds. The interest of this approach is illustrated on nontrivial program examples in polynomial arithmetic.

preprint2013arXiv

Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs

The problem of computing the smallest fixed point of an order-preserving map arises in the study of zero-sum positive stochastic games. It also arises in static analysis of programs by abstract interpretation. In this context, the discount rate may be negative. We characterize the minimality of a fixed point in terms of the nonlinear spectral radius of a certain semidifferential. We apply this characterization to design a policy iteration algorithm, which applies to the case of finite state and action spaces. The algorithm returns a locally minimal fixed point, which turns out to be globally minimal when the discount rate is nonnegative.

preprint2012arXiv

Concrete Semantics of Programs with Non-Deterministic and Random Inputs

This document gives semantics to programs written in a C-like programming language, featuring interactions with an external environment with noisy and imprecise data.