Search

• < Previous
• 1
• Next >

---

Computational Complexity of Smooth Differential Equations

Akitoshi Kawamura ; Hiroyuki Ota ; Carsten Rösnick ; Martin Ziegler.

The computational complexity of the solutions $h$ to the ordinary differential equation $h(0)=0$, $h'(t) = g(t, h(t))$ under various assumptions on the function $g$ has been investigated. Kawamura showed in 2010 that the solution $h$ can be PSPACE-hard even if $g$ is assumed to be Lipschitz&nbsp;[&hellip;]

---

Real Analytic Machines and Degrees

Tobias Gärtner ; Martin Ziegler.

We study and compare in two degree-theoretic ways (iterated Halting oracles analogous to Kleene's arithmetical hierarchy and the Borel hierarchy of descriptive set theory) the capabilities and limitations of three models of analytic computation: BSS machines (aka real-RAM) and strongly/weakly&nbsp;[&hellip;]

---

Semantics, Specification Logic, and Hoare Logic of Exact Real Computation

Sewon Park ; Franz Brauße ; Pieter Collins ; SunYoung Kim ; Michal Konečný ; Gyesik Lee ; Norbert Müller ; Eike Neumann ; Norbert Preining ; Martin Ziegler.

We propose a simple imperative programming language, ERC, that features arbitrary real numbers as primitive data type, exactly. Equipped with a denotational semantics, ERC provides a formal programming language-theoretic foundation to the algorithmic processing of real numbers. In order to capture&nbsp;[&hellip;]

---