Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with decidability:
TR04-006 | 6th January 2004
Günter Hotz

A remark on nondecidabilities of the initial value problem of ODEs

We prove that it is not decidable on R-machines if for a fixed finite intervall [a,b) the solution of the initial value problems of systems of ordinary differetial equations have solutions over this interval. This result holds independly from assumptions about differentiability of the right sides of the ODEs. Futhermore ... more >>>

TR04-011 | 16th January 2004
Christian Glaßer

Counting with Counterfree Automata

We study the power of balanced regular leaf-languages.
First, we investigate (i) regular languages that are
polylog-time reducible to languages in dot-depth 1/2 and
(ii) regular languages that are polylog-time decidable.
For both classes we provide

- forbidden-pattern characterizations, and
- characterizations in terms of regular expressions.

Both ... more >>>

ISSN 1433-8092 | Imprint