All reports by Author Klaus-Joern Lange:

__
TR14-177
| 14th December 2014
__

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig#### Visibly Counter Languages and Constant Depth Circuits

__
TR11-095
| 22nd June 2011
__

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie#### Low uniform versions of NC1

Revisions: 1

__
TR10-070
| 17th April 2010
__

Eric Allender, Klaus-Joern Lange#### Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

__
TR96-048
| 12th September 1996
__

Eric Allender, Klaus-Joern Lange#### StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

more >>>Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

In the setting known as DLOGTIME-uniformity,

the fundamental complexity classes

$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several

robust characterizations.

In this paper we refine uniformity further and examine the impact

of these refinements on $NC^1$ and its subclasses.

When applied to the logarithmic circuit depth characterization of $NC^1$,

some refinements leave ...
more >>>

Eric Allender, Klaus-Joern Lange

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

Eric Allender, Klaus-Joern Lange

We present a deterministic algorithm running in space

O((log^2 n)/loglog n) solving the connectivity problem

on strongly unambiguous graphs. In addition, we present

an O(log n) time-bounded algorithm for this problem

running on a parallel pointer machine.