189 datasets found

In this research report, we study the algorithmic complexity of different broadcast and multicast ad hoc routing problems given a wireless medium.

In this paper, it is shown that the Gröbner basis (for any monomial ordering) of a zero-dimensional ideal may be computed within a bit complexity which is essentially...

International audience

In this work, we propose an ExpSpace tableau-based algorithm for deciding consistency of a knowledge base in the description logic SHOIQ. The construction of this...

In this paper, we improve the bound of complexity of the algorithms on polynomial ideals having complexities polynomial in $d^n$ where $d$ is the maximal degree of...

Everybody knows the Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL), which has proved invaluable in public-key cryptanalysis and in many other fields....

First we justify our concern in latency constraints for real-time systems with precedence constraints. We evoke the model based on graph theory used to state and solve...

E-unification problems are central in automated deduction. In this work, we consider unification modulo theories that extend the well-known ACI or ACUI, by adding a...

25 pages

International audience

We explore several concepts for analyzing the intuitive notion of computational irreducibility and we propose a robust formal definition, first in the field of...

8 pages

International audience

Innovation is a complex process more than one way. The organization of the preliminary phases of innovation projects mobilizing interdisciplinary teams that implement...

International audience

International audience

International audience

This thesis proposes a model of RNA secondary structures with or without pseudoknots. According to a combinatorial approach, we design different models of these...

34 pages

Consider a system of n polynomial equations and r polynomial inequations in n indeterminates of degree bounded by d with coefficients in a polynomial ring of s...