Avtomatne grupe

delo diplomskega seminarja

Carlo Lanzi Luciani (Avtor), Ganna Kudryavtseva (Mentor), Alessandro Logar (Mentor)

Povzetek

V diplomskem delu predstavljamo nekaj zanimivih primerov z avtomati generiranih grup. V prvem delu predstavimo input in output avtomatona z simboli abecede X. Množico končnih zaporedij teh simolov, imenovano končni slovar, razumemo kot monoid ali kot množico vozlišč drevesa. Nato preidemo na definicijo Mealyjevega končnega determinističnega avtomata A in jo grafično prikažemo z Moorovimi diagrami. Nato definiramo koncept začetnega avtomata in njegovega delovanja. V drugem delu opišemo delovanje avtomatov abstraktno prek koncepta sinhrone avtomatne transformacije f. Se osredotočimo le na obrnljive avtomate. Preučimo še vpliv obrnljivnosti avtomata na dostopnost njegovih stanj in podamo definicijo z avtomatom generirane grupe. Tretji del opisuje vrsto algebraičnih orodij potrebnih pri analizi z avtomatom generiranih grup. Pričnemo z definicijo levega in desnega delovanja grupe G na množico X in na grupo N, semidirektnega produkta in nazadnje venčnega produkta. V naslednjem razdelku opisujemo povezavo teh struktur z avtomi. V četrtem in zadnjem delu predstavimo klasifikacijo grupe generirane z avtomati z dvema stanjema nad abecedo dveh črk. Preden izrek navedemo predstavimo grupe, ki se pojavijo v rezultatu, začenjši z neskončno diedersko grupo, torej grupe simetrij Z. Sledi grupa svetilničarja (lamplighter group), in definicija posebne sinhrone avtomatske transformacije, imenovane seštevalni stroj. Nazadnje predstavimo del dokaza klasifikacijskega izreka, kjer si pomagamo z analizo primerov.

Ključne besede

mathematics;automaton;finite automaton;word space;Moore diagram;wreath product;semidirect product;recursion;infinite lamplighter group;infinite dihedral group;adding machine;groups acting on rooted trees;

Podatki

Jezik:	Angleški jezik
Leto izida:	2021
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FGG - Fakulteta za gradbeništvo in geodezijo
Založnik:	[C. Lanzi Luciani]
UDK:	512
COBISS:	60858883
Št. ogledov:	805
Št. prenosov:	108
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Groups of automata
Sekundarni povzetek:	In this bachelor thesis we present some interesting examples and results on groups generated by Mealy automata. In the first section we introduce the input and output of an automaton as sequences of symbols from an alphabet X, and we discuss their properties. In particular, we present the set X^* of finite sequences as the set of vertices of a rooted tree. Then we go on to the formal definition of a finite deterministic Mealy automaton (we will simply call it an automaton) A, and we provide some examples of automata given by Moore diagrams (graph representations of automata). We define the concept of an initial automaton and its action. In the second section we give an abstract characterization of actions of automata: the notion of a synchronous automatic transformation f. We pay a special attention to invertible automata. Then we provide the definition of a group generated by an automaton. In the third section we describe some algebraic structures that arise in connection to groups of automata. We first revise the notions of left and right actions of a group on a set and on a group, the semidirect product construction and finally the wreath product construction. We then study the relationship of these notions with automata. In the fourth section we present the classification of groups generated by 2-state automata over a 2-letter-alphabet. Before formulating the result we introduce two important groups that arise in this theorem, i.e., the infinite dihedral group and the lamplighter group. The latter group can be realized as a wreath product of the infinite cyclic group Z and the two-element group Z/2Z. Then we define a synchronous automatic transformation called the adding machine. Finally we present a detailed account of a part of the proof of the classification theorem. It is based on careful case consideration.
Sekundarne ključne besede:	matematika;avtomati;končni avtomati;besedni prostor;Moorov diagram;semidirektni produkt;venčni produkt;rekurzivnost;grupa svetilničarja;neskončna diedrska grupa;stroj dodajanja;delovanja grup na drevesih;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja, Program dvojne diplome iz matematike z Univerzo v Trstu
Strani:	36 str.
ID:	12750776