Search

In this paper we provide a characterization of the complexity class PSPACE by using a purely continuous model defined with polynomial ordinary differential equations. info:eu-repo/semantics/publishedVersion

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.

The population protocol model was introduced by Angluin \emph{et al.} as a model of passively mobile anonymous finite-state agents. This model computes a predicate on the multiset of their inputs via interactions by pairs. The original population protocol model has been proved to compute only semi-linear predicates and has been recently extended in various ways. In the community protocol model by Guerraoui and Ruppert, agents have unique identifiers but may only store a finite number of the identifiers they already heard about. The community protocol model provides the power of a Turing machine with a $O(n\log n)$ space. We consider variations on the two above models and we obtain a whole landscape that covers and extends already known results. Namely, by considering the case of homonyms, that is to say the case when several agents may share the same identifier, we provide a hierarchy that goes from the case of no identifier (population protocol model) to the case of unique identifiers (community protocol model). We obtain in particular that any Turing Machine on space $O(\log^{O(1)} n)$ can be simulated with at least $O(\log^{O(1)} n)$ identifiers, a result filling a gap left open in all previous studies. Our results also extend and revisit in particular the hierarchy provided by Chatzigiannakis \emph{et al.} on population protocols carrying Turing Machines on limited space, solving the problem of the gap left by this work between per-agent space $o(\log \log n)$ (proved to be equivalent to population protocols) and $O(\log n)$ (proved to be equivalent to Turing machines)., Comment: arXiv admin note: substantial text overlap with arXiv:1412.2497

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.

Best paper award; International audience; When seeking to understand how computation is carried out in the cell to maintain itself in its environment, process signals and make decisions, the continuous nature of protein interaction processes forces us to consider also analog computation models and mixed analog-digital computation programs. However, recent results in the theory of analog computability and complexity establish fundamental links with classical programming. In this paper, we derive from these results the strong (uniform computability) Turing completeness of chemical reaction networks over a finite set of molecular species under the differential semantics , solving a long standing open problem. Furthermore we derive from the proof a compiler of mathematical functions into elementary chemical reactions. We illustrate the reaction code generated by our compiler on trigonometric functions, and on various sigmoid functions which can serve as markers of presence or absence for implementing program control instructions in the cell and imperative programs. Then we start comparing our compiler-generated circuits to the natural circuit of the MAPK signaling network, which plays the role of an analog-digital converter in the cell with a Hill type sigmoid input/output functions.

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.

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.

We propose a formalization of generic algorithms that includes analog algorithms. This is achieved by reformulating and extending the framework of abstract state machines to include continuous-time models of computation. We prove that every hybrid algorithm satisfying some reasonable postulates may be expressed precisely by a program in a simple and expressive language.

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

Angluin et al. introduced Population protocols as a model in which n passively mobile anonymous finite-state agents stably compute a predicate on the multiset of their inputs via interactions by pairs. The model has been extended by Guerraoui and Ruppert to yield the community protocol models where agents have unique identifiers but may only store a finite number of the identifiers they already heard about. The Population protocol model only computes semi-linear predicates, whereas the community protocol model provides the power of a Turing machine with a \(O(n\log n)\) space.

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.

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.

We consider a class of fully stochastic and fully distributed algorithms, that we prove to learn equilibria in games. Indeed, we consider a family of stochastic distributed dynamics that we prove to converge weakly (in the sense of weak convergence for probabilistic processes) towards their mean-field limit, i.e an ordinary differential equation (ODE) in the general case. We focus then on a class of stochastic dynamics where this ODE turns out to be related to multipopulation replicator dynamics. Using facts known about convergence of this ODE, we discuss the convergence of the initial stochastic dynamics: For general games, there might be non-convergence, but when convergence of the ODE holds, considered stochastic algorithms converge towards Nash equilibria. For games admitting Lyapunov functions, that we call Lyapunov games, the stochastic dynamics converge. We prove that any ordinal potential game, and hence any potential game is a Lyapunov game, with a multiaffine Lyapunov function. For Lyapunov games with a multiaffine Lyapunov function, we prove that this Lyapunov function is a super-martingale over the stochastic dynamics. This leads a way to provide bounds on their time of convergence by martingale arguments. This applies in particular for many classes of games that have been considered in literature, including several load balancing game scenarios and congestion games.

The Church-Turing thesis states that any sufficiently powerful computational model which captures the notion of algorithm is computationally equivalent to the Turing machine. This equivalence usually holds both at a computability level and at a computational complexity level modulo polynomial reductions. However, the situation is less clear in what concerns models of computation using real numbers, and no analog of the Church-Turing thesis exists for this case. Recently it was shown that some models of computation with real numbers were equivalent from a computability perspective. In particular it was shown that Shannon’s General Purpose Analog Computer (GPAC) is equivalent to Computable Analysis. However, little is known about what happens at a computational complexity level. In this paper we shed some light on the connections between this two models, from a computational complexity level, by showing that, modulo polynomial reductions, computations of Turing machines can be simulated by GPACs, without the need of using more (space) resources than those used in the original Turing computation, as long as we are talking about bounded computations. In other words, computations done by the GPAC are as space-efficient as computations done in the context of Computable Analysis.

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$.

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

We propose a formalization of analog algorithms, extending the framework of abstract state machines to continuous-time models of computation.

International audience; Population protocols have been introduced by Angluin et {al.} as a model of networks consisting of very limited mobile agents that interact in pairs but with no control over their own movement. A collection of anonymous agents, modeled by finite automata, interact pairwise according to some rules that update their states. Predicates on the initial configurations that can be computed by such protocols have been characterized as semi-linear predicates. In an orthogonal way, several distributed systems have been termed in literature as being realizations of games in the sense of game theory. We investigate under which conditions population protocols, or more generally pairwise interaction rules, correspond to games. We show that restricting to asymetric games is not really a restriction: all predicates computable by protocols can actually be computed by protocols corresponding to games, i.e. any semi-linear predicate can be computed by a Pavlovian population multi-protocol.

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.

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.

International audience; We study how to reach a Nash equilibrium in a load balanc- ing scenario where each task is managed by a selfish agent and attempts to migrate to a machine which will minimize its cost. The cost of a machine is a function of the load on it. The load on a machine is the sum of the weights of the jobs running on it. We prove that Nash equilibria can be learned on that games with incomplete information, using some Lyapunov techniques.

Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a collection of anonymous agents, modeled by finite automata, that interact with one another to carry out computations, by updating their states, using some rules. Their computational power has been investigated under several hypotheses but always when restricted to finite size populations. In particular, predicates stably computable in the original model have been characterized as those definable in Presburger arithmetic. We study mathematically the convergence of population protocols when the size of the population goes to infinity. We do so by giving general results, that we illustrate through the example of a particular population protocol for which we even obtain an asymptotic development. This example shows in particular that these protocols seem to have a rather different computational power when a huge population hypothesis is considered., Submitted to Applied Mathematics and Computation. 2009

We provide an overview of theories of continuous time computation. These theories allow us to understand both the hardness of questions related to continuous time dynamical systems and the computational power of continuous time analog models. We survey the existing models, summarizing results, and point to relevant references in the literature.

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.

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.

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.

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.

Rapport interne.; In order to extend the modeling capabilities of rewriting systems, it is rather natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules subject to probabilities leads to numerous questions about the underlying notions and results. We focus here on the problem of termination of a set of probabilistic rewrite rules. A probabilistic rewrite system is said almost surely terminating if the probability that a derivation leads to a normal form is one. Such a system is said positively almost surely terminating if furthermore the mean length of a derivation is finite. We provide several results and techniques in order to prove positive almost sure termination of a given set of probabilistic rewrite rules. All these techniques subsume classical ones for non-probabilistic systems.

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.

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.

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.

Colloque avec actes et comité de lecture. internationale.; International audience; Several software systems have been developed recently for the automated generation of combustion reactions kinetic mechanisms using different representations of species and reactions and different generation algorithms. In parallel, several software systems based on rewriting have been developed for the easy modeling and prototyping of systems using rules controlled by strategies. This paper presents our current experience in using the rewrite system \ELAN\ for the automated generation of the combustion reactions mechanisms previously implemented in the \EXGAS\ kinetic mechanism generator system. We emphasize the benefits of using rewriting and rule-based programming controlled by strategies for the generation of kinetic mechanisms.

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.

Colloque avec actes et comité de lecture. internationale.; International audience; Several software systems have been developed recently for the automated generation of combustion reactions kinetic mechanisms using different representations of species and reactions and different generation algorithms. In parallel, several software systems based on rewriting have been developed for the easy modeling and prototyping of systems using rules controlled by strategies. This paper presents our current experience in using the rewrite system {\sf ELAN} for prototyping the automatic generation of the combustion reactions mechanisms previously implemented in the {\sf EXGAS} kinetic mechanism generator system. We describe how to express in {\sf ELAN} acyclic and cyclic molecules, reactants, elementary reactions and the primary mechanism for acyclic species. Examples and generated outputs are given.

Colloque avec actes et comité de lecture. internationale.; International audience; Recently rule based languages focussed on the use of rewriting as a modeling tool which results in making specifications executable. To extend the modeling capabilities of rule based languages, we explore the possibility of making the rule applications subject to probabilistic choices. We propose an extension of the Elan strategy language to deal with randomized systems. We argue through several examples that we propose indeed a natural setting to model systems with randomized choices. This leads us to interesting new problems, and we address the generalization of the usual concepts in abstract reduction systems to randomized systems.

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.

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].

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.

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.

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.

In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation.

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).