Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYLOG-TIME REDUCTIONS:
Reports tagged with polylog-time reductions:
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