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
than varieties.
|
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-21493-6_6 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
similar correspondence,different concept,typed monoids,non regular language,syntactic monoid,language recognition,finite monoids,algebraic structure,finer notion,algebraic description,eilenberg-like theorem | Discrete mathematics,Context-free language,Algebra,Closure (mathematics),Algebraic structure,Monoid,Syntactic monoid,Free monoid,Regular language,Trace theory,Mathematics | Journal |
Volume | Citations | PageRank |
18 | 3 | 0.45 |
References | Authors | |
13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christoph Behle | 1 | 23 | 4.14 |
Andreas Krebs | 2 | 27 | 5.83 |
Stephanie Reifferscheid | 3 | 17 | 2.27 |