References of "Mainz, Isabelle"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailEfficient Symbolic Representation of Convex Polyhedra in High-Dimensional Spaces
Boigelot, Bernard ULiege; Mainz, Isabelle ULiege

in Lecture Notes in Computer Science (2018)

This work is aimed at developing an efficient data structure for representing symbolically convex polyhedra. We introduce an original data structure, the Decomposed Convex Polyhedron (DCP), that is closed ... [more ▼]

This work is aimed at developing an efficient data structure for representing symbolically convex polyhedra. We introduce an original data structure, the Decomposed Convex Polyhedron (DCP), that is closed under intersection and linear transformations, and allows to check inclusion, equality, and emptiness. The main feature of DCPs lies in their ability to represent concisely polyhedra that can be expressed as combinations of simpler sets, which can overcome combinatorial explosion in high dimensional spaces. DCPs also have the advantage of being reducible into a canonical form, which makes them efficient for representing simple sets constructed by long sequences of manipulations, such as those handled by state-space exploration tools. Their practical efficiency has been evaluated with the help of a prototype implementation, with promising results. [less ▲]

Detailed reference viewed: 49 (15 ULiège)
Full Text
Peer Reviewed
See detailAn efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
Boigelot, Bernard ULiege; Mainz, Isabelle ULiege; Marsault, Victor ULiege et al

in Leibniz International Proceedings in Informatics (2017, August), 80

Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that ... [more ▼]

Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that eventually periodic sets are b-recognisable in every base b, and Cobham's theorem implies the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a $b$-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem is decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case. [less ▲]

Detailed reference viewed: 83 (23 ULiège)
Full Text
See detailLes algorithmes : entre quotidien et créativité
Nicolay, Samuel ULiege; Kleyntssens, Thomas ULiege; Mainz, Isabelle ULiege

Conference given outside the academic context (2015)

Detailed reference viewed: 59 (21 ULiège)
Full Text
Peer Reviewed
See detailAcceleration of Affine Hybrid Transformations
Boigelot, Bernard ULiege; Herbreteau, Frédéric; Mainz, Isabelle ULiege

in Lecture Notes in Computer Science (2014), 8837

This work addresses the computation of the set of reachable configurations of linear hybrid automata. The approach relies on symbolic state-space exploration, using acceleration in order to speed up the ... [more ▼]

This work addresses the computation of the set of reachable configurations of linear hybrid automata. The approach relies on symbolic state-space exploration, using acceleration in order to speed up the computation and to make it terminate for a broad class of systems. Our contribution is an original method for accelerating the control cycles of linear hybrid automata, i.e., to compute their unbounded repeated effect. The idea consists in analyzing the data transformations that label these cycles, by reasoning about the geometrical features of the corresponding system of linear constraints. This approach is complete over Multiple Counters Systems (MCS), and is able to accelerate hybrid transformations that are out of scope of existing techniques. [less ▲]

Detailed reference viewed: 105 (34 ULiège)