On Syntactic Structures.

Room FC1.029, DMat-FCUP
Tuesday, 16 June, 2015 - 13:30

The algebraic language theory contributes to the classification of regular languages and to the decision of memberships of a given language to various important classes of languages (star-free, piecewise testable, ...). The crucial notion is here the variety of languages (for each finite alphabet A one has a Boolean algebra $\mathcal{V}(A)$ of regular languages over $A$ which is closed with respect to quotients, and for each morphism $f:B^*\to A^*$ and $L\in \mathcal{V}(A)$ one has also $f^{-1}(L)\in\mathcal{V}(B)$.

We consider also varieties of finite deterministic automata and pseudovarieties of finite monoids. The links are via the minimal automaton of a language and via constructing the transformation monoid of an automaton.

There are numerous significant classes of languages which are not varieties. So we need to weaken the closure properties in the definition. There are numerous variants and one has to enrich automata and monoids with an additional algebraic structure to get the correspondence: languages $\leftrightarrow$ automata $\leftrightarrow$ monoids as above.

Speaker: 

Libor Polák (University Brno, Czech Republic)
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.