A Survey on Continuous Time Computations (2009)
Bournez, Olivier, Campagnolo, Manuel
We provide an overview of theories of continuous time computation. These theories allow us to understand both the hardness of questions related to continuous time dynamical systems and the...
On the Convergence of Population Protocols When Population Goes to Infinity (2009)
Bournez, Olivier, Chassaing, Philippe, Cohen, Johanne, Gerin, Lucas, Koegler, Xavier
Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a...
Verification of Timed Automata Using Rewrite Rules and Strategies (2009)
Beffara, Emmanuel, Bournez, Olivier, Kacem, Hassen, Kirchner, Claude
ELAN is a powerful language and environment for specifying and prototyping deduction systems in a language based on rewrite rules controlled by strategies. Timed automata is a class of continuous...
Population Protocols that Correspond to Symmetric Games (2009)
Bournez, Olivier, Chalopin, Jeremie, Cohen, Johanne, Koegler, Xavier
Population protocols have been introduced by Angluin et {al.} as a model of networks consisting of very limited mobile agents that interact in pairs but with no control over their own movement. A...
Playing With Population Protocols (2009)
Bournez, Olivier, Chalopin, Jérémie, Cohen, Johanne, Koegler, Xavier
Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement: A collection of anonymous agents, modeled by...
Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions (2009)
Bournez, Olivier, Gomaa, Walid, Hainry, Emmanuel
Recursive analysis is the most classical approach to model and discuss computations over the reals. It is usually presented using Type 2 or higher order Turing machines. Recently, it has been shown...
Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions (2009)
Bournez, Olivier, Gomaa, Walid, Hainry, Emmanuel
Recursive analysis is the most classical approach to model and discuss computations over the reals. It is usually presented using Type 2 or higher order Turing machines. Recently, it has been shown...
Implicit complexity in recursive analysis (2009)
Bournez, Olivier, Gomaa, Walid, Hainry, Emmanuel
Recursive analysis is a model of analog computation which is based on type 2 Turing machines. Various classes of functions computable in recursive analysis have recently been characterized in a...
Implicit complexity in recursive analysis (2009)
Bournez, Olivier, Gomaa, Walid, Hainry, Emmanuel
Recursive analysis is a model of analog computation which is based on type 2 Turing machines. Various classes of functions computable in recursive analysis have recently been characterized in a...
A dynamic approach for load balancing (2009)
Barth, Dominique, Bournez, Olivier, Boussaton, Octave, Cohen, Johanne
We study how to reach a Nash equilibrium in a load balanc- ing scenario where each task is managed by a selfish agent and attempts to migrate to a machine which will minimize its cost. The cost of a...
A dynamic approach for load balancing (2009)
Barth, Dominique, Bournez, Olivier, Boussaton, Octave, Cohen, Johanne
We study how to reach a Nash equilibrium in a load balanc- ing scenario where each task is managed by a selfish agent and attempts to migrate to a machine which will minimize its cost. The cost of a...
Et Sécurité, Olivier Bournez, Johanne Cohen, Chargée De Recherche, ...
Scientific leader:
Proving Positive Almost Sure Termination Under Strategies (2008)
Olivier Bournez, Florent Garnier
Abstract In last RTA, we introduced the notion of probabilistic rewrite systems and we gave some conditions entailing termination of those systems within a finite mean number of reduction steps....
Proving Positive Almost Sure Termination Under Strategies (2008)
Olivier Bournez, Florent Garnier
Abstract In last RTA, we introduced the notion of probabilistic rewrite systems and we gave some conditions entailing termination of those systems within a finite mean number of reduction steps....
IOS Press Recursive Analysis Characterized as a Class of Real Recursive Functions (2008)
Olivier Bournez, Emmanuel Hainry
Abstract. Recently, using a limit schema, we presented an analog and machine independent algebraic characterization of elementary functions over the real numbers in the sense of recursive analysis....
Abstract How much can analog and hybrid systems be proved (2008)
Church thesis and its variants say roughly that all reasonable models of computation do not have more power than Turing machines. In a contrapositive way, they say that any model with super-Turing...
Chapter 1 On matrix mortality in low dimensions (2008)
Olivier Bournez, Michael Branicky
A set F = {A1,..., Am} of n × n matrices is said to be mortal if there exist integers k ≥ 1 and i1, i2,..., ik ∈ {1,..., m} such that Ai1Ai2 · · · Aik = 0. In that case F is also said to be...
Safe Recursion and Calculus over an Arbitrary (2008)
Structure Olivier Bournez, Olivier Bournez, Paulin De Naurois
In this paper, we show that the Bellantoni and Cook characterization of polynomial time computable functions in term of safe recursive functions can be transfered to the model of computation over an...
On the Mortality Problem for Matrices of Low Dimensions (2008)
Olivier Bournez, Michael Branicky
In this paper, we discuss the existence of an algorithm to decide if a given set of 2 2 matrices is mortal. A set F = fA1 ; : : : ; Amg of square matrices is said to be mortal if there exist an...
A survey on continuous time computations (2008)
Olivier Bournez, Manuel L. Campagnolo
Abstract. We provide an overview of theories of continuous time computation. These theories allow us to understand both the hardness of questions related to continuous time dynamical systems and the...
UNIVERSITÀ DI PISA Ecole Doctorale de Sciences Mathématiques de Paris Centre (2008)
Doctorat En Informatique, Stefano Galatolo, Olivier Bournez, Abbas Edalat, Peter Gács, Olivier Bournez, ...
Mathieu HOYRUP Calculabilité, aléatoire et théorie ergodique sur les espaces métriques Calcolabilità, aleatorio e teoria ergodica in spazi metrici Thèse dirigée par
Laboratoire de l'Informatique du Paralllisme (2007)
Ecole Normale, Suprieure Lyon, Olivier Bournez, Olivier Bournez, Michel Cosnard, Michel Cosnard
Unit de recherche associe au CNRS n1398 On the computational power and super-Turing capabilities of dynamical systems
Deciding Stability and Mortality of Piecewise Ane Dynamical Systems (2007)
Vincent Blondel Olivier, Olivier Bournez, Pascal Koiran
This paper studies problems such as: given a discrete time dynamical system of the form x(t + 1) = f(x(t)) where f : R
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
stability of saturated linear dynamical
The stability of saturated linear dynamical systems (2007)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
is undecidable
PROCEEDINGS OF THE IEEE 1 Effective Synthesis of Switching Controllers for Linear Systems (2007)
Eugene Asarin, Olivier Bournez, Thao Dang, Oded Maler, Amir Pnueli
Abstract — In this work we suggest a novel methodology for synthesizing switching controllers for continuous and hybrid systems whose dynamics are defined by linear differential equations. We...
Michael Branicky, Michael Branicky, Olivier Bournez, Olivier Bournez, ...
SPI On the mortality problem for matrices of low dimensions
Modèles Continus. Calculs. Algorithmique Distribuée. (2007)
Les systèmes dynamiques continus permettent de modéliser de nombreux systèmes physiques, biologiques, ou issus de l'informatique distribuée. Nous nous intéressons à leur pouvoir de...
Implicit Complexity over an Arbitrary Structure: Quantifier Alternations (2006)
Bournez, Olivier, Cucker, Felipe, Jacobé De Naurois, Paulin, Marion, Jean-Yves
We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the...
Implicit Complexity over an Arbitrary Structure: Quantifier Alternations (2006)
Bournez, Olivier, Cucker, Felipe, Jacobé De Naurois, Paulin, Marion, Jean-Yves
We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the...
Bournez, Olivier, Florent, Garnier, Kirchner, Claude
Nous présentons une méthode de preuve qui permet de montrer la terminaison en temps moyen fini d'un algorithme probabiliste et distribué utilisé par le protocole WI-FI 802.11b.
Bournez, Olivier, Florent, Garnier, Kirchner, Claude
Nous présentons une méthode de preuve qui permet de montrer la terminaison en temps moyen fini d'un algorithme probabiliste et distribué utilisé par le protocole WI-FI 802.11b.
Bournez, Olivier, Florent, Garnier, Kirchner, Claude
Nous présentons une méthode de preuve qui permet de montrer la terminaison en temps moyen fini d'un algorithme probabiliste et distribué utilisé par le protocole WI-FI 802.11b.
Modèles Continus. Calculs. Algorithmique Distribuée. (2006)
Les systèmes dynamiques continus permettent de modéliser de nombreux systèmes physiques, biologiques, ou issus de l'informatique distribuée. Nous nous intéressons à leur pouvoir de...
Modèles Continus. Calculs. Algorithmique Distribuée. (2006)
Les systèmes dynamiques continus permettent de modéliser de nombreux systèmes physiques, biologiques, ou issus de l'informatique distribuée. Nous nous intéressons à leur pouvoir de...
Modèles Continus. Calculs. Algorithmique Distribuée. (2006)
Les systèmes dynamiques continus permettent de modéliser de nombreux systèmes physiques, biologiques, ou issus de l'informatique distribuée. Nous nous intéressons à leur pouvoir de...
Recursive analysis characterized as a class of real recursive functions (2006)
Olivier Bournez, Emmanuel Hainry
Recently, using a limit schema, we presented an analog and machine independent algebraic characterization of elementary functions over the real numbers in the sense of recursive analysis. In a...
How much can analog and hybrid systems be proved (super-)Turing (2006)
Church thesis and its variants say roughly that all reasonable models of computation do not have more power than Turing Machines. In a contrapositive way, they say that any model with super-Turing...
Olivier Bournez, Manuel L. Campagnolo, Daniel S. Graça, Emmanuel Hainry
In this paper we revisit one of the first models of analog computation, Shannon’s General Purpose Analog Computer (GPAC). The GPAC has often been argued to be weaker than computable analysis. As...
Elementarily Computable Functions Over the Real Numbers and R-Sub-Recursive Functions (2005)
Bournez, Olivier, Hainry, Emmanuel
We present an analog and machine-independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to...
Elementarily Computable Functions Over the Real Numbers and R-Sub-Recursive Functions (2005)
Bournez, Olivier, Hainry, Emmanuel
We present an analog and machine-independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to...
How much can analog and hybrid systems be proved (super-)Turing (2005)
Church thesis and its variants say roughly that all reasonable models of computation do not have more power than Turing Machines. In a contrapositive way, they say that any model with super-Turing...
Recursive Analysis Characterized as a Class of Real Recursive Functions (2005)
Bournez, Olivier, Hainry, Emmanuel
Recently, using a limit schema, we presented an analog and machine independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive...
How much can analog and hybrid systems be proved (super-)Turing (2005)
Church thesis and its variants say roughly that all reasonable models of computation do not have more power than Turing Machines. In a contrapositive way, they say that any model with super-Turing...
Recursive Analysis Characterized as a Class of Real Recursive Functions (2005)
Bournez, Olivier, Hainry, Emmanuel
Recently, using a limit schema, we presented an analog and machine independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive...
Proving Positive Almost-Sure Termination (2005)
Bournez, Olivier, Garnier, Florent
In order to extend the modeling capabilities of rewriting systems, it is rather natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules...
Proving Positive Almost-Sure Termination (2005)
Bournez, Olivier, Garnier, Florent
In order to extend the modeling capabilities of rewriting systems, it is rather natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules...
Elementarily computable functions over the real numbers and R-sub-recursive functions (2005)
Olivier Bournez, Emmanuel Hainry
We present an analog and machine-independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to...
Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time (2005)
Bournez, Olivier, Cucker, Felipe, De Naurois, Paulin Jacobé, Marion, Jean-Yves
We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of...
Bournez, Olivier, Cucker, Felipe, Jacobé De Naurois, Paulin, Marion, Jean-Yves
We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L.Blum, M.Shub and S.Smale. We show that the levels...
Bournez, Olivier, Cucker, Felipe, Jacobé De Naurois, Paulin, Marion, Jean-Yves
We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L.Blum, M.Shub and S.Smale. We show that the levels...
Stratégies de réécriture probabiliste dans ELAN4 (2004)
Bournez, Olivier, Garnier, Florent, Kirchner, Claude
Ce rapport décrit l'implantation des stratégies de réécriture probabilistes dans le prototype ELAN 4. Il rappelle l'apport de ces stratégies et présente quelques exemples.
Stratégies de réécriture probabiliste dans ELAN4 (2004)
Bournez, Olivier, Garnier, Florent, Kirchner, Claude
Ce rapport décrit l'implantation des stratégies de réécriture probabilistes dans le prototype ELAN 4. Il rappelle l'apport de ces stratégies et présente quelques exemples.
Stratégies de réécriture probabiliste dans ELAN4 (2004)
Bournez, Olivier, Garnier, Florent, Kirchner, Claude
Ce rapport décrit l'implantation des stratégies de réécriture probabilistes dans le prototype ELAN 4. Il rappelle l'apport de ces stratégies et présente quelques exemples.
Rewriting logic and probabilities (2003)
Olivier Bournez, Mathieu Hoyrup
Abstract Rewriting Logic has shown to provide a general and elegant framework for unifying a wide variety of models, including concurrency models and deduction systems. In order to extend the...
Rewriting logic and probabilities (2003)
Olivier Bournez, Mathieu Hoyrup
Abstract Rewriting Logic has shown to provide a general and elegant framework for unifying a wide variety of models, including concurrency models and deduction systems. In order to extend the...
Probabilistic rewrite strategies: Applications to elan (2002)
Olivier Bournez, Claude Kirchner, Loria Inria
Abstract. Recently rule based languages focussed on the use of rewriting as a modeling tool which results in making specifications executable. To extend the modeling capabilities of rule based...
Verification of Timed Automata Using Rewrite Rules and Strategies (2001)
Beffara, Emmanuel, Bournez, Olivier, Kacem, Hassen, Kirchner, Claude
ELAN is a powerful language and environment for specifying and prototyping deduction systems in a language based on rewrite rules controlled by strategies. Timed automata is a class of continuous...
On the representation of timed polyhedra (2000)
Abstract. In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in...
On the Representation of Timed Polyhedra (2000)
. In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in...
Approximate Reachability Analysis of Piecewise-Linear Dynamical Systems (2000)
Eugene Asarin, Olivier Bournez, Thao Dang, Oded Maler
. In this paper we describe an experimental system called d=dt for approximating reachable states for hybrid systems whose continuous dynamics is defined by linear differential equations. We use an...
Effective Synthesis of Switching Controllers for Linear Systems (2000)
Eugene Asarin, Olivier Bournez, Thao Dang, Oded Maler, Amir Pnueli
In this work we suggest a novel methodology for synthesizing switching controllers for continuous and hybrid systems whose dynamics are defined by linear differential equations. We formulate the...
Approximate reachability analysis of piecewise-linear dynamical systems (2000)
Eugene Asarin, Olivier Bournez, Thao Dang, Oded Maler
Abstract. In this paper we describe an experimental system called d=dt for approximating reachable states for hybrid systems whose continuous dynamics is de ned by linear di erential equations. We...
On the mortality problem for matrices of low dimensions. (1999)
Bournez, Olivier, Branicky, Michael
(eng) In this paper, we discuss the existence of an algorithm to decide if a given set of 2 \times 2 matrices is mortal: a set F=\{A_1,\dots,A_m\} of 2 \times 2 matrices is said to be...
Deciding stability and mortality of piecewise affine dynamical systems. (1999)
Blondel, Vincent, Bournez, Olivier, Koiran, Pascal, Papadimitriou, Christos H., Tsitsiklis, John N.
(eng) We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are...
Orthogonal polyhedra: Representation and computation (1999)
Olivier Bournez, Oded Maler, Amir Pnueli
Abstract. In this paper we investigate orthogonal polyhedra, i.e. polyhedra which are finite unions of full-dimensional hyper-rectangles. We define representation schemes for these polyhedra based on...
Orthogonal Polyhedra: Representation and Computation (1999)
Olivier Bournez, Oded Maler, Amir Pnueli
. In this paper we investigate orthogonal polyhedra, i.e. polyhedra which are finite unions of full-dimensional hyper-rectangles. We define representation schemes for these polyhedra based on their...
Deciding Stability and Mortality of Piecewise Ane Dynamical Systems (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Vincent Blondel Olivier, Olivier Bournez, ...
We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems dened by iteration of piecewise-ane maps are undecidable. Such...
The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)
Vincent Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...
The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)
Vincent Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
mptoticallystable?),Mortality (doalltrajectoriesgo through theorigin?),andNilpotence(doesthereexistaniteratef k off such thatf k 0?). Itiswell-known thatvarioustypesofdynamicalsystems,such...
The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...
Deciding Stability and Mortality of Piecewise Affine Dynamical Systems (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Vincent Blondel, Olivier Bournez, ...
We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are undecidable. Such...
Orthogonal Polyhedra: Representation and Computation (1999)
Olivier Bournez, Oded Maler, Amir Pnueli
. In this paper we investigate orthogonal polyhedra, i.e. polyhedra which are finite unions of full-dimensional hyper-rectangles. We define representation schemes for these polyhedra based on their...
E-mail: Pascal.Koiran ens-lyon.fr (1999)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...
Orthogonal polyhedra: Representation and computation (1999)
Olivier Bournez, Oded Maler, Amir Pnueli
Abstract. In this paper we investigate orthogonal polyhedra, i.e. polyhedra which are nite unions of full-dimensional hyper-rectangles. We de ne representation schemes for these polyhedra based on...
Deciding Stability and Mortality of Piecewise Affine Dynamical Systems (1998)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis
This paper studies problems such as: given a discrete time dynamical system of the form x(t + 1) = f(x(t)) where f : R
Patrick Gros, Olivier Bournez, Edmond Boyer, Gravir Cnrs, Inria Rhone Alpes
Image matching consists of finding features in different images that represent the same feature of the observed scene. It is a basic process in vision whenever several images are used. This paper...
Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. (1997)
(eng) We study the computational power of rational Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be...
Some bounds on the computational power of Piecewise Constant Derivative systems. (1997)
Ecole Normale, Ecole Normale, Suprieure Lyon, Suprieure Lyon, Olivier Bournez, Olivier Bournez
We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as...
Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy (1997)
Ecole Normale, Suprieure Lyon, Olivier Bournez
We pursue the study of the computational power of Piecewise Constant Derivative (PCD) systems started in [5, 6]. PCD systems are dynamical systems defined by a piecewise constant differential...
Some bounds on the computational power of Piecewise Constant Derivative systems. (1997)
We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as...
) Olivier Bournez Laboratoire de l'Informatique du Parall'elisme Ecole Normale Sup'erieure de Lyon 46, All'ee d'Italie F-69364 Lyon Cedex 07, France obournez@lip.ens-lyon.fr...
Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy (1997)
In this paper, we characterize the computational power of dynamical systems with piecewise constant derivatives (PCD) considered as computational machines working on a continuous real space with a...
On the Computational Power of Dynamical Systems and Hybrid Systems (1996)
Olivier Bournez, Michel Cosnard
We explore the simulation and computational capabilities of discrete and continuous dynamical systems. We introduce and compare several notions of simulation between discrete and continuous systems....
On the computational power and super-turing capabilities of dynamical systems. (1995)
Bournez, Olivier, Cosnard, Michel
(eng) We explore the simulation and computational capabilities of dynamical systems. We first introduce and compare several notions of simulation between discrete systems. We give a general framework...
Using geometric quasi-invariants to match and model images of line segments (1995)
Gros, Patrick, Bournez, Olivier, Boyer, Edmond
Image matching consists in finding in two images the features which represent a same feature of the observed scene. It is a basic process of vision as soon as several images are used. use of local...
Using geometric quasi-invariants to match and model images of line segments (1995)
Gros, Patrick, Bournez, Olivier, Boyer, Edmond
Image matching consists in finding in two images the features which represent a same feature of the observed scene. It is a basic process of vision as soon as several images are used. use of local...
Using geometric quasi-invariants to match and model images of line segments (1995)
Gros, Patrick, Bournez, Olivier, Boyer, Edmond
Image matching consists in finding in two images the features which represent a same feature of the observed scene. It is a basic process of vision as soon as several images are used. use of local...
capabilities of dynamical systems (1995)
Ecole Normale, Supérieure Lyon, Olivier Bournez, Michel Cosnard, Olivier Bournez, Michel Cosnard
Unité de recherche associée au CNRS n°1398 On the computational power and super-Turing capabilities of dynamical systems