Search

Your search keyword '"Olivier Bournez"' showing total 39 results
Start Over Author "Olivier Bournez" Topic mathematics
39 results on '"Olivier Bournez"'

1. Playing With Population Protocols

Author

Xavier Koegler, Johanne Cohen, Jérémie Chalopin, and Olivier Bournez

Subjects
Mathematics, QA1-939, Electronic computers. Computer science, QA75.5-76.95
Abstract

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 finite automata, interact in pairs according to some rules. Predicates on the initial configurations that can be computed by such protocols have been characterized under several hypotheses. We discuss here whether and when the rules of interactions between agents can be seen as a game from game theory. We do so by discussing several basic protocols.

Published
2009
Full Text
View/download PDF

2. On the functions generated by the general purpose analog computer

Author

Daniel S. Graça, Olivier Bournez, and Amaury Pouly

Subjects
FOS: Computer and information sciences, Discrete mathematics, Class (set theory), 010102 general mathematics, Univariate, Dynamical Systems (math.DS), Function (mathematics), Computational Complexity (cs.CC), Space (mathematics), 01 natural sciences, Stability (probability), Domain (mathematical analysis), Computer Science Applications, Theoretical Computer Science, 010101 applied mathematics, Computer Science - Computational Complexity, Range (mathematics), Computational Theory and Mathematics, FOS: Mathematics, Mathematics - Dynamical Systems, 0101 mathematics, Differential (infinitesimal), Information Systems, Mathematics
Abstract

We consider the General Purpose Analog Computer (GPAC), introduced by Claude Shannon in 1941 as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. We extend the model properly to a model of computation not restricted to univariate functions (i.e. functions $f: \mathbb{R} \to \mathbb{R}$) but also to the multivariate case of (i.e. functions $f: \mathbb{R}^n \to \mathbb{R}^m$), and establish some basic properties. In particular, we prove that a very wide class of (continuous and discontinuous) functions can be uniformly approximated over their full domain. Technically: we generalize some known results about the GPAC to the multidimensional case: we extend naturally the notion of \emph{generable} function, from the unidimensional to the multidimensional case. We prove a few stability properties of this class, mostly stability by arithmetic operations, composition and ODE solving. We establish that generable functions are always analytic. We prove that generable functions include some basic (useful) generable functions, and that we can (uniformly) approximate a wide range of functions this way. This extends some of the results from \cite{Sha41} to the multidimensional case, and this also strengths the approximation result from \cite{Sha41} over a compact domain to a uniform approximation result over unbounded domains. We also discuss the issue of constants, and we prove that involved constants can basically assumed to always be polynomial time computable numbers.

Published
2017
Full Text
View/download PDF

3. Ordinary Differential Equations & Computability

Author

Olivier Bournez

Subjects
Computational complexity theory, musculoskeletal, neural, and ocular physiology, Computation, Computability, Numerical analysis, macromolecular substances, 0102 computer and information sciences, 01 natural sciences, nervous system, 010201 computation theory & mathematics, Ordinary differential equation, Theory of computation, Applied mathematics, Mathematics
Abstract

We review several results relating ordinary differential equations and analog models of computations.

Published
2018
Full Text
View/download PDF

4. Reachability Problems for One-Dimensional Piecewise Affine Maps

Author

Oleksiy Kurganskyy, Olivier Bournez, and Igor Potapov

Subjects
p-adic analysis, Pure mathematics, 010201 computation theory & mathematics, Reachability, 010102 general mathematics, Computer Science (miscellaneous), 0102 computer and information sciences, Piecewise affine, 0101 mathematics, 01 natural sciences, Reference model, Mathematics, Decidability
Abstract

Piecewise affine maps (PAMs) are frequently used as a reference model to discuss the frontier between known and open questions about the decidability for reachability questions. In particular, the reachability problem for one-dimensional PAM is still an open problem, even if restricted to only two intervals. As the main contribution of this paper we introduce new techniques for solving reachability problems based on [Formula: see text]-adic norms and weights as well as showing decidability for two classes of maps. Then we show the connections between topological properties for PAM’s orbits, reachability problems and representation of numbers in a rational base system. Finally we construct an example where the distribution properties of well studied sequences can be significantly disrupted by taking fractional parts after regular shifts. The study of such sequences could help with understanding similar sequences generated in PAMs or in well known Mahler’s [Formula: see text] problem.

Published
2018

5. Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length

Author

Olivier Bournez, Daniel S. Graça, and Amaury Pouly

Subjects
FOS: Computer and information sciences, 0209 industrial biotechnology, Polynomial, Computer systems organization, Computational complexity theory, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, Mathematics of computing, Computable analysis, Computing methodologies, Turing machine, symbols.namesake, 020901 industrial engineering & automation, Artificial Intelligence, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Complexity class, Time complexity, Mathematics, Theory of computation, Model of computation, Algebra, Computer Science - Computational Complexity, 010201 computation theory & mathematics, Hardware and Architecture, Control and Systems Engineering, symbols, Software, Information Systems
Abstract

The outcomes of this article are twofold. Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class P of languages computable in polynomial time in terms of differential equations with polynomial right-hand side. This result gives a purely continuous elegant and simple characterization of P. We believe it is the first time complexity classes are characterized using only ordinary differential equations. Our characterization extends to functions computable in polynomial time over the reals in the sense of Computable Analysis. Our results may provide a new perspective on classical complexity, by giving a way to define complexity classes, like P, in a very simple way, without any reference to a notion of (discrete) machine. This may also provide ways to state classical questions about computational complexity via ordinary differential equations. Continuous-Time Models of Computation. Our results can also be interpreted in terms of analog computers or analog models of computation: As a side effect, we get that the 1941 General Purpose Analog Computer (GPAC) of Claude Shannon is provably equivalent to Turing machines both in terms of computability and complexity, a fact that has never been established before. This result provides arguments in favour of a generalised form of the Church-Turing Hypothesis, which states that any physically realistic (macroscopic) computer is equivalent to Turing machines both in terms of computability and complexity.

Published
2017

6. On the number of binary-minded individuals required to compute 12

Author

Olivier Bournez and Guillaume Aupy

Subjects
Discrete mathematics, Polynomial, Continuous-time stochastic process, education.field_of_study, General Computer Science, Stochastic process, Population, Binary number, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Stochastic partial differential equation, Stochastic differential equation, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Probabilistic analysis of algorithms, education, Mathematics
Abstract

We recently obtained partial results on the computational power of population protocols when the population is assumed to be large. We studied in particular a particular protocol that we proved to converge towards 12, using weak-convergence methods for stochastic processes. In this paper, we prove that it is possible to compute 12 with precision @e>0 in a time polynomial in [email protected] using a number of agents polynomial in [email protected], with individuals that can have only two states. This is established through a general result on approximation of stochastic differential equations by a stochastic Euler-like discretization algorithm, of general interest.

Published
2011
Full Text
View/download PDF

7. Computing with Polynomial Ordinary Differential Equations

Author

Olivier Bournez, Daniel S. Graça, and Amaury Pouly

Subjects
Statistics and Probability, FOS: Computer and information sciences, Control and Optimization, General Mathematics, Open problem, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, symbols.namesake, Computable function, 0202 electrical engineering, electronic engineering, information engineering, Time complexity, Mathematics, Discrete mathematics, Numerical Analysis, Algebra and Number Theory, Applied Mathematics, Computability, Ode, 020206 networking & telecommunications, Riemann hypothesis, Computer Science - Computational Complexity, 010201 computation theory & mathematics, Ordinary differential equation, symbols, Differential algebraic equation
Abstract

In 1941, Claude Shannon introduced the General Purpose Analog Computer(GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. Following Shannon's arguments, functions generated by GPACs must be differentially algebraic. As it is known that some computable functions like Euler's $\Gamma(x)=\int_{0}^{\infty}t^{x-1}e^{-t}dt$ or Riemann's Zeta function $\zeta(x)=\sum_{k=0}^\infty \frac1{k^x}$ are not differentially algebraic, this argument has been often used to demonstrate in the past that the GPAC is less powerful than digital computation. It was proved in JOC2007, that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines. Our purpose is first to discuss the robustness of the notion of computation involved in JOC2007, by establishing that natural variants of the notion of computation from this paper leads to the same computability result. Second, to go considerations about (time) complexity, we explore several natural variants for measuring time/space complexity of a computation. Rather surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations. Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can be used as a kind of programming model, and that there is a rather nice and robust notion of ODE programming., Comment: arXiv admin note: substantial text overlap with arXiv:1601.05360

Published
2016
Full Text
View/download PDF

8. Rigorous Numerical Computation of Polynomial Differential Equations Over Unbounded Domains

Author

Daniel S. Graça, Olivier Bournez, and Amaury Pouly

Subjects
Combinatorics, Discrete mathematics, Polynomial, Computation, Mathematics::Analysis of PDEs, Value (computer science), Type (model theory), Polynomial differential equations, Mathematics
Abstract

In this abstract we present a rigorous numerical algorithm which solves initial-value problems IVPs defined with polynomial differential equations i.e.i¾?IVPs of the type $$y'=pt,y$$, $$yt_0=y_0$$, where p is a vector of polynomials for any value of t. The inputs of the algorithm are the data defining the initial-value problem, the time T at which we want to compute the solution of the IVP, and the maximum allowable error $$\varepsilon >0$$. Using these inputs, the algorithm will output a value $$\tilde{y}_T$$ such that $$\Vert \tilde{y}_T-yT\Vert \le \varepsilon $$ in time polynomial in T, $$-\log \varepsilon $$, and in several quantities related to the polynomial IVP.

Published
2016
Full Text
View/download PDF

9. Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time

Author

Olivier Bournez, Paulin Jacobé de Naurois, Felipe Cucker, Jean-Yves Marion, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Linear logic, proof networks and categorial grammars (CALLIGRAMME), and Bournez, Olivier

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Polynomial, Logic, complexity theory, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Structural complexity theory, Arts and Humanities (miscellaneous), Complexity class, 0101 mathematics, Time complexity, Blum's speedup theorem, Mathematics, implicit complexity, Discrete mathematics, Model of computation, 010102 general mathematics, Recursion (computer science), PH, Shub, Smale model, 010201 computation theory & mathematics, Hardware and Architecture, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Blum, Software
Abstract

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 partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.

Published
2005
Full Text
View/download PDF

10. Using Local Planar Geometric Invariants to Match and Model Images of Line Segments

Author

Edmond Boyer, Olivier Bournez, Patrick Gros, Modeling, localization, recognition and interpretation in computer vision (MOVI), Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble (GRAVIR - IMAG), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, and École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 0209 industrial biotechnology, business.industry, Epipolar geometry, Geometric transformation, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 02 engineering and technology, Polyhedron, 020901 industrial engineering & automation, Planar, Line segment, Computer Science::Computer Vision and Pattern Recognition, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Computer vision, Computer Vision and Pattern Recognition, Affine transformation, Artificial intelligence, Geometric hashing, business, Software, Blossom algorithm, Mathematics
Abstract

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 describes a matching algorithm for lines segments in two images. The key idea of the algorithm is to assume that the apparent motion between the two images can be approximated by a planar geometric transformation (a similarity or an affine transformation) and to compute such an approximation. Under such an assumption, local planar invariants related the kind of transformation used as approximation, should have the same value in both images. Such invariants are computed for simple segment configurations in both images and matched according to their values. A global constraint is added to ensure a global coherency between all the possible matches: all the local matches must define approximately the same geometric transformation between the two images. These first matches are verified and completed using a better and more global approximation of the apparent motion by a planar homography and an estimate of the epipolar geometry. If more than two images are considered, they are initially matched pairwise; then global matches are deduced in a second step. Finally, from a set of images representing different aspects of an object, it is possible to compare them and to compute a model of each aspect using the matching algorithm. This work uses in a new way many elements already known in vision; some of the local planar invariants used here were presented as quasi-invariants by Binford and studied by Ben-Arie in his work on thepeaking effect. The algorithm itself uses other ideas coming from the geometric hashing and the Hough algorithms. Its main limitations come from the invariants used. They are really stable when they are computed for a planar object or for many man-made objects which contain many coplanar facets and elements. On the other hand, the algorithm will probably fail when used with images of very general polyhedrons. Its main advantages are that it still works even if the images are noisy and the polyhedral approximation of the contours is not exact, if the apparent motion between the images is not infinitesimal, if they are several different motions in the scene, and if the camera is uncalibrated and its motion unknown. The basic matching algorithm is presented in Section 2, the verification and completion stages in Section 3, the matching of several images is studied in Section 4 and the algorithm to model the different aspects of an object is presented in Section 5. Results obtained with the different algorithms are shown in the corresponding sections.

Published
1998
Full Text
View/download PDF

11. On The Complexity of Bounded Time Reachability for Piecewise Affine Systems

Author

Walid Gomaa, Olivier Bournez, Amaury Pouly, and Hugo Bazille

Subjects
Discrete mathematics, Affine combination, Reachability problem, Reachability, Affine hull, Bounded function, Dimension (graph theory), Computer Science::Formal Languages and Automata Theory, Decidability, Undecidable problem, Mathematics
Abstract

Reachability for piecewise affine systems is known to be undecidable, starting from dimension 2. In this paper we investigate the exact complexity of several decidable variants of reachability and control questions for piecewise affine systems. We show in particular that the region to region bounded time versions leads to NP-complete or co-NP-complete problems, starting from dimension 2.

Published
2014
Full Text
View/download PDF

12. Computation with perturbed dynamical systems

Author

Emmanuel Hainry, Daniel S. Graça, Olivier Bournez, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Faculdade de Ciências e Tecnologia [Faro] (FCT), Universidade do Algarve (UAlg), Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Équipe Associée ComputR, and École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Theoretical computer science, Hybrid systems, Dynamical systems theory, Computer Networks and Communications, Infinitesimal, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], robustness, 0102 computer and information sciences, Dynamical system, 01 natural sciences, Turing-machines, Automata, Theoretical Computer Science, Linear dynamical system, Projected dynamical system, Recursive language, Reachable sets, Dynamical systems, 0101 mathematics, Mathematics, computational power, Computability, Achilles, Applied Mathematics, 010102 general mathematics, Arithmetical hierarchy, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Analytic-maps, Undecidability, Algebra, Computational Theory and Mathematics, 010201 computation theory & mathematics, Neural-networks, Limit set, verification, Random dynamical system, reachability
Abstract

This paper analyzes the computational power of dynamical systems robust to infinitesimal perturbations. Previous work on the subject has delved on very specific types of systems. Here we obtain results for broader classes of dynamical systems (including those systems defined by Lipschitz/analytic functions). In particular we show that systems robust to infinitesimal perturbations only recognize recursive languages. We also show the converse direction: every recursive language can be robustly recognized by a computable system. By other words we show that robustness is equivalent to decidability. Highlights? We consider dynamical systems as language acceptors and as language recognizers. ? We analyze how infinitesimal perturbations on a dynamical system affect the language it accepts/recognizes. ? Languages can be robustly accepted/recognized by dynamical systems. ? A language is robustly accepted/recognized if and only if it is recursive.

Published
2013
Full Text
View/download PDF

13. Computing with Large Populations Using Interactions

Author

Pierre Fraigniaud, Xavier Koegler, Olivier Bournez, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Bournez, Olivier

Subjects
Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], education.field_of_study, Selection rule, media_common.quotation_subject, Population, 0102 computer and information sciences, 02 engineering and technology, Mobile ad hoc network, Population protocol, Infinity, 01 natural sciences, Constructive, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Networking and Internet Architecture, 020201 artificial intelligence & image processing, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Algebraic number, education, Protocol (object-oriented programming), Mathematics, media_common
Abstract

International audience; We define a general model capturing the behavior of a population of anonymous agents that interact in pairs. This model captures some of the main features of opportunistic networks, in which nodes (such as the ones of a mobile ad hoc networks) meet sporadically. For its reminiscence to Population Protocol, we call our model \emph{Large-Population Protocol}, or LPP. We are interested in the design of LPPs enforcing, for every $\nu\in[0,1]$, a proportion $\nu$ of the agents to be in a specific subset of marked states, when the size of the population grows to infinity; In which case, we say that the protocol \emph{computes} $\nu$. We prove that, for every $\nu\in[0,1]$, $\nu$ is computable by a LPP if and only if $\nu$ is algebraic. Our positive result is constructive. That is, we show how to construct, for every algebraic number $\nu\in[0,1]$, a protocol which computes $\nu$.

Published
2012

14. On the complexity of solving initial value problems

Author

Olivier Bournez, Amaury Pouly, and Daniel S. Graça

Subjects
FOS: Computer and information sciences, Polynomial, Computer Science - Numerical Analysis, Value (computer science), Mathematics::General Topology, Numerical Analysis (math.NA), Computational Complexity (cs.CC), Lipschitz continuity, Domain (mathematical analysis), Combinatorics, Computer Science - Computational Complexity, Bounded function, FOS: Mathematics, Initial value problem, Constant (mathematics), Mathematics
Abstract

In this paper we prove that computing the solution of an initial-value problem $\dot{y}=p(y)$ with initial condition $y(t_0)=y_0\in\R^d$ at time $t_0+T$ with precision $e^{-\mu}$ where $p$ is a vector of polynomials can be done in time polynomial in the value of $T$, $\mu$ and $Y=\sup_{t_0\leqslant u\leqslant T}\infnorm{y(u)}$. Contrary to existing results, our algorithm works for any vector of polynomials $p$ over any bounded or unbounded domain and has a guaranteed complexity and precision. In particular we do not assume $p$ to be fixed, nor the solution to lie in a compact domain, nor we assume that $p$ has a Lipschitz constant., Comment: 8 pages (two columns per page), submitted to ISSAC'12 conference

Published
2012

15. Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains

Author

Daniel S. Graça, Amaury Pouly, Olivier Bournez, and Bournez, Olivier

Subjects
Discrete mathematics, Differential equation, Function (mathematics), Lipschitz continuity, Computable analysis, symbols.namesake, Ordinary differential equation, Taylor series, symbols, Applied mathematics, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Time complexity, Complex plane, Mathematics
Abstract

In this paper we consider the computational complexity of solving initial-value problems defined with analytic ordinary differential equations (ODEs) over unbounded domains of Rn and Cn, under the Computable Analysis setting. We show that the solution can be computed in polynomial time over its maximal interval of definition, provided it satisfies a very generous bound on its growth, and that the function admits an analytic extension to the complex plane.

Published
2011
Full Text
View/download PDF

16. Robust computations with dynamical systems

Author

Daniel S. Graça, Emmanuel Hainry, Olivier Bournez, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Faculdade de Ciências e Tecnologia [Faro] (FCT), Universidade do Algarve (UAlg), Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Petr Hlineny and Antonin Kucera, and Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)

Subjects
computable analysis, Dynamical systems theory, Reachability problem, Differential equation, Infinitesimal, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], MathematicsofComputing_NUMERICALANALYSIS, model-checking, 0102 computer and information sciences, 01 natural sciences, Computable analysis, Turing machine, symbols.namesake, Analog computations, Applied mathematics, 0101 mathematics, Mathematics, Discrete mathematics, 010102 general mathematics, Lipschitz continuity, Decidability, Model-checking, 010201 computation theory & mathematics, analog computation, symbols, verification, Veri cation, Computer Science::Formal Languages and Automata Theory
Abstract

International audience; In this paper we discuss the computational power of Lipschitz dynamical systems which are robust to infinitesimal perturbations. Whereas the study in [1] was done only for not-so-natural systems from a classical mathematical point of view (discontinuous differential equation systems, discontinuous piecewise affine maps, or perturbed Turing machines), we prove that the results presented there can be generalized to Lipschitz and computable dynamical systems. In other words, we prove that the perturbed reachability problem (i.e. the reachability problem for systems which are subjected to infinitesimal perturbations) is co-recursively enumerable for this kind of systems. Using this result we show that if robustness to infinitesimal perturbations is also required, the reachability problem becomes decidable. This result can be interpreted in the following manner: undecidability of verification doesn't hold for Lipschitz, computable and robust systems. We also show that the perturbed reachability problem is co-r.e. complete even for C ∞ -systems.

Published
2010
Full Text
View/download PDF

17. Distributed Learning of Equilibria in a Routing Game

Author

Johanne Cohen, Olivier Bournez, Dominique Barth, Octave Boussaton, Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Theoretical adverse computations, and safety (CARTE), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-05-SSIA-0016,SOGEA,Sécurité des Jeux. Equilibres et Algorithmes Répartis.(2005), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Lyapunov function, TheoryofComputation_MISCELLANEOUS, Mathematical optimization, Computer Science::Computer Science and Game Theory, Differential equation, 0102 computer and information sciences, 01 natural sciences, Nash equilibria, Theoretical Computer Science, symbols.namesake, 0502 economics and business, Convergence (routing), 050207 economics, Mathematics, Lyapunov stability, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 05 social sciences, ComputingMilieux_PERSONALCOMPUTING, learning algorithm, 010201 computation theory & mathematics, Hardware and Architecture, Distributed algorithm, Nash equilibrium, symbols, weak convergence, Routing (electronic design automation), routing game, Game theory, Software
Abstract

International audience; We focus on the problem of learning equilibria in a particular routing game similar to the Wardrop traffic model. We describe a routing game played by a large number of players and present a distributed learning algorithm that we prove to converge weakly to equilibria for the system. The proof of convergence is based on a differential equation governing the global evolution of the system that is inferred from all the local evolutions of the agents in play. We prove that the differential equation converges with the help of Lyapunov techniques.

Published
2009
Full Text
View/download PDF

18. Distributed Learning of Wardrop Equilibria

Author

Dominique Barth, Olivier Bournez, Johanne Cohen, Octave Boussaton, Cohen épouse Bournez, Johanne, ARA Sécurité des systèmes embarqués et Intelligence Ambiante - Sécurité des Jeux. Equilibres et Algorithmes Répartis. - - SOGEA2005 - ANR-05-SSIA-0016 - SSIA - VALID, Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS), Theoretical adverse computations, and safety (CARTE), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-05-SSIA-0016,SOGEA,Sécurité des Jeux. Equilibres et Algorithmes Répartis.(2005), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Lyapunov function, TheoryofComputation_MISCELLANEOUS, game theory, Mathematical optimization, Computer Science::Computer Science and Game Theory, Differential equation, Evolutionary game theory, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Nash Equilibrium, symbols.namesake, Strategy, Wardrop network, 010201 computation theory & mathematics, Nash equilibrium, Convergence (routing), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, symbols, Distributed learning, Game theory, Mathematics
Abstract

International audience; We consider the problem of learning equilibria in a well known game theoretic traffic model due to Wardrop. We consider a distributed learning algorithm that we prove to converge to equilibria. The proof of convergence is based on a differential equation governing the global macroscopic evolution of the system, inferred from the local microscopic evolutions of agents. We prove that the differential equation converges with the help of Lyapunov techniques.

Published
2008

19. Proving Positive Almost Sure Termination Under Strategies

Author

Florent Garnier, Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and Frank Pfenning

Subjects
Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Reduction (recursion theory), Probabilistic logic, Termination problem, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, 010201 computation theory & mathematics, restrict, 0202 electrical engineering, electronic engineering, information engineering, Calculus, 020201 artificial intelligence & image processing, Rewriting, Markov decision process, Mathematics
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. Termination was considered under arbitrary unrestricted policies. Policies correspond to strategies for non-probabilistic rewrite systems. This is often natural or more useful to restrict policies to a subclass. We introduce the notion of positive almost sure termination under strategies, and we provide sufficient criteria to prove termination of a given probabilitic rewrite system under strategies. This is illustrated with several examples.

Published
2006
Full Text
View/download PDF

20. Implicit Complexity over an Arbitrary Structure: Quantifier Alternations

Author

Paulin Jacobé de Naurois, Jean-Yves Marion, Felipe Cucker, Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Linear logic, proof networks and categorial grammars (CALLIGRAMME), and Bournez, Olivier

Subjects
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], blum shub smale model, 0102 computer and information sciences, complexité, 01 natural sciences, Theoretical Computer Science, Combinatorics, logical characterizations, Implicit complexity, caractérisations logiques, Computer Science::Logic in Computer Science, Complexity class, modèles de blum shub et smale, 0101 mathematics, Predicative expression, Time complexity, Mathematics, Discrete mathematics, Polynomial hierarchy, BSS computation, Model of computation, 010102 general mathematics, Arbitrary structures, Computer Science Applications, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, Safe recursion, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Minification, complexity, Information Systems
Abstract

Rapport interne.; 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 of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.

Published
2006

21. The General Purpose Analog Computer and Computable Analysis are Two Equivalent Paradigms of Analog Computation

Author

Manuel L. Campagnolo, Emmanuel Hainry, Daniel S. Graça, Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), and Bournez, Olivier

Subjects
Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computable number, Computation, 010102 general mathematics, Analog computer, 0102 computer and information sciences, 01 natural sciences, Computable analysis, law.invention, Algebra, Turing machine, symbols.namesake, Computable function, Real-valued function, 010201 computation theory & mathematics, law, symbols, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], 0101 mathematics, Mathematics, Church's thesis
Abstract

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 main contribution, we show that if we change the notion of GPAC-computability in a natural way, we compute exactly all real computable functions (in the sense of computable analysis). Moreover, since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions can be defined by such models.

Published
2006

22. From Chemical Rules to Term Rewriting

Author

Olivier Bournez, Hélène Kirchner, Liliana Ibanescu, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Bournez, Olivier, and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)

Subjects
Theoretical computer science, General Computer Science, 0102 computer and information sciences, 02 engineering and technology, Prefix grammar, automated generation of chemical reaction mechanisms, 01 natural sciences, Theoretical Computer Science, cyclic labeled graph, Strategy language, rule-based programming, Semi-Thue system, Computer Science::Logic in Computer Science, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Symbolic Computation, strategy language, Mathematics, term and graph rewriting, Graph rewriting, Graph, Abstract semantic graph, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Confluence, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, Rewriting, MathematicsofComputing_DISCRETEMATHEMATICS, Computer Science(all)
Abstract

In this paper, rule-based programming is explored in the field of automated generation of chemical reaction mechanisms. We explore a class of graphs and a graph rewriting relation where vertices are preserved and only edges are changed. We show how to represent cyclic labeled graphs by decorated labeled trees or forests, then how to transform trees into terms. A graph rewriting relation is defined, then simulated by a tree rewriting relation, which can be in turn simulated by a rewriting relation on equivalence classes of terms. As a consequence, this kind of graph rewriting can be implemented using term rewriting. This study is motivated by the design of the GasEl system for the generation of kinetics reactions mechanisms. In GasEl, chemical reactions correspond to graph rewrite rules and are implemented by conditional rewriting rules in ELAN. The control of their application is done through the ELAN strategy language.

Published
2005

23. Elementarily Computable Functions Over the Real Numbers and R-Sub-Recursive Functions

Author

Olivier Bournez, Emmanuel Hainry, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Computability, General Computer Science, Real analysis, Computable number, 010102 general mathematics, 0102 computer and information sciences, 01 natural sciences, μ-recursive function, Computable analysis, Theoretical Computer Science, Algebra, μ operator, Computable function, Analog computations, 010201 computation theory & mathematics, [INFO]Computer Science [cs], 0101 mathematics, Algebraic number, Recursive analysis, Real recursive functions, Analysis, Mathematics, Real number
Abstract

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 the smallest class of functions that contains some basic functions, and closed by composition, linear integration, and a simple limit schema.We generalize this result to all higher levels of the Grzegorczyk Hierarchy.This paper improves several previous partial characterizations and has a dual interest:•Concerning recursive analysis, our results provide machine-independent characterizations of natural classes of computable functions over the real numbers, allowing to define these classes without usual considerations on higher-order (type 2) Turing machines.•Concerning analog models, our results provide a characterization of the power of a natural class of analog models over the real numbers and provide new insights for understanding the relations between several analog computational models.

Published
2005
Full Text
View/download PDF

24. An analog Characterization of Elementarily Computable Functions Over the Real Numbers

Author

Olivier Bournez, Emmanuel Hainry, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), Loria, Publications, Diaz, Josep and Karhumäki, Juhani and Lepisto, Arto and Sannella, Donald Theodore, Diaz, Josep and Karhumäki, Juhani and Lepisto, Arto and Sannella, Donald Theodore, and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, computability, Real analysis, Computable number, analog models, 010102 general mathematics, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], modèles analogiques, Grzegorczyk hierarchy, 0102 computer and information sciences, complexité, 01 natural sciences, μ-recursive function, Computable analysis, μ operator, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Computable function, Real-valued function, 010201 computation theory & mathematics, calculabilité, 0101 mathematics, complexity, Mathematics
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; We present an analog and machine-independent algebraic characterizations of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to the smallest class of functions that contains some basic functions, and closed by composition, linear integration, and a simple limit schema. We generalize this result to all higher levels of the Grzegorczyk Hierarchy. Concerning recursive analysis, our results provide machine-independent characterizations of natural classes of computable functions over the real numbers, allowing to define these classes without usual considerations on higher-order (type 2) Turing machines. Concerning analog models, our results provide a characterization of the power of a natural class of analog models over the real numbers.

Published
2004

25. Tailoring Recursion to Characterize Non-Deterministic Complexity Classes Over Arbitrary Structures

Author

Felipe Cucker, Jean-Yves Marion, Olivier Bournez, P. de Jacobe Naurois, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Linear logic, proof networks and categorial grammars (CALLIGRAMME), Bournez, Olivier, and Loria, Publications

Subjects
Polynomial, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, complexité, 01 natural sciences, Mutual recursion, Combinatorics, Structural complexity theory, Computer Science::Logic in Computer Science, Complexity class, 0101 mathematics, Predicative expression, Mathematics, implicit complexity, Polynomial hierarchy, Discrete mathematics, 010102 general mathematics, complexité implicite, Recursion (computer science), bss model, 16. Peace & justice, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], PH, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, modèle bss, complexity
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; 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 of the polynomial hierarchy correspond to safe recursion with predicative minimization. The levels of the digital polynomial hierarchy correspond to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.

Published
2004
Full Text
View/download PDF

26. Rewriting Logic and Probabilities

Author

Olivier Bournez, Mathieu Hoyrup, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Robert Nieuwenhuis, and Loria, Publications

Subjects
Theoretical computer science, Existential quantification, Concurrency, probabilités, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, logique réécriture, probabilities, Probabilistic logic, 020207 software engineering, Rule-based system, 16. Peace & justice, rewriting logic, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Confluence, Probabilistic CTL, Computer Science::Programming Languages, Rewriting, Natural language
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; 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 modeling capabilities of rule based languages, it is natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules subject to probabilities leads to numerous questions about the underlying notions and results. In this paper, we discuss whether there exists a notion of probabilistic rewrite system with an associated notion of probabilistic rewriting logic.

Published
2003

27. Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time

Author

Felipe Cucker, Jean-Yves Marion, Paulin Jacobé de Naurois, Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Linear logic, proof networks and categorial grammars (CALLIGRAMME), Andrew D. Gordon, and Loria, Publications

Subjects
Discrete mathematics, Polynomial, Computability, Model of computation, 010102 general mathematics, récursion sûre, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], blum shub smale model, 0102 computer and information sciences, Decision problem, complexité, 01 natural sciences, Combinatorics, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Computable function, 010201 computation theory & mathematics, Complexity class, modèle de blum shub smale, 0101 mathematics, complexity, Time complexity, Blum's speedup theorem, safe recursion, Mathematics
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; 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 partial recursive functions over any arbitrary structure. We show that polynomial time computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions.

Published
2003

28. On the mortality problem for matrices of low dimensions

Author

Olivier Bournez, Michael S. Branicky, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, Reachability problem, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Decision Problem, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Square matrix, Theoretical Computer Science, Combinatorics, Set (abstract data type), 020901 industrial engineering & automation, Integer, Rational Entry, Composition Problem, Mathematics, Discrete mathematics, Computability, Turing Machine, Reachability Problem, State (functional analysis), 2 × 2 real matrices, Computational Theory and Mathematics, 010201 computation theory & mathematics, Theory of computation, Computer Science::Formal Languages and Automata Theory
Abstract

International audience; 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=s ¼,A_ms>$ of square matrices is said to be \motnouv{mortal} if there exist an integer $k >³ 1$ and some integers $i_1,i_2,>¼,i_k >Î s ¼, ms>$ with $A_{i_1} A_{i_2} s~ A_{i_k}=0$. We survey this problem and propose some new extensions. We prove the problem to be BSS-undecidable for real matrices and Turing-decidable for two rational matrices. We relate the problem for rational matrices to the entry-equivalence problem, to the zero-in-the-corner problem, and to the reachability problem for piecewise-affine functions. Finally, we state some NP-completeness results.

Published
2002
Full Text
View/download PDF

29. A Generalization of Equational Proof Theory?

Author

Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), H. Hermanns, R. Segala, and Loria, Publications

Subjects
Discrete mathematics, logique floue, Generalization, 010102 general mathematics, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Probabilistic logic, Rule-based system, 02 engineering and technology, Term (logic), 01 natural sciences, rewriting, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Proof theory, 0202 electrical engineering, electronic engineering, information engineering, Calculus, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, Rewriting, Structural proof theory, fuzzy logic, 0101 mathematics, Rule of inference, Mathematics, réécriture
Abstract

Rule based languages focussed in last decade on the use of term rewriting as a modeling tool [5]. To extend modeling capabilities of these languages, we explored recently the possibility of making the rule applications subject to probabilistic choices [2]. Dealing with rewriting with probabilistic firing of rules leads to numerous problems about the understanding of the underlying theoretical notions and results. In [2], we started to discuss what could be the generalizations of the classical notions in rewriting community for abstract reduction systems [1]. The next natural step is to understand if a generalization of equational proof theory for probabilistic systems exists. Our first attempt to do so yielded the theory which is presented in this abstract and which is actually closer to fuzzy logic than probabilities [3].

Published
2002

30. Deciding stability and mortality of piecewise affine dynamical systems

Author

Pascal Koiran, Olivier Bournez, Vincent D. Blondel, John N. Tsitsiklis, Christos H. Papadimitriou, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Imagerie Paramétrique (LIP), Université Pierre et Marie Curie - Paris 6 (UPMC)-IFR58-Centre National de la Recherche Scientifique (CNRS), Droit et changement social (DCS), Université de Nantes - UFR Droit et Sciences Politiques (UFR DSP), and Université de Nantes (UN)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, Hybrid systems, General Computer Science, Dynamical systems theory, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Decidability, 0102 computer and information sciences, 02 engineering and technology, Dynamical system, 01 natural sciences, Theoretical Computer Science, Piecewise linear systems, Discrete system, 020901 industrial engineering & automation, Stability theory, calculabilité, Mortality, stabilit, Mathematics, Discrete mathematics, computability, Function (mathematics), stability, Discrete dynamical systems, Undecidable problem, Discrete time and continuous time, 010201 computation theory & mathematics, Piecewise affine systems, Computer Science::Formal Languages and Automata Theory, Computer Science(all)
Abstract

In this paper we study problems such as: given a discrete time dynamical system of the form x(t + 1)= f(x(t)) where f: R-n --> R-n is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n greater than or equal to2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that AM-activity and Stability become decidable in dimension 1 for continuous functions. (C) 2001 Elsevier Science B.V. All rights reserved.

Published
2001
Full Text
View/download PDF

31. The stability of saturated linear dynamical systems is undecidable

Author

Pascal Koiran, Vincent D. Blondel, Olivier Bournez, John N. Tsitsiklis, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Imagerie Paramétrique (LIP), Université Pierre et Marie Curie - Paris 6 (UPMC)-IFR58-Centre National de la Recherche Scientifique (CNRS), Loria, Publications, Horst Reichel, Sophie Tison, LIFL, and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)

Subjects
0209 industrial biotechnology, Pure mathematics, Dynamical systems theory, Computer Networks and Communications, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], stabilite, 0102 computer and information sciences, 02 engineering and technology, Dynamical system, 01 natural sciences, Stability (probability), dynamical system, Linear dynamical system, Theoretical Computer Science, 020901 industrial engineering & automation, Exponential stability, Convergence (routing), systèmes dynamiques, Hybrid automaton, stabilité, décidabilite, Mathematics, Discrete mathematics, computability, piecewise affine systems, Applied Mathematics, Linear system, Mathematical analysis, decidability, dynamical systems, stability, hybrid systems, mortality, Undecidable problem, Decidability, saturated linear systems, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Computational Theory and Mathematics, 010201 computation theory & mathematics, Hybrid system, système dynamique, decidabilité
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; 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 results had been known only for point-to-point properties. We prove these properties undecidable for saturated linear dynamical systems, and for continuous piecewise affine dynamical systems in dimension three. We also describe some consequences of our results on the possible dynamics of such systems.

Published
2001

32. Effective Synthesis of Switching Controllers for Linear Systems

Author

Amir Pnueli, Oded Maler, Olivier Bournez, Eugene Asarin, Thao Dang, VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF), Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Droit et changement social (DCS), Université de Nantes - UFR Droit et Sciences Politiques (UFR DSP), Université de Nantes (UN)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, systèmes hybrides, controller synthesis, Iterative method, Linear system, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 02 engineering and technology, hybrid systems, Controllability, 020901 industrial engineering & automation, Linear differential equation, Control theory, Reachability, Control system, Hybrid system, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, synthèse de controleur, Electrical and Electronic Engineering, Mathematics
Abstract

Article dans revue scientifique avec comité de lecture.; In this work, we suggest a novel methodology for synthesizing switching controllers for continuous and hybrid systems whose dynamics is defined by linear differential equations. We formulate the synthesis problem as finding the conditions upon which a controller should switch the behaviour of the system from one ``mode'' to another in order to avoid a set of bad states, an propose an abstract algorithm which solves the problem by iterative calculation of reachable states. We have implemented a concrete version of the algorithm which uses a new approximation scheme for reachability analysis for linear systems.

Published
2000

33. Some bounds on the computational power of piecewise constant derivative systems

Author

Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Dynamical systems theory, Reachability problem, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, dynamical system, Theoretical Computer Science, calculabilité, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, Mathematics, computability, modèle de calcul sur les réels, Computability, Arithmetical hierarchy, Computational Theory and Mathematics, Discrete time and continuous time, 010201 computation theory & mathematics, système dynamique, Theory of computation, Piecewise, 020201 artificial intelligence & image processing, real computational model, Constant (mathematics), Algorithm
Abstract

Article dans revue scientifique avec comité de lecture.; 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 computational machines working on a continuous space with a continuous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or as a continuous value, called continuous time. We relate the two notions of time for general PCD systems. We prove that general PCD systems are equivalent to Turing machines and linear machines in finite discrete time. We prove that the languages recognized by purely rational PCD systems in dimension $d$ in finite continuous time are precisely the languages of the $d-2^{th}$ level of the arithmetical hierarchy. Hence the reachability problem of purely rational PCD systems of dimension $d$ in finite continuous time is $\Sigma_{d-2}$-complete.

Published
1999
Full Text
View/download PDF

34. Achilles and the tortoise climbing up the hyper-arithmetical hiearchy

Author

Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Hybrid systems, General Computer Science, Dynamical systems theory, Reachability problem, Dimension (graph theory), [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 01 natural sciences, Piecewise constant, Theoretical Computer Science, Combinatorics, calculabilité, 0101 mathematics, Dynamical system (definition), Mathematics, computability, modèle de calcul sur les réels, Derivative systems, Computability, 010102 general mathematics, Hyper-arithmetical hierarchy, Arithmetical hierarchy, 010201 computation theory & mathematics, Piecewise, real computational model, Constant (mathematics), Computer Science(all)
Abstract

Article dans revue scientifique avec comité de lecture.; 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 continuous real time: we prove that piecewise constant derivative systems recognize precisely the languages of the ${\omega ^{k}} ^{th}$ (respectively: ${\omega ^{k}+1} ^{th}$) level of the hyper-arithmetical hierarchy in dimension $d=2k+3$ (respectively: $d=2k+4$), $k \ge 0$. Hence we prove that the reachability problem for PCD systems of dimension $d=2k+3$ (resp. $d=2k+4$), $k \ge 1$, is hyper-arithmetical and is $\Sigma_{\omega ^{k}} $-complete (resp. $\Sigma_{\omega ^{k}+1}$-complete).

Published
1999
Full Text
View/download PDF

35. On matrix mortality in low dimensions

Author

Michael S. Branicky, Olivier Bournez, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), V. Blondel, E. Sontag, M. Vidyasagar, J. Willems, Loria, Publications, and V. Blondel, E. Sontag, M. Vidyasagar, J. Willems

Subjects
0209 industrial biotechnology, problème matriciel, 010102 general mathematics, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 02 engineering and technology, matrix problem, 01 natural sciences, mortality, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Combinatorics, Set (abstract data type), Matrix (mathematics), 020901 industrial engineering & automation, Calculus, 0101 mathematics, mortalité, Mathematics
Abstract

A set F = {A1,…, Am} of n×n matrices is said to be mortal if there exist integers k ≥ 1 and i 1, i 2,…, i k ∈ {1,…, m} such that A i 1A i 2 ••• A i k = 0. In that case F is also said to be k-length mortal.

Published
1998

36. Some bounds on the computational power of piecewise constant derivative systems (extended abstract)

Author

Olivier Bournez

Subjects
Turing machine, symbols.namesake, Dimension (vector space), Discrete time and continuous time, Dynamical systems theory, Differential equation, Mathematical analysis, symbols, Piecewise, Applied mathematics, Constant (mathematics), Arithmetical hierarchy, Mathematics
Abstract

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 computational machines working on a continuous space with a continuous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or as a continuous value, called continuous time. We prove that the languages recognized by PCD systems in dimension d in finite continuous time are precisely the languages of the d–2 th level of the arithmetical hierarchy. Hence we provide a precise characterization of the computational power of purely rational PCD systems in continuous time according to their dimension and we solve a problem left open by [2].

Published
1997
Full Text
View/download PDF

37. Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH

Author

Olivier Bournez, Jean-Yves Marion, Felipe Cucker, Paulin Jacobé de Naurois, Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Linear logic, proof networks and categorial grammars (CALLIGRAMME), and Loria, Publications

Subjects
General Computer Science, récursion sûre, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], blum shub smale model, 0102 computer and information sciences, complexité, 01 natural sciences, Theoretical Computer Science, Structural complexity theory, Complexity class, parallel polynomial time, 0101 mathematics, Time complexity, safe recursion, Mathematics, Real number, Polynomial hierarchy, Discrete mathematics, computability, modèle blum shub smale, Computability, 010102 general mathematics, Recursion (computer science), Complexity, sequential polynomial time, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], PH, 010201 computation theory & mathematics, Computer Science(all)
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; Considering the Blum, Shub, and Smale computational model for real numbers, extended by Poizat to general structures, classical complexity can be considered as the restriction to finite structures of a more general notion of computability and complexity working over arbitrary structures. In a previous paper, we showed that the machine-independent characterization of Bellantoni and Cook of sequential polynomial time for classical complexity is actually the restriction to finite structures of a characterization of sequential polynomial time over arbitrary structures. In this paper, we prove that the same phenomenon happens for several other complexity classes: over arbitrary structures, parallel polynomial time corresponds to safe recursion with substitutions, and the polynomial hierarchy corresponds to safe recursion with predicative minimization. Our results yield machine-independent characterizations of several complexity classes subsuming previous ones when restricted to finite structures.

Full Text
View/download PDF

38. Polynomial differential equations compute all real computable functions on computable compact intervals

Author

Olivier Bournez, Daniel S. Graça, Manuel L. Campagnolo, Emmanuel Hainry, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Instituto Superior Técnico, Universidade Técnica de Lisboa (IST), Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Bournez, Olivier

Subjects
Differential equations, Statistics and Probability, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Control and Optimization, General Mathematics, 0102 computer and information sciences, General Purpose Analog Computer, 01 natural sciences, Computable analysis, Computable function, utm theorem, Analog computation, 0101 mathematics, Mathematics, Discrete mathematics, Numerical Analysis, Algebra and Number Theory, Computable number, Applied Mathematics, Computability, 010102 general mathematics, Church–Turing thesis, Recursive set, 010201 computation theory & mathematics, Test vector, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
Abstract

International audience; In the last decade, the field of analog computation has experienced renewed interest. In particular, there have been several attempts to understand which relations exist between the many models of analog computation. Unfortunately, most models are not equivalent. It is known that Euler's Gamma function is computable according to computable analysis, while it cannot be generated by Shannon's General Purpose Analog Computer (GPAC). This example has often been used to argue that the GPAC is less powerful than digital computation. However, as we will demonstrate, when computability with GPACs is not restricted to real-time generation of functions, we obtain two equivalent models of analog computation. Using this approach, it has been shown recently that the Gamma function becomes computable by a GPAC \cite{Gra04}. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.

39. Approximate reachability analysis of piecewise-linear dynamical systems?

Author

Eugene Asarin, Thao Dang, Olivier Bournez, Oded Maler, VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF), Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Nancy Lynch , Bruce H. Krogh, Loria, Publications, and Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, systèmes hybrides, Dynamical systems theory, synthesis, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 02 engineering and technology, Dynamical system, Piecewise linear function, Discrete system, reachability analysis, 020901 industrial engineering & automation, Differential inclusion, Linear differential equation, 0202 electrical engineering, electronic engineering, information engineering, systèmes dynamiques, Applied mathematics, Hybrid automaton, Mathematics, dynamical systems, hybrid systems, vérification, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], synthèse, Hybrid system, 020201 artificial intelligence & image processing, atteignabilité, Algorithm
Abstract

Colloque avec actes et comité de lecture. internationale.; International audience; In this paper we describe an experimental system called "ddt" for approximating reachable states for hybrid systems whose continuous dynamics is defined by linear differential equations. We use an approximation algorithm whose accumulation of errors during the continuous evolution is much smaller than in previously-used methods. The "ddt" system can, so far, treat non-trivial continuous systems, hybrid systems, convex differential inclusions and controller synthesis problems.

Catalog

Books, media, physical & digital resources
See catalog results