prikaz prve stranice dokumenta Krohn-Rhodesova teorija
  Download
PDF 479.9 KB
master's thesis
Krohn-Rhodesova teorija
Zagreb: University of Zagreb, Faculty of Science, 2020. urn:nbn:hr:217:530449
Miošić, Ivan
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Miošić, I. (2020). Krohn-Rhodesova teorija (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:530449

Miošić, Ivan. "Krohn-Rhodesova teorija." Master's thesis, University of Zagreb, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:217:530449

Miošić, Ivan. "Krohn-Rhodesova teorija." Master's thesis, University of Zagreb, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:217:530449

Miošić, I. (2020). 'Krohn-Rhodesova teorija', Master's thesis, University of Zagreb, Faculty of Science, accessed 23 December 2024, https://urn.nsk.hr/urn:nbn:hr:217:530449

Miošić I. Krohn-Rhodesova teorija [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2020 [cited 2024 December 23] Available at: https://urn.nsk.hr/urn:nbn:hr:217:530449

I. Miošić, "Krohn-Rhodesova teorija", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:217:530449

Metadata
TitleKrohn-Rhodesova teorija
Title (english)Krohn-Rhodes theory
AuthorIvan Miošić
MentorMarko Horvat (mentor)
Committee memberMarko Horvat (predsjednik povjerenstva)
Committee memberVedran Čačić (član povjerenstva)
Committee memberIgor Ciganović (član povjerenstva)
Committee memberMiljenko Marušić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2020-12-01, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:530449
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2021-02-23 10:58:46