Krohn-Rhodesova teorija

master's thesis

• Title (english): Krohn-Rhodes theory
• Author: Ivan Miošić
• Mentor: Marko Horvat (mentor)
• Committee member: Marko Horvat (predsjednik povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Igor Ciganović (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-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: računarska teorija konačnih automata; algebarska teorija konačnih polugrupa; homomorfizam; Krohn-Rhodesov dekompozicijski teorem
• Keywords (english): computational theory of finite automata; algebraic theory of finite semigroups; homomorphism; Krohn-Rhodes decomposition theorem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:530449
• Study programme: Title: 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 resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-02-23 10:58:46