logo-polimi
Loading...
Degree programme
Show/Search Programme
Course Details
Print
Save Document

Dettaglio Insegnamento

Context
Academic Year 2021/2022
Name Dott. - MI (1385) Modelli e Metodi Matematici per l'Ingegneria / Mathematical Models and Methods in Engineering
Programme Year 1

Course Details
ID Code 057416
Course Title (SEMI)GROUP THEORY AND AUTOMATA
Course Type MONODISCIPLINARE
Credits (CFU / ECTS) 5.0
Course Description 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)
Scientific-Disciplinary Sector (SSD) --

Details
Alphabetical group Professor Course details
From (included) To (excluded)
A ZZZZ Rodaro Emanuele
manifestidott v. 1.7.0 / 1.7.0
Area Servizi ICT
23/05/2022