Search

Mopsa is a multilanguage static analysis platform relying on abstract interpretation. It is able to analyze C, Python, and programs mixing these two languages; we focus on the C analysis here. It provides a novel way to combine abstract domains, in order to offer extensibility and cooperation between them, which is especially beneficial when relational numerical domains are used. The analyses are currently flow-sensitive and fully context-sensitive. We focus only on proving programs to be correct, as our analyses are designed to be sound and terminating but not complete. We present our first participation to SV-Comp, where Mopsa earned a bronze medal in the SoftwareSystems category.

A matching M in a graph G is r -degenerate if the subgraph of G induced by the set of vertices incident with an edge in M is r -degenerate. Goddard, Hedetniemi, Hedetniemi, and Laskar (Generalized subgraph-restricted matchings in graphs, Discrete Mathematics 293 (2005) 129–138)introduced the notion of acyclic matchings, which coincide with 1-degenerate matchings. Solving a problem they posed, we describe an efficient algorithm to determine the maximum size of an r -degenerate matching in a given chordal graph. Furthermore, we study the r -chromatic index of a graph defined as the minimum number of r -degenerate matchings into which its edge set can be partitioned, obtaining upper bounds and discussing extremal graphs.

International audience; This paper aims to exploit the massive parallelism of Field-Programmable Gate Arrays (FPGAs) by programming them in OCaml, a multiparadigm and statically typed language. It first presents O2B, an implementation of the OCaml virtual machine using a softcore processor to run the entire OCaml language on an FPGA. It then introduces Macle, a language to express, in ML-style, hardware-accelerated user-defined functions, implemented as gates and registers on the same FPGA. Macle allows to implement pure computations and compose them in parallel. It also supports processing of dynamic data structures such as arrays, matrices and trees allocated by the OCaml runtime in the memory of the softcore processor. Macle functions can then be called, as hardware accelerators, by OCaml programs executed by O2B. This combination of Macle and OCaml codes in a single source program enables to easily prototype FPGA applications mixing numeric and symbolic computations.

We consider a stochastic matching model with a general compatibility graph, as introduced in \cite{MaiMoy16}. We prove that most common matching policies (including FCFM, priorities and random) satisfy a particular sub-additive property, which we exploit to show in many cases, the coupling-from-the-past to the steady state, using a backwards scheme {\em \`a la} Loynes. We then use these results to explicitly construct perfect bi-infinite matchings, and to build a perfect simulation algorithm in the case where the buffer of the system is finite., Comment: arXiv admin note: substantial text overlap with arXiv:1711.02620

This paper presents a unified computational framework for the estimation of distances, geodesics and barycenters of merge trees. We extend recent work on the edit distance [106] and introduce a new metric, called the Wasserstein distance between merge trees, which is purposely designed to enable efficient computations of geodesics and barycenters. Specifically, our new distance is strictly equivalent to the L2-Wasserstein distance between extremum persistence diagrams, but it is restricted to a smaller solution space, namely, the space of rooted partial isomorphisms between branch decomposition trees. This enables a simple extension of existing optimization frameworks [112] for geodesics and barycenters from persistence diagrams to merge trees. We introduce a task-based algorithm which can be generically applied to distance, geodesic, barycenter or cluster computation. The task-based nature of our approach enables further accelerations with shared-memory parallelism. Extensive experiments on public ensembles and SciVis contest benchmarks demonstrate the efficiency of our approach -- with barycenter computations in the orders of minutes for the largest examples -- as well as its qualitative ability to generate representative barycenter merge trees, visually summarizing the features of interest found in the ensemble. We show the utility of our contributions with dedicated visualization applications: feature tracking, temporal reduction and ensemble clustering. We provide a lightweight C++ implementation that can be used to reproduce our results.

International audience; A temporal graph G is a sequence of static graphs indexed by a set of integers representing time instants. Given ∆ an integer, a ∆-module is a set of vertices A having the same neighbourhood outside of A for ∆ consecutive instants. We address specific cases of ∆-module enumeration, when |A| = 2 or when ∆ = ∞. Our main parameter for time complexity analysis is the history length τ = max{t : G t ∈ G not empty } − min{t : G t ∈ G not empty }. Using red-black tree data structure, we give solutions to above enumeration problems in time logarithmic in τ. For the general ∆-module enumeration problem, we give a pre-processing using overlapping properties of minimal ∆modules. Numerical analysis of our implementation on graphs collected from real world data scales up to a history length of 10 8 time instants 1. Keywords graph theory • historical data • modular decomposition • temporal graph Supported by Courtanet-Sorbonne Université convention C19.0665 and ANRT grant 2019.0485.

This paper introduces progressive algorithms for the topological analysis of scalar data. Our approach is based on a hierarchical representation of the input data and the fast identification of topologically invariant vertices, which are vertices that have no impact on the topological description of the data and for which we show that no computation is required as they are introduced in the hierarchy. This enables the definition of efficient coarse-to-fine topological algorithms, which leverage fast update mechanisms for ordinary vertices and avoid computation for the topologically invariant ones. We demonstrate our approach with two examples of topological algorithms (critical point extraction and persistence diagram computation), which generate interpretable outputs upon interruption requests and which progressively refine them otherwise. Experiments on real-life datasets illustrate that our progressive strategy, in addition to the continuous visual feedback it provides, even improves run time performance with regard to non-progressive algorithms and we describe further accelerations with shared-memory parallelism. We illustrate the utility of our approach in batch-mode and interactive setups, where it respectively enables the control of the execution time of complete topological pipelines as well as previews of the topological features found in a dataset, with progressive updates delivered within interactive times., Accepted to IEEE TVCG on February 17th, 2021

This article present a method to compute efficiently relatives resolvents of an univariate polynomial without numerical computation of its roots. It is at once an effective version of the fundamental theorems of Galois and of symmetric functions.; Cet article présente une méthode pour calculer efficacement les résolvantes relatives d'un polynôme en une variable sans calcul numérique de ses racines. C'est à la fois une version effective des théorèmes fondamentaux de Galois et des fonctions symétriques.

International audience; We introduce a virtual machine approach to pro-gram FPGAs using a high-level programming language (with automatic memory management) while hardware-accelerating a subset of it. This offers an interesting trade-off between high-level synthesis tools and pure software approaches. We describe a preliminary implementation of this hybrid approach using the OCaml language on Intel FPGAs. The associated toolset fully automatizes the compilation process from the OCaml source program to the SoPC hardware and software configuration. First results are encouraging, both for programmability and efficiency.

International audience

International audience

National audience; Les circuits reprogrammables de types FPGA constituent un matériel de choix pour la réalisation d'accélérateurs de calculs. L'implémentation O2B de la machine virtuelle OCaml permet d'appeler des circuits externes réalisés sur FPGA depuis un langage de haut niveau (OCaml) compilé en bytecode. La conception de circuits s'appuie sur des langages de description de matériel (HDL) souvent fort éloignés des langages algorithmiques. C'est pourquoi l'on présente Macle, un langage applicatif dédié à la programmation de calculs séquentiels et parallèles synthétisables en circuits. On décrit la chaîne de compilation de Macle vers un HDL et son intégration à O2B.

International audience; This paper presents the model of Layered Memory Automata (LaMA) to deal with languages involving infinite alphabets, with practical applications in the analysis of datastreams, or modeling complex resource usages in concurrent systems. The LaMA can be seen as an extension of the Finite Memory Automata (FMA) with memory layers and the capacity of dealing with an unbounded amount of memory. Despite the increased expressiveness, the LaMA preserve most of the “good” properties of the FMA, in particular the closure properties for the so-called quasi-regular constructions. Moreover, the layering of the memory enables particularly economical constructions, which is an important focus of our study. The capacity of dealing with an unbounded amount of memory brings the LaMA closer to more powerful automata models such as the history register automata (HRA), thus occupying an interesting position at the crossroad between the operational and the more abstract points of view over data-languages.

International audience; We are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing trees. These families are typical representatives of tree models with a small depth. Once a tree of size n is compacted by keeping only one occurrence of all fringe subtrees appearing in the tree the resulting graph contains only O(n/ ln n) nodes. This result must be compared to classical results of compaction in the families of simply generated trees, where the analogous result states that the compacted structure is of size of order n/ √ ln n. The result about the plane binary increasing trees has already been proved, but we propose a new and generic approach to get the result. Finally, an experimental study is presented, based on a prototype implementation of compacted binary search trees that are modeled by plane binary increasing trees.

Let D be a division ring, n a positive integer, and \(\mathrm{GL}_n(D)\) the set of invertible square matrices of size n and values in D, called the general linear group. We address the intersection graph of subgroups of \(\mathrm{GL}_n(D)\) and prove that it has diameter at most 3. Two particular cases of its induced subgraphs are then investigated: by cyclic subgroups, and by almost subnormal subgroups. We prove that the latter case results in a connected graph whose diameter is sharply bounded by 2. In the former case, we completely characterise the connectivity of the induced graph with respect to D, where, in case of connectivity, we prove that it has diameter at most 7 in general, and at most 5 if D is a locally finite field of characteristic not 2 different from \(\mathbb {F}_3\) and \(\mathbb {F}_9\).

Monadic programming is an essential component in the toolbox of functional programmers. For the pure and total programmers, who sometimes navigate the waters of certified programming in type theory, it is the only means to concisely implement the imperative traits of certain algorithms. Monads open up a portal to the imperative world, all that from the comfort of the functional world. The trend towards certified programming within type theory begs the question of reasoning about such programs. Effectful programs being encoded as pure programs in the host type theory, we can readily manipulate these objects through their encoding. In this article, we pursue the idea, popularized by Maillard [Kenji Maillard, 2019], that every monad deserves a dedicated program logic and that, consequently, a proof over a monadic program ought to take place within a Floyd-Hoare logic built for the occasion. We illustrate this vision through a case study on the SimplExpr module of CompCert [Xavier Leroy, 2009], using a separation logic tailored to reason about the freshness of a monadic gensym., LIPIcs, Vol. 193, 12th International Conference on Interactive Theorem Proving (ITP 2021), pages 29:1-29:19

International audience

International audience; Link streams model the dynamics of interactions in complex distributed systems as sequences of links (interactions) occurring at a given time. Detecting patterns in such sequences is crucial for many applications but it raises several challenges. In particular, there is no generic approach for the specification and detection of link stream patterns in a way similar to regular expressions and automata for text patterns. To address this, we propose a novel automata framework integrating both timed constraints and finite memory together with a recognition algorithm. The algorithm uses structures similar to tokens in high-level Petri nets and includes non-determinism and concurrency. We illustrate the use of our framework in real-world cases and evaluate its practical performances.

Temporal graphs are the modeling of pairwise and historical interaction in recordings of a dataset. A temporal matching formalizes the planning of pair working sessions of a required duration. We depict algorithms finding temporal matchings maximizing the total workload, by an exact algorithm and an approximation. The exact algorithm is a dynamic programming solving the general case in \(O^*((\gamma +1)^n)\) time, where n is the number of vertices, \(\gamma \) represents the desired duration of each pair working session, and \(O^*\) only focuses on exponential factors. When the input data is embedded in an Euclidean space, called geometric data, our approximation is based on a new notion of temporal velocity. We revise a known notion of static density [van Leeuwen, 2009] and result in a polynomial time approximation scheme for temporal geometric graphs of bounded density. We confront our implementations to known opensource implementation (Our source code is available at https://github.com/Talessseed/Temporal-matching-of-historical-and-geometric-graphs).

We study concurrent programs with non-deterministic choice, loops and a fork-join style of coordination under the lens of combinatorics. As a starting point, we interpret these programs as combinatorial structures. We propose a framework, based on analytic combinatorics, allowing to analyse their quantitative aspects such as the average number of execution path induced by the choice operator, or the proportion of executions of a program with respect to its number of execution prefixes. Building on this theoretical investigation, we develop efficient algorithms aimed at the statistical exploration of their state-space. The first algorithm is a uniform random sampler of bounded executions, providing a good default exploration strategy. The second algorithm is a uniform random sampler of execution prefixes of a given bounded length, offering a more fine-grained generation tool, thus enabling to bias the exploration in a controlled manner. The fundamental characteristics of these algorithms is that they work on the syntax of the programs and do not require the explicit construction of the state-space.

National audience

We review state-of-the-art formal methods applied to the emerging field of the verification of machine learning systems. Formal methods can provide rigorous correctness guarantees on hardware and software systems. Thanks to the availability of mature tools, their use is well established in the industry, and in particular to check safety-critical applications as they undergo a stringent certification process. As machine learning is becoming more popular, machine-learned components are now considered for inclusion in critical systems. This raises the question of their safety and their verification. Yet, established formal methods are limited to classic, i.e. non machine-learned software. Applying formal methods to verify systems that include machine learning has only been considered recently and poses novel challenges in soundness, precision, and scalability. We first recall established formal methods and their current use in an exemplar safety-critical field, avionic software, with a focus on abstract interpretation based techniques as they provide a high level of scalability. This provides a golden standard and sets high expectations for machine learning verification. We then provide a comprehensive and detailed review of the formal methods developed so far for machine learning, highlighting their strengths and limitations. The large majority of them verify trained neural networks and employ either SMT, optimization, or abstract interpretation techniques. We also discuss methods for support vector machines and decision tree ensembles, as well as methods targeting training and data preparation, which are critical but often neglected aspects of machine learning. Finally, we offer perspectives for future research directions towards the formal verification of machine learning systems.

International audience; In this paper we study the problem of finding neighbor optimal designs for a general correlation structure. We give universal optimality conditions for nearest-neighbor (NN) balanced block designs when observations on the same block are modeled by an autoregressive AR(m) process with arbitrary order m. The cases m=1,2 have been studied by Grondona and Cressie (Sankhyā Indian J Stat Ser A 55(2):267–284, 1993) for AR(2) and by Gill and Shukla (Biometrika 72(3):539–544, 1985a, Commun Stat Theory Methods 14(9):2181–2197, 1985b) and Kunert (Biometrika 74(4):717–724, 1987) for AR(1); we extend these results to the cases m≥3.

In the context of combinatorial sampling, the so-called “unranking method” can be seen as a link between a total order over the objects and an effective way to construct an object of given rank. The most classical order used in this context is the lexicographic order, which corresponds to the familiar word ordering in the dictionary. In this article, we propose a comparative study of four algorithms dedicated to the lexicographic unranking of combinations, including three algorithms that were introduced decades ago. We start the paper with the introduction of our new algorithm using a new strategy of computations based on the classical factorial numeral system (or factoradics). Then, we present, in a high level, the three other algorithms. For each case, we analyze its time complexity on average, within a uniform framework, and describe its strengths and weaknesses. For about 20 years, such algorithms have been implemented using big integer arithmetic rather than bounded integer arithmetic which makes the cost of computing some coefficients higher than previously stated. We propose improvements for all implementations, which take this fact into account, and we give a detailed complexity analysis, which is validated by an experimental analysis. Finally, we show that, even if the algorithms are based on different strategies, all are doing very similar computations. Lastly, we extend our approach to the unranking of other classical combinatorial objects such as families counted by multinomial coefficients and k-permutations.

In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomenon arising in concurrency. This paper is essentially focusing on the the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space.

Tuttorial; International audience

International audience; We present a static analysis of endian portability for C programs. Our analysis can infer that a given program, or two syntactically close versions thereof, compute the same outputs when run with the same inputs on platforms with different byte-orders, a.k.a. endiannesses. We target low-level C programs that abuse C pointers and unions, hence rely on implementation-specific behaviors undefined in the C standard. Our method is based on abstract interpretation, and parametric in the choice of a numerical abstract domain. We first present a novel concrete collecting semantics, relating the behaviors of two versions of a program, running on platforms with different endiannesses. We propose a joint memory abstraction, able to infer equivalence relations between littleand big-endian memories. We introduce a novel symbolic predicate domain to infer relations between individual bytes of the variables in the two programs, which has near-linear cost, and the right amount of relationality to express (bitwise) arithmetic properties relevant to endian portability. We implemented a prototype static analyzer, able to scale to large real-world industrial software, with zero false alarms.

International audience; Modern programs are increasingly multilanguage, to benefit from each programming language's advantages and to reuse libraries. For example, developers may want to combine high-level Python code with low-level, performance-oriented C code. In fact, one in five of the 200 most downloaded Python libraries available on GitHub contains C code. Static analyzers tend to focus on a single language and may use stubs to model the behavior of foreign function calls. However, stubs are costly to implement and undermine the soundness of analyzers. In this work, we design a static analyzer by abstract interpretation that can handle Python programs calling C extensions. It analyses directly and fully automatically both the Python and the C source codes. It reports runtime errors that may happen in Python, in C, and at the interface. We implemented our analysis in a modular fashion: it reuses off-the-shelf C and Python analyses written in the same analyzer. This approach allows sharing between abstract domains of different languages. Our analyzer can tackle tests of real-world libraries a few thousand lines of C and Python long in a few minutes.

Accepted for publication in the upcoming TopoInVis book (Springer).; International audience; This paper documents the organization, the execution, and the results of the Topology ToolKit (TTK) hackathon that took place at the TopoInVis 2019 conference. The primary goal of the hackathon was to promote TTK in our research community as a unified software development platform for topology-based data analysis algorithms. To this end, participants were first introduced to the structure and capabilities of TTK, and then worked on their own TTK-related projects while being mentored by senior TTK developers. Notable outcomes of the hackathon were first steps towards Python and Docker packages, further integration of TTK in Inviwo, the extension of TTK with new algorithms, and the discovery of current limitations of TTK as well as future development directions.

International audience; Multidimensional Projection is a fundamental tool for high-dimensional data analytics and visualization. With very few exceptions, projection techniques are designed to map data from a high-dimensional space to a visual space so as to preserve some dissimilarity (similarity) measure, such as the Euclidean distance for example. In fact, although adopting distinct mathematical formulations designed to favor different aspects of the data, most multidimensional projection methods strive to preserve dissimilarity measures that encapsulate geometric properties such as distances or the proximity relation between data objects. However, geometric relations are not the only interesting property to be preserved in a projection. For instance, the analysis of particular structures such as clusters and outliers could be more reliably performed if the mapping process gives some guarantee as to topological invariants such as connected components and loops. This paper introduces TopoMap, a novel projection technique which provides topological guarantees during the mapping process. In particular, the proposed method performs the mapping from a high-dimensional space to a visual space, while preserving the 0-dimensional persistence diagram of the Rips filtration of the high-dimensional data, ensuring that the filtrations generate the same connected components when applied to the original as well as projected data. The presented case studies show that the topological guarantee provided by TopoMap not only brings confidence to the visual analytic process but also can be used to assist in the assessment of other projection methods.

International audience; Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. DAGs are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70's by Robinson. In many applications one needs to construct connected DAGs and to control their number of edges, but the adaptation of Robinson's enumeration to take this into account led to counting formulas based on the inclusion-exclusion principle, inducing a high computational cost for the uniform random sampling of DAGs based on this formula. In the present paper we propose two contributions. First we enumerate a new class of DAGs, enriched with an independent ordering of the children of each vertex, according to their numbers of vertices and edges. We obtain a constructive recursive counting formula for them (i.e. without using the inclusion-exclusion principle) using a new decomposition scheme. Then we show the applicability of our method by proposing a constructive enumeration of Robinson's labelled DAGs, by vertices and edges, based on the same decomposition. As a consequence we are able to derive efficient uniform random samplers for both models.

A temporal graph \(\mathcal {G}\) is a sequence of static graphs indexed by a set of integers T representing time instants. For \(\varDelta \) an integer, a pair of \(\varDelta \)-twins is a pair of vertices \(u\ne v\) which, starting at some time instant, have exactly the same neighbourhood outside \(\{u, v\}\) for \(\varDelta \) consecutive instants. We address the enumeration problem of all pairs of \(\varDelta \)-twins in \(\mathcal {G}\), such that the overall runtime depends the least on the history length, namely \(\max \{t:G_t\in \mathcal {G}\text { not empty }\}-\min \{t:G_t\in \mathcal {G}\text { not empty }\}\). We give logarithmic solutions, using red-black tree data structure. Numerical analysis of our implementation on graphs collected from real world data scales up to \(10^8\) history length (Source code at https://github.com/DaemonFire/deltatwinsMEI.).

International audience; We study the combinatorial structure of the state-space of non-deterministic fork-join processes. As a first step we establish a link between concurrent programs and a class of combinatorial structures based on the notion of increasing labelling. Beyond the theory, our goal is to develop algorithms and tools for the statistical analysis of the process behaviours. In the second part we develop and experiment two efficient random sampling algorithms serving as basic building blocks for state-space exploration. One is a uniform random sampler of bounded executions, providing a good default exploration strategy, and the other is a uniform sampler of execution prefixes allowing to bias the exploration in a controlled manner. The fundamental characteristic of these algorithms is that they work on the control graph of the programs and do not require the construction of its state-space, thus providing a way to tackle the infamous state explosion problem.

International audience; We present a specification language aiming at soundly modeling unavailable functions in a static analyzer for C by abstract interpretation. It takes inspiration from Behavioral Interface Specification Languages popular in deductive verification, notably Frama-C's ACSL, as we annotate function prototypes with pre and post-conditions expressed concisely in a first-order logic, but with key differences. Firstly, the specification aims at replacing a function implementation in a safety analysis, not verifying its functional correctness. Secondly, we do not rely on theorem provers; instead, specifications are interpreted at function calls by our abstract interpreter. We implemented the language into Mopsa, a static analyzer designed to easily reuse abstract domains across widely different languages (such as C and Python). We show how its design helped us support a logic-based language with minimal effort. Notably, it was sufficient to add only a handful transfer functions (including very selective support for quantifiers) to achieve a sound and precise analysis. We modeled a large part of the GNU C library and C execution environment in our language, including the manipulation of unbounded strings, file descriptors, and programs with an unbounded number of symbolic command-line parameters, which allows verifying programs in a realistic setting. We report on the analysis of C programs from the Juliet benchmarks and Coreutils.

International audience; In this paper, we present an approach for programming microcontrollers that provides more expressivity and safety than a low-level language approach traditionally used to program such devices. To this end, we provide various abstraction layers (abstraction of the microcontroller, of the electronic components of the circuit, and of concurrency) which, while being adapted to the scarce resources of the hardware, offer high-level programming traits for the development of embedded applications. The various presented abstractions make use of an OCaml virtual machine able to run on devices with limited resources and take advantage of the expressivity and extensibility of the language. We illustrate the interest of our work on both entertainment applications and embedded software examples.

Python is an increasingly popular dynamic programming language, particularly used in the scientific community and well-known for its powerful and permissive high-level syntax. Our work aims at detecting statically and automatically type errors. As these type errors are exceptions that can be caught later on, we precisely track all exceptions (raised or caught). We designed a static analysis by abstract interpretation able to infer the possible types of variables, taking into account the full control-flow. It handles both typing paradigms used in Python, nominal and structural, supports Python’s object model, introspection operators allowing dynamic type testing, dynamic attribute addition, as well as exception handling. We present a flow- and context-sensitive analysis with special domains to support containers (such as lists) and infer type equalities (allowing it to express parametric polymorphism). The analysis is soundly derived by abstract interpretation from a concrete semantics of Python developed by Fromherz et al. Our analysis is designed in a modular way as a set of domains abstracting a concrete collecting semantics. It has been implemented into the MOPSA analysis framework, and leverages external type annotations from the Typeshed project to support the vast standard library. We show that it scales to benchmarks a few thousand lines long, and preliminary results show it is able to analyze a small real-life command-line utility called PathPicker. Compared to previous work, it is sound, while it keeps similar efficiency and precision., LIPIcs, Vol. 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020), pages 17:1-17:29

Let D be a division ring, n a positive integer, and GL_n(D) the general linear group of degree n over D. In this paper, we study the induced subgraph of the intersection graph of GL_n(D) generated by all non-trivial proper almost subnormal subgroups of GL_n(D). We show that this subgraph is complete if it is non-null. This property will be used to study subgroup structure of a division ring. In particular, we prove that every non-central almost subnormal subgroup of the multiplicative group D* of a division ring D contains a non-central subnormal subgroup of D*.

National audience; Cet ouvrage débute par une introduction à la logique des prédicats du premier ordre : syntaxe, sémantique et preuves formelles. Il guide ensuite le lecteur vers quelques uns de ses aspects plus avancés : théorème de complétude, théorème d'indécidabilité. Se tournant ensuite vers les rapports de la logique et de l'informatique, il présente les méthodes algorithmiques de démonstration automatique comme la résolution et l'unification ainsi que des applications plus directes des concepts logiques au domaine informatique (problème SAT, bases de données relationnelles, vérification de modèle, etc.)Sa lecture ne demande aucun prérequis en la matière et peut s'adresser à tout étudiant débutant en logique (licence ou master d'informatique, élève ingénieur). L'exposé des notions de base de logique sont accompagnées de nombreux exercices corrigés.

IEEE VIS Tutorials 2020 http://ieeevis.org/year/2020/info/tutorials; International audience

This paper describes a localized algorithm for the topological simplification of scalar data, an essential pre-processing step of topological data analysis (TDA). Given a scalar field $f$ and a selection of extrema to preserve, the proposed localized topological simplification (LTS) derives a function g that is close to $f$ and only exhibits the selected set of extrema. Specifically, sub- and superlevel set components associated with undesired extrema are first locally flattened and then correctly embedded into the global scalar field, such that these regions are guaranteed-from a combinatorial perspective-to no longer contain any undesired extrema. In contrast to previous global approaches, LTS only and independently processes regions of the domain that actually need to be simplified, which already results in a noticeable speedup. Moreover, due to the localized nature of the algorithm, LTS can utilize shared-memory parallelism to simplify regions simultaneously with a high parallel efficiency (70%). Hence, LTS significantly improves interactivity for the exploration of simplification parameters and their effect on subsequent topological analysis. For such exploration tasks, LTS brings the overall execution time of a plethora of TDA pipelines from minutes down to seconds, with an average observed speedup over state-of-the-art techniques of up to $\times 36$ . Furthermore, in the special case where preserved extrema are selected based on topological persistence, an adapted version of LTS partially computes the persistence diagram and simultaneously simplifies features below a predefined persistence threshold. The effectiveness of LTS, its parallel efficiency, and its resulting benefits for TDA are demonstrated on several simulated and acquired datasets from different application domains, including physics, chemistry, and biomedical imaging.

This thesis investigates certified programming by stepwise refinement in the framework of the Coq proof assistant. This allows the construction of programs that are correct by construction. The programming language that is considered is a simple imperative language with assignment, selection, sequence, and iteration. The semantics of this language is formalized in a relational and predicative setting, and is shown to be equivalent to an axiomatic semantics in the style of a Hoare logic. The stepwise refinement approach to programming requires that refinement steps from the specification to the program be proved correct. For so doing, we use a calculus of weakest pre-specifications which is a generalisation of the calculus of weakest pre-conditions. Finally, to capture the whole refinement history of a program development, we formalize a design language and a logic for reasoning about program designs in order to establish that all refinement steps are indeed correct. The approach developed during this thesis is entirely mecanised using the Coq proof assistant.; Cette thèse s’intéresse à la programmation certifiée correcte dans le cadre formel fourni par l’assistant de preuve Coq, et conduite par étapes de raffinements, permettant ainsi d’aboutir à un résultat correct par construction. Le langage de programmation considéré est un langage impératif simple, avec affectations, alternatives, séquences, et boucles. La sémantique associée à ce langage est une sémantique relationnelle exprimée dans un cadre prédicatif plus adapté à un plongement dans la théorie des types, plutôt que dans le calcul des relations. Nous étudions la relation entre d’une part la sémantique prédicative et relationnelle que nous avons choisie, et d’autre part une approche plus classique dans le style de la logique de Hoare. En particulier, nous montrons que les deux approches ont en théorie la même puissance. La démarche que nous étudions consiste à certifier, avec l’aide d’un assistant de preuve, les raffinements successifs permettant de passer de la spécification au programme. Nous nous intéressons donc aussi aux techniques de preuve permettant en pratique d’établir la validité des raffinements. Plus précisément, nous utilisons un calcul de la plus faible pré-spécification jouant ici le rôle du calcul de la plus faible pré-condition dans les approches classiques. Afin que l’articulation des étapes de raffinement reste aussi proche que possible de l’activité de programmation, nous formalisons un langage de développement qui permet de décrire l’arborescence des étapes de raffinement, ainsi qu’une logique permettant de raisonner sur ces développements, et de garantir leur correction.

We study the asymptotic number of certain monotonically labeled increasing trees arising from a generalized evolution process. The main difference between the presented model and the classical model of binary increasing trees is that the same label can appear in distinct branches of the tree. In the course of the analysis we develop a method to extract asymptotic information on the coefficients of purely formal power series. The method is based on an approximate Borel transform (or, more generally, Mittag-Leffler transform) which enables us to quickly guess the exponential growth rate. With this guess the sequence is then rescaled and a singularity analysis of the generating function of the scaled counting sequence yields accurate asymptotics. The actual analysis is based on differential equations and a Tauberian argument. The counting problem for trees of size n exhibits interesting asymptotics involving powers of n with irrational exponents.

International audience; We propose to extend an existing framework combining abstract interpretation and continuous constraint programming for numerical invariant synthesis, by using more expressive underlying abstract domains, such as zonotopes. The original method, which relies on iterative refinement, splitting and tightening a collection of abstract elements until reaching an inductive set, was initially presented in combination with simple underlying abstract elements: boxes and octagons. The novelty of our work is to use zonotopes, a sub-polyhedric domain that shows a good compromise between cost and precision. As zonotopes are not closed under intersection, we had to extend the existing framework, in addition to designing new operations on zonotopes, such as a novel splitting algorithm based on paving zonotopes by sub-zonotopes and parallelotopes. We implemented this method on top of the APRON library, and tested it on programs with non-linear loops that present complex, possibly non-convex, invariants. We present some results demonstrating both the interest of this splitting-based algorithm to synthesize invariants on such programs, and the good compromise presented by its use in combination with zonotopes with respect to its use with both simpler domains such as boxes and octagons, and more expressive domains such as polyhedra.

International audience; Sound static analyses for large subsets of static programming languages such as C are now widespread. For example the Astrée static analyzer soundly overapproximates the behavior of C programs that do not contain any dynamic code loading, longjmp statements nor recursive functions. The sound and precise analysis of widely used dynamic programming languages like JavaScript and Python remains a challenge. This paper examines the variation of static analyses of Python-in precision, time and memory usage-by adapting three parameters: (i) the value sensitivity, (ii) the allocation sensitivity and (iii) the activation of an abstract garbage collector. It is not clear yet which level of sensitivity constitutes a sweet spot in terms of precision versus efficiency to achieve a meaningful Python analysis. We thus perform an experimental evaluation using a prototype static analyzer on benchmarks a few thousand lines long. Key findings are: the value analysis does not improve the precision over type-related alarms; the value analysis is three times costlier than the type analysis; the allocation sensitivity depends on the value sensitivity; using an abstract garbage collector lowers memory usage and running times, but does not affect precision.

We propose a comparative study of four algorithms dedicated to the lexicographic unranking of combinations. The three first ones are algorithms from the literature. We give some key ideas how to analyze them in average and describe their strengths and weaknesses. We then introduce a new algorithm based on a new strategy inside the classical factorial numeral system (or factoradics). We conclude the paper with an experimental study, in particular when n = 10000; k = 5000, our algorithm is 36 (resp. 53) times as fast as our C++ implementation of Matlab's (resp. Sagemath's) algorithm.

National audience

International audience; A Revolution for developing of safety critical application Developing safety critical applications often requires rare human resources to complete successfully while off-the-shelf block solutions appear difficult to adapt especially during short-term projects. Developed during the R&D project FUI LCHIP[5], the CLEARSY Safety Platform fulfills a need for a technical solution to overcome the difficulties to develop SIL3/SIL4 system. Its technology is based on a smart combination of diverse hardware (2x PIC 32 micro-controllers) and a formal method with proof heavily used in the railways industry for decades. It avoids most testing and ensures safety at the highest level. The CLEARSY Safety Platform is both a software and a hardware platform aimed at designing and executing safety critical applications. One formal modelling language (B) is used to program the board. Programs are developed using a dedicated IDE or could be the by-product of some translation from a Domain Specific Language to B. The IDE takes care of the verification of the software (type check, proof, compilation) and then ensures its uploading to the hardware platform. Program is guaranteed to execute until a misbehaviour is detected, leading to a safe restricted mode where board outputs are deactivated. Added value The CLEARSY Safety Platform eases the development of safety critical applications as:-it covers the whole development cycle of control-command systems based on digital inputs/outputs.-development time is shortened as the safety principles are built-in, and are out of reach of the developer who cannot alter them. Development is focused on the behaviour.

The tax code, as a legislative text, defines a mathematical function that computes the income tax of a fiscal household. In order to collect taxes, this function is implemented as an algorithm by the Direction Générale des Finances Publiques (DGFiP), using a domain specific language called M (standing for "Macro-language"). We propose a formal semantics of the M language, tested thanks to data published by the DGFiP. This formalization, coupled with the public release by the DGFiP of the codebase used to compute the income tax, allowed us to produce a fully formalized artifact encoding the fragment of the tax code describing the income tax computation. We demonstrate the usefulness of such a formalization thanks to a prototype that uses an SMT solver to infer meta-properties on the income tax computation. These meta-properties could complete and refine the existing economical analysis of the redistributive effects of the income tax, as well as various social benefits. More generally, a systematic formalization of the algorithmic fragments of the law would raise the assurance level on the coherence of the French socio-fiscal system. This work has led to the development of three software artifacts: a mechanized semantics for M, an interpreter and compiler for M based on this semantics (written in OCaml), and a Python prototype of encoding the income tax computation into the Z3 SMT solver., Le code des impôts définit dans son texte législatif une fonction mathématique per-mettant de calculer l'impôt sur le revenu d'un foyer fiscal. Afin de recouvrer l'impôt, cette fonction est implémentée sous la forme d'un algorithme par la Direction Générale des Finances Publiques (DGFiP), en utilisant un langage dédié appelé M (pour macro-langage). Nous proposons une sémantique formelle du langage M, testée grâce aux données publiées par la DGFiP. Cette formalisation, couplée à la publication par la DGFiP de la base de code M calculant l'impôt, nous donne accès à une formalisation complète de la portion du code des impôts définissant l'algorithme de calcul de l'impôt sur le revenu. Nous démontrons l'utilité d'une telle formalisation grâce à un prototype à base de solveurs SMT permet-tant d'inférer des méta-propriétés sur le calcul de l'impôt. Ces méta-propriétés peuvent ensuite compléter et affiner les analyses économiques existantes sur les effets redistributifs de l'impôt sur le revenu, mais aussi de diverses allocations. Plus généralement, une for-malisation systématique des portions algorithmiques de la loi permettrait d'augmenter le niveau d'assurance sur la cohérence du système socio-fiscal français. Trois artefacts logiciels accompagnent cet article : une formalisation mécanisée de la sémantique du langage M, un compilateur pour le langage M basé sur cette sémantique, ainsi que le prototype d'encodage du code des impôts dans le solveur SMT Z3.

Conference postponed to 2021 (COVID19); International audience; Any Boolean function corresponds with a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a direct acyclic graph where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (ROBDD). We propose to revisit the classical compaction process to give a new way of enumerating ROBDDs of a given size without considering fully expanded trees and the compaction step. Our method also provides an unranking procedure for the set of ROBDDs. As a by-product we get a random uniform and exhaustive sampler for ROBDDs for a given number of variables and size.

International audience; There exists a wealth of literature concerning families of increasing trees, particularly suitable for representing the evolution of either data structures in computer science, or probabilistic urns in mathematics, but are also adapted to model evolutionary trees in biology. The classical notion of increasing trees corresponds to labeled trees such that, along paths from the root to any leaf, node labels are strictly increasing; in addition nodes have distinct labels. In this paper we introduce new families of increasingly labeled trees relaxing the constraint of unicity of each label. Such models are especially useful to characterize processes evolving in discrete time whose nodes evolve simultaneously. In particular, we obtain growth processes for biology much more adequate than the previous increasing models. The families of monotonic trees we introduce are much more delicate to deal with, since they are not decomposable in the sense of Analytic Combinatorics. New tools are required to study the quantitative statistics of such families. In this paper, we first present a way to combinatorially specify such families through evolution processes, then, we study the tree enumerations.