20.500.12556/RUL-161528 Uporaba grup v sinhronizaciji delo diplomskega seminarja Use of groups in synchronization Končni avtomat sinhronizira, če obstaja beseda, ki slika poljubno začetno stanje v fiksno končno stanje. V diplomskem delu definiramo hierarhijo lastnosti permutacijskih grup, povezanih s sinhronizacijo, in obravnavamo povezave med njimi. S pomočjo O’Nan-Scottove klasifikacije primitivnih grup pokažemo, da so vse sinhronizabilne grupe, ki niso skoraj enostavne, tudi ločevalne. Poleg tega podamo mejo za dolžino najkrajše ponastavitvene besede za avtomate, katerih obrnljivi prehodi tvorijo razširjajočo grupo, in mejo uporabimo za dokaz Pinovega izreka o dolžini najkrajše ponastavitvene besede avtomata s praštevilsko mnogo stanji ter cikličnim prehodom. A finite automaton is synchronizing if it permits a reset word, i.e. if there exists a sequence of transitions which maps any state to a predetermined fixed state. In this work we define a hierarchy of permutation group properties related to synchronization, and consider the links between them. Referencing the O’Nan-Scott classification of primitive groups, we prove that all synchronizing groups, which are not almost simple, are also separating. Additionally, we establish an upper bound for the length of the shortest reset word in an automaton whose invertible transitions form a spreading group, and use this bound to prove Pin’s theorem concerning the reset words of automata with a prime number of states and a cyclic transition. Černýjeva domneva ponastavitvena beseda permutacijska grupa primitivna grupa O’Nan-Scottov izrek sinhronizabilna grupa ločevalna grupa razširjajoča grupa Černý conjecture reset word permutation group primitive group O’Nan-Scott theorem synchronizing group separating group spreading group true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-09-12 08:15:16 2024-09-12 08:15:24 2024-09-17 10:34:27 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 512 143010 207802371 12776.pdf 12776.pdf 1 F4EFD20E66C5CD57C789D5C0594C13B7 82d36ece8f91bf2feef0e14f4e22cab29f7c364872414386424d16d1f94540c7 580afddf-70ce-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190481 Fakulteta za matematiko in fiziko 0 0 0