A Survey on Analog Models of Computation
From MaRDI portal
Publication:5024572
DOI10.1007/978-3-030-59234-9_6OpenAlexW2804728090MaRDI QIDQ5024572
Publication date: 26 January 2022
Published in: Theory and Applications of Computability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.05729
Related Items (7)
Physarum-inspired multi-commodity flow dynamics ⋮ Machines that perform measurements ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines ⋮ Projective embedding of dynamical systems: uniform mean field equations ⋮ A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations ⋮ Programming with ordinary differential equations: some first steps towards a programming language
Cites Work
- Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
- Fixed Point Techniques in Analog Systems
- The Complete Proof Theory of Hybrid Systems
- Rate-independent computation in continuous chemical reaction networks
- On Reachability for Hybrid Automata over Bounded Time
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- A Differentially Algebraic Replacement Theorem, and Analog Computability
- Efficient Turing-Universal Computation with DNA Polymers
- Alan Turing: Life and Legacy of a Great Thinker
- Some recent developments on Shannon's General Purpose Analog Computer
- Model Checking Real-Time Systems
- Axiomatizing Analog Algorithms
- Timed regular expressions
- Continuous-Time Symmetric Hopfield Nets Are Computationally Universal
- Handbook of Natural Computing
- The discrete versus continuous controversy in physics
- Discrete-time and continuous-time modelling: some bridges and gaps
- On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
- Diffusive Influence Systems
- A Uniform Substitution Calculus for Differential Dynamic Logic
- Hypercomputation
- Turing universality of the Biochemical Ground Form
- Three Paths to Effectiveness
- A Natural Axiomatization of Computability and Proof of Church's Thesis
- Strand Algebras for DNA Computing
- Storage Modification Machines
- Polynomial algorithms in linear programming
- A universal differential equation
- Dynamical Systems which Solve Optimization Problems with Linear Constraints
- Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
- Quantum theory, the Church–Turing principle and the universal quantum computer
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Undecidable event detection problems for ODEs of dimension one and two
- Evolutionary game dynamics
- Building Infinite Machines
- Unpredictability and undecidability in dynamical systems
- Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length (Journal version)
- Real Interactive Proofs for VPSPACE.
- Tight space-noise tradeoffs in computing the ergodic measure
- On Recurrent Reachability for Continuous Linear Dynamical Systems
- Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
- Tractional Motion Machines: Tangent-Managing Planar Mechanisms as Analog Computers and Educational Artifacts
- A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle
- Logical Foundations of Cyber-Physical Systems
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- A Step towards a Complexity Theory for Analog Systems
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- Logical Analysis of Hybrid Systems
- Computability of Operators on Continuous and Discrete Time Streams
- From finite automata toward hybrid systems (Extended abstract)
- A Universal Ordinary Differential Equation
- Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs
- Compactness in the Theory of Continuous Automata
- The Extent of Computation in Malament–Hogarth Spacetimes
- Hybrid Systems: Computation and Control
- Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
- Constructing Continuous Systems from Discrete Cellular Automata
- Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds
- Neurons with graded response have collective computational properties like those of two-state neurons.
- Timing in chemical reaction networks
- Programming in Biomolecular Computation
- The New Promise of Analog Computation
- Some Aspects of a Complexity Theory for Continuous Time Systems
- The Euclid Abstract Machine: Trisection of the Angle and the Halting Problem
- Complexity of Self‐Assembled Shapes
- Experimental computation of real numbers by Newtonian machines
- The Church-Turing Thesis over Arbitrary Domains
- Unconventional Computation
- La thèse de l’hyper-calcul : enjeux et problèmes philosophiques
- Les deux formes de la thèse de Church-Turing et l’épistémologie du calcul
- Computation in networks of passively mobile finite-state sensors
- The Convergence of Bird Flocking
- Computational complexity with experiments as oracles
- Logical Reversibility of Computation
- Machines, Computations, and Universality
- New Computational Paradigms
- New Computational Paradigms
- Sequential abstract-state machines capture sequential algorithms
- Mathematical Theory of the Differential Analyzer
- SOFSEM 2006: Theory and Practice of Computer Science
- Achilles and the tortoise climbing up the arithmetical hierarchy
- Iteration, inequalities, and differentiability in analog computers
- Non-Turing computations via Malament--Hogarth space-times
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic function computation with chemical reaction networks
- Study of dynamical systems from the viewpoint of complexity and computational capabilities
- On the decidability and complexity of problems for restricted hierarchical hybrid systems
- The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\)
- On Ladner's result for a class of real machines with restricted use of constants
- Low dimensional hybrid systems -- decidable, undecidable, don't know
- The expressive power of analog recurrent neural networks on infinite input streams
- Non-standard semantics of hybrid systems modelers
- A complex analogue of Toda's theorem
- Limits of computation. From a programming perspective
- Verification of population protocols
- Mediated population protocols
- Passively mobile communicating machines that use restricted space
- Probabilistic analysis of a differential equation for linear programming
- Chomskian hierarchies of families of sets of piecewise continuous functions
- Real recursive functions and their hierarchy
- Homonym population protocols
- Expressive power of first-order recurrent neural networks determined by their attractor dynamics
- A new polynomial-time algorithm for linear programming
- Computability of analog networks
- The elementary computable functions over the real numbers: applying two new techniques
- The halting probability Omega: irreducible complexity in pure mathematics
- The nature of the extended analog computer
- Computability on reals, infinite limits and differential equations
- A foundation for real recursive function theory
- Computation with finite stochastic chemical reaction networks
- Differential dynamic logic for hybrid systems
- The complexity of analog computation
- Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
- Linear programming and the Newton barrier flow
- Conservative logic
- Karmarkar's linear programming algorithm and Newton's method
- The chemical abstract machine
- What's decidable about hybrid automata?
- Achilles and the tortoise climbing up the hyper-arithmetical hierarchy
- Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
- A theory of timed automata
- Dynamical system where proving chaos is equivalent to proving Fermat's conjecture
- Analog computation via neural networks
- Computability with low-dimensional dynamical systems
- Recursion theory on the reals and continuous-time computation
- Trace-based methods for solving nonlinear global optimization and satisfiability problems
- Reachability analysis of dynamical systems having piecewise-constant derivatives
- Automata over continuous time
- Extending stochastic and quantum functions
- Analog computers and recursive functions over the reals.
- Hypercomputation with quantum adiabatic processes
- Natural computation and non-Turing models of computation
- Continuous-time computation with restricted integration capabilities
- Hypercomputation: Philosophical issues
- A theory of complexity for continuous time systems
- On the functions generated by the general purpose analog computer
- Construction of a universal ordinary differential equation \(C^{\infty}\) of order 3
- An optical model of computation
- The extended analog computer
- A guide to membrane computing.
- An analog characterization of the Grzegorczyk hierarchy
- Membrane computing. An introduction.
- On the computational power of neural nets
- Undecidable Hopf bifurcation with undecidable fixed point
- Optimization and dynamical systems
- The design of novel distributed protocols from differential equations
- The computational power of population protocols
- Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
- Hybrid systems. Computation and control. 1st international workshop, HSCC '98, Berkeley, CA, USA, April 13--15, 1998. Proceedings
- A mathematical model for adaptive transport network in path finding by true slime mold
- Emulating cellular automata in chemical reaction-diffusion networks
- An algorithmic approach to collective behavior
- Generalized finite automata over real and complex numbers
- Polynomial differential equations compute all real computable functions on computable compact intervals
- An algebraic proof of the real number PCP theorem
- Real-time computability of real numbers by chemical reaction networks
- Taylor approximation for hybrid systems
- Physical constraints on hypercomputation
- The P\(\neq\) NP conjecture in the context of real and complex analysis
- How much can analog and hybrid systems be proved (super-)Turing
- Relativistic computers and the Turing barrier
- Church's thesis meets the \(N\)-body problem
- Abstract interpretation and types for systems biology
- Continuity and computability of reachable sets
- Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions
- The physical Church thesis as an explanation of the Galileo thesis
- On the complexity of bounded time and precision reachability for piecewise affine systems
- Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
- Topological automata
- A Mathematical View of Interior-Point Methods in Convex Optimization
- Periodic Generalized Automata over the Reals
- Noise vs computational intractability in dynamics
- Robustness of Expressivity in Chemical Reaction Networks
- Strong Turing Degrees for Additive BSS RAM's
- Finite Automata over Structures
- Towards an Axiomatization of Simple Analog Algorithms
- Computing with Large Populations Using Interactions
- The Computational Power of Interactive Recurrent Neural Networks
- Probability 1 Computation with Chemical Reaction Networks
- The promise of analog computation
This page was built for publication: A Survey on Analog Models of Computation