Search

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.

International audience; This chapter deals with a question in the very core of IA: what can be computed by a machine? An agreement has been reached on the answer brought by Alan Turing in 1936. Indeed, all other proposed approaches have led to exactly the same answer. Thus, there is a mathematical model of what can be done by a machine. And this has allowed to prove surprising results which feed the reflection on intelligence and machines.

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

Non standard Analysis is an area of Mathematics dealing with notions of infinitesimal and infinitely large numbers, in which many statements from classical Analysis can be expressed very naturally. Cheap non-standard analysis introduced by Terence Tao in 2012 is based on the idea that considering that a property holds eventually is sufficient to give the essence of many of its statements. Cheap non-standard analysis provides constructivity but at some (acceptable) price. Computable Analysis is a very natural tool for discussing computations over the reals, and more general constructivity in Mathematics. In a recent article, we considered computability in cheap non-standard analysis. We proved that many concepts from computable analysis as well as several concepts from computability can be very elegantly and alternatively presented in this framework. We discuss in the current article several applications of this framework: We provide alternative proofs based on this approach of several statements from computable analysis. This includes intermediate value theorem, and computability of zeros, of maximum points and of a theorem from Rice.

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

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.

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.

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.

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.

Population protocols have been introduced as a model in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. In this paper, we consider population protocols acting on families of graphs, that is to say on particular topologies. Stably computable predicates on strings of size n correspond exactly to languages of NSPACE(n), that is to say to non-deterministic space of Turing machines. Stably computable predicates on cliques correspond to semi-linear predicates, namely exactly those definable in Presburger’s arithmetic. Furthermore, we exhibit a strict hierarchy in-between when considering graphs between strings and cliques.

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.

Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger’s arithmetic.

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

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.

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.

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.

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.

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

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.

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.

Accepted for publication in International Journal of Unconventional Computing; International audience; Recursive analysis is the most classical approach to model and discuss computations over the real numbers.Recently, it has been shown that computability classes of functions in the sense of recursive analysis can be defined (or characterized) in an algebraic machine independent way, without resorting to Turing machines. In particular nice connections between the class of computable functions (and some of its sub- and sup-classes) over the reals and algebraically defined (sub- and sup-) classes of R-recursive functions à la Moore 96 have been obtained. However, until now, this has been done only at the computability level, and not at the complexity level. In this paper we provide a framework that allows us to dive into the complexity level of real functions. In particular we provide the first algebraic characterization of polynomial-time computable functions over the reals. This framework opens the field of implicit complexity of analog functions, and also provides a new reading of some of the existing characterizations at the computability level.

Cours sur les fondements de l'informatique : il se focalise sur trois domaines centraux en informatique : la logique, les modèles de calculs et la complexité. Tous ces domaines sont reliés par la question suivante : quelles sont les capacités et les limites des ordinateurs ?

International audience; We consider the verification of algorithms expressed in the Heard-Of Model, a round-based computational model for fault-tolerant distributed computing. Rounds in this model are communication-closed, and we show that every execution recording individual events corresponds to a coarser-grained execution based on global rounds such that the local views of all processes are identical in the two executions. This result helps us to substantially mitigate state-space explosion and verify Consensus algorithms using standard model checking techniques.