logo-polimi
Loading...
Manifesto
Cerca/Visualizza Manifesto
Dati Insegnamento
Stampe
Manifesto

Dettaglio Insegnamento

Contesto
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

Scheda Insegnamento
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 Nielsen-Schreier 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) --

Dettaglio
Scaglione Docente Programma dettagliato
Da (compreso) A (escluso)
A ZZZZ Rodaro Emanuele
manifestidott v. 1.7.0 / 1.7.0
Area Servizi ICT
12/08/2022