All reports by Author Stephanie Reifferscheid:

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