Krohn-Rhodesova teorija

diplomski rad

• Naslov (engleski): Krohn-Rhodes theory
• Autor: Ivan Miošić
• Mentor: Marko Horvat (mentor)
• Član povjerenstva: Marko Horvat (predsjednik povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Član povjerenstva: Igor Ciganović (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-12-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Krohn-Rhodesova teorija spaja računarsku teoriju konačnih automata i algebarsku teoriju konačnih polugrupa. U ovom radu dajemo pregled temeljnih ideja i koncepata ove dualne teorije. Pokazujemo kako je svakom konačnom automatu prirodno pridružena konačna polugrupa. Izučavamo pojmove homomorfizma i simulacije između konačnih automata, odnosno transformacijskih polugrupa. Predstavljamo metode za dobivanje novih automata ili polugrupa kombinacijom polaznih. Na koncu iskazujemo i djelomično dokazujemo temeljni Krohn-Rhodesov dekompozicijski teorem. Njime je utvrđeno postojanje rastava proizvoljnog konačnog automata, odnosno transformacijske polugrupe, u jednostavnije sastavne dijelove.

Sažetak (engleski)

Krohn-Rhodes theory combines the computational theory of finite automata with the algebraic theory of finite semigroups. Here, an overview of the basic ideas and concepts from this dual theory is provided. It is shown that for each finite automaton there is a naturally associated finite semigroup. The concepts of homomorphism and simulation between finite automata and transformation semigroups, respectively, are studied. Several methods for obtaining new automata or semigroups by a combination of starting ones are presented. Finally, the fundamental Krohn-Rhodes decomposition theorem is stated, and proved to an extent. This theorem establishes the existence of a decomposition of an arbitrary finite automaton (and of any transformation semigroup as well) into simpler components.

• Ključne riječi: računarska teorija konačnih automata; algebarska teorija konačnih polugrupa; homomorfizam; Krohn-Rhodesov dekompozicijski teorem
• Ključne riječi (engleski): computational theory of finite automata; algebraic theory of finite semigroups; homomorphism; Krohn-Rhodes decomposition theorem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:530449
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-02-23 10:58:46