All reports by Author Christoph Behle:

__
TR11-173
| 22nd December 2011
__

Christoph Behle, Andreas Krebs#### Regular Languages in MAJ[<] with three variables

__
TR11-095
| 22nd June 2011
__

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

Revisions: 1

__
TR11-035
| 4th March 2011
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

__
TR09-085
| 14th September 2009
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### An Approach to characterize the Regular Languages in TC0 with Linear Wires

Revisions: 1

Christoph Behle, Andreas Krebs

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.

It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq ... 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 >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.

This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.

more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>