Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Theory of Computation:
TR01-059 | 20th July 2001
Elvira Mayordomo

A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

We obtain the following full characterization of constructive dimension
in terms of algorithmic information content. For every sequence A,
cdim(A)=liminf_n (K(A[0..n-1])/n.

more >>>

TR01-081 | 8th August 2001
Palash Sarkar

Pushdown Automaton with the Ability to Flip its Stack

We introduce the idea of pushdown automata with the ability to flip
its stack. By bounding the number of times the stack can be flipped
we obtain a hierarchy of language classes from the context free
languages to the recursively enumerable languages. We show that each
class in ... more >>>

ISSN 1433-8092 | Imprint