Avtomatne grupe

delo diplomskega seminarja

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2021
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FGG - Faculty of Civil and Geodetic Engineering
Publisher:	[C. Lanzi Luciani]
UDC:	512
COBISS:	60858883
Views:	805
Downloads:	108
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Groups of automata
Secondary abstract:	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.
Secondary keywords:	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;
Type (COBISS):	Final seminar paper
Study programme:	0
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja, Program dvojne diplome iz matematike z Univerzo v Trstu
Pages:	36 str.
ID:	12750776