期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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
关键词：algebraic characterization, descriptive complexity, formal languages
