Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with algebraic characterization:
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 >>>

ISSN 1433-8092 | Imprint