Avtomatne grupe : delo diplomskega seminarja

Lanzi Luciani, Carlo (avtor), Kudryavtseva, Ganna (mentor), Logar, Alessandro (komentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: avtomat, končni avtomat, besedni prostor, Moorov diagram, semidirektni produkt, venčni produkt, rekurzivnost, grupa svetilničarja, neskončna diedrska grupa, stroj dodajanja, delovanje grup na drevesih
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2021
• PID: 20.500.12556/RUL-125902
• UDK: 512
• COBISS.SI-ID: 60858883
• Datum objave v RUL: 09.04.2021

LANZI LUCIANI, Carlo, 2021, Avtomatne grupe : delo diplomskega seminarja [na spletu]. Diplomsko delo. [Dostopano 6 maj 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=125902

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Groups of automata

Izvleček

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.

• Ključne besede: 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