Knowledge base: Warsaw University of Technology

Settings and your account

Back

High-performance Computation of Synchronizing Words for Finite Automata

Michalina Nikonowicz, Kazimierz Wojciechowski

Abstract

The following thesis presents a high-performance distributed computing system in order to validate the Černý conjecture. Our computations confirm the validity of the conjecture for binary automata of up to 10 states. In order to verify the conjecture the system generates all nonisomorphic unary automata, preliminarily eliminates some of the generated automata, generates all possible binary automata out of the remaining unary automata and finally verifies the conjecture by checking the length of a shortest synchronizing word of every generated binary automaton that is synchronizable. The system summarizes all gathered data from computational nodes and displays the state of the computation in real-time, some of the automata with long synchronizing words and possibly automata that violate the conjecture. The system gives the ability to investigate found automata or their power graphs in an interactive 3D environment.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Michalina Nikonowicz (FMIS) Michalina Nikonowicz,, Faculty of Mathematics and Information Science (FMIS) Kazimierz Wojciechowski (FMIS) Kazimierz Wojciechowski,, Faculty of Mathematics and Information Science (FMIS)
Title in Polish
Wysoko wydajne obliczanie słów synchronizujących dla automatów skończonych
Supervisor
Michał Dębski (FMIS/DAC) Michał Dębski,, Department of Algebra and Combinatorics (FMIS/DAC)Faculty of Mathematics and Information Science (FMIS)
Certifying unit
Faculty of Mathematics and Information Science (FMIS)
Affiliation unit
Department of Algebra and Combinatorics (FMIS/DAC)
Study subject / specialization
, Informatyka (Computer Science)
Language
(pl) Polish
Status
Finished
Defense Date
31-01-2019
Issue date (year)
2019
Reviewers
Maciej Bartoszuk (FMIS/DAICM) Maciej Bartoszuk,, Department of Artificial Intelligence and Computational Methods (FMIS/DAICM)Faculty of Mathematics and Information Science (FMIS) Maciej Bartoszuk (FMIS/DAICM) Maciej Bartoszuk,, Department of Artificial Intelligence and Computational Methods (FMIS/DAICM)Faculty of Mathematics and Information Science (FMIS) Michał Dębski (FMIS/DAC) Michał Dębski,, Department of Algebra and Combinatorics (FMIS/DAC)Faculty of Mathematics and Information Science (FMIS) Michał Dębski (FMIS/DAC) Michał Dębski,, Department of Algebra and Combinatorics (FMIS/DAC)Faculty of Mathematics and Information Science (FMIS)
Keywords in Polish
Hipoteza Černýego, obliczenia naukowe, automat synchronizowalny, obliczenia rozproszone, .Net Core, Three.js, Material Design, SignalR
Keywords in English
Černý conjecture, scientific computing, synchronizable automaton, distributed com- puting, .Net Core, Three.js, Material Design, SignalR
Abstract in Polish
W niniejszej pracy dyplomowej zostaje przedstawiony wydajny rozproszony system obliczeniowy sprawdzający hipotezę Černýego. Obliczenia potwierdzają prawdziwość hipotezy dla automatów binarnych o liczbie stanów do 10 włącznie. W celu sprawdzenia hipotezy system generuje nieizomorficzne automaty unarne, wstępnie eliminuje wygenerowane automaty, a następnie generuje automaty binarne i sprawdza prawdziwość hipotezy badając długość słowa synchronizującego dla wygenerowanych automatów które są synchronizowalne. System podsumowuje zebrane wyniki z węzłów obliczeniowych oraz wyświetla stan obliczeń w czasie rzeczywistym, niektóre automaty o długim słowie synchronizującym oraz ewentualne kontrprzykłady do hipotezy. Ponadto, system umożliwia interaktywną wizualizację znalezionych automatów lub ich grafów potęgowych w środowisku trójwymiarowym.
File
  • File: 1
    PracaDyplomowaNikonowiczWojciechowski.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 29663

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT7b5f7b8c27bd41a58dd461fc5d190dfa/
URN
urn:pw-repo:WUT7b5f7b8c27bd41a58dd461fc5d190dfa

Confirmation
Are you sure?
Report incorrect data on this page