Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-035 | 4th March 2011 13:49

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

RSS-Feed

Abstract:

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.
We prove an Eilenberg-like theorem for varieties of typed monoids as well as a similar correspondence for classes of languages with weaker closure properties.



ISSN 1433-8092 | Imprint