On the computational power of dynamical systems and hybrid systems

DOI10.1016/S0304-3975(96)00086-2zbMath0874.68303MaRDI QIDQ1349871

Olivier Bournez, Michel Cosnard

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Related Items (21)

Infinite traces and symbolic dynamics ⋮ Conservatively Approximable Functions ⋮ Complexity of reachability problems for finite discrete dynamical systems ⋮ The impact of models of a physical oracle on computational power ⋮ AN ANALOGUE-DIGITAL CHURCH-TURING THESIS ⋮ The promise of analog computation ⋮ Some bounds on the computational power of piecewise constant derivative systems (extended abstract) ⋮ Retracted: Universal computation is `almost surely' chaotic ⋮ Computations with oracles that measure vanishing quantities ⋮ A dynamical model of parallel computation on bi-infinite time-scale ⋮ A survey of computational complexity results in systems and control ⋮ Computability of countable subshifts in one dimension ⋮ Physical constraints on hypercomputation ⋮ THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY ⋮ Deciding stability and mortality of piecewise affine dynamical systems ⋮ The stability of saturated linear dynamical systems is undecidable ⋮ How much can analog and hybrid systems be proved (super-)Turing ⋮ Limits to measurement in experiments governed by algorithms ⋮ Achilles and the tortoise climbing up the hyper-arithmetical hierarchy ⋮ What is a universal computing machine? ⋮ Computational complexity with experiments as oracles

Cites Work

• Unnamed Item
• Unnamed Item
• The algorithmic analysis of hybrid systems
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• A weak version of the Blum, Shub, and Smale model
• A survey on real structural complexity theory
• From ATP to timed graphs and hybrid systems
• Analog computation via neural networks
• Computability with low-dimensional dynamical systems
• Computing over the reals with addition and order
• The simple dynamics of super Turing theories
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Nonlinear regulation: The piecewise linear approach
• Unpredictability and undecidability in dynamical systems
• On some relations between dynamical systems and transition systems
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Generalized shifts: unpredictability and undecidability in dynamical systems
• Logical Reversibility of Computation
• Achilles and the tortoise climbing up the arithmetical hierarchy

This page was built for publication: On the computational power of dynamical systems and hybrid systems