Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Christoph Behle:

TR11-173 | 22nd December 2011
Christoph Behle, Andreas Krebs

Regular Languages in MAJ[<] with three variables

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 >>>

TR11-095 | 22nd June 2011
Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

Low uniform versions of NC1

Revisions: 1

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 >>>

TR11-035 | 4th March 2011
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint