
Dettaglio Insegnamento
Anno Accademico 
2021/2022 
Corso di Studi 
Dott.  MI (1385) Modelli e Metodi Matematici per l'Ingegneria / Mathematical Models and Methods in Engineering 
Anno di Corso 
1 
Codice Identificativo 
057416 
Denominazione Insegnamento 
(SEMI)GROUP THEORY AND AUTOMATA 
Tipo Insegnamento 
MONODISCIPLINARE 
Crediti Formativi Universitari (CFU) 
5.0 
Programma sintetico 
The aim of the course is twofold: the first is to show how algebraic methods are used in characterizing certain automata and languages in the Chomsky hierarchy, the second one is to show how to use typical tools in automata theory to face certain algebraic problems in group and semigroup theory. The timetable of the two parts will depend on the background and interests of the students attending the course. Roughly the course will be structured as follows:
1) Basic concepts: foundamentals of semigroups, groups. Cayley graphs, free groups and presentation of groups, Dehn's algorithmic problems is groups and semigroups. (4 hours).
2) Finite automata, regular languages, syntactic monoid of a language, rational and recognizable languages, Schutzenberger's theorem on star free languages. The "passepartout" of several undecidability results: the Post correspondence problem and the equalizer of two morphisms. (6 hours)
3) A glimpse of automata methods in group and semigroup theory: Stallings's construction, the NielsenSchreier theorem. An outline to the word problem for free inverse semigroups and groups. (4 hours)
4) Automata groups: the Burnside problem and the Grigorchuck's group (6 hours)
5) Growth of groups and the Grigorchuck's group, and some mentions to amenability of groups, paradoxical decompositions, random walks on groups (5 hours) 
Settori Scientifico Disciplinari (SSD) 


Scaglione

Docente

Programma dettagliato

Da (compreso)

A (escluso)

A

ZZZZ

Rodaro Emanuele


