
Linear version of Holub's algorithm
Tvrdý, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
This work studies a linear agorithm which decides if a given word is a fixed point of any nontrivial morphism. This work also contains a description of auxiliary data structures which are crucial for linear time complexity of the algorithm. A Java implementation of the algorithm is provided along with a stepbystep visualization for particular input words. 1


Neural modelling of mathematical structures and their extensions
Smolík, Martin ; Urban, Josef (advisor) ; Holub, Štěpán (referee)
In this thesis we aim to build algebraic models in computer using machine learning methods and in particular neural networks. We start with a set of axioms that describe functions, constants and relations and use them to train neural networks approximating them. Every element is represented as a real vector, so that neural networks can operate on them. We also explore and compare different representations. The main focus in this thesis are groups. We train neural representations for cyclic (the simplest) and symmetric (the most complex) groups. Another part of this thesis are experiments with extending such trained models by introducing new "algebraic" elements, not unlike the classic extension of rational numbers Q[ √ 2]. 1


Pole Shifting Theorem in Control Theory
Gažo, Alexander ; Tůma, Jiří (advisor) ; Holub, Štěpán (referee)
Title: Pole Shifting Theorem in Control Theory Author: Alexander Gažo Department: Department of Algebra Supervisor: doc. RNDr. Jiří Tůma, DrSc., Department of Algebra Abstract: The poleshifting theorem is one of the basic results of the theory of linear dynamical systems with linear feedback. This thesis aims to compile all knowledge needed to fully understand the theorem in one place, in a way compre hensive to undergraduate students. To do this, I first define first order dynamical linear systems with constant coefficients with control and define the stability of such systems. Examining this property, I demonstrate that the characteristic polynomial of the coefficient matrix representing the system is a valuable indica tor of the system's behaviour. Then I show that the definition of controllability motivated by discretetime systems also holds for continuoustime systems. Using these notions, the poleshifting theorem is then proved. Keywords: discrete linear dynamical system with constant coefficients, contin uous linear dynamical system with constant coefficients, eigenvalue assignment, control, controllability, linear feedback, stability, basic control theory 1


Neural modelling of mathematical structures and their extensions
Smolík, Martin ; Urban, Josef (advisor) ; Holub, Štěpán (referee)
In this thesis we aim to build algebraic models in computer using machine learning methods and in particular neural networks. We start with a set of axioms that describe functions, constants and relations and use them to train neural networks approximating them. Every element is represented as a real vector, so that neural networks can operate on them. We also explore and compare different representations. The main focus in this thesis are groups. We train neural representations for cyclic (the simplest) and symmetric (the most complex) groups. Another part of this thesis are experiments with extending such trained models by introducing new "algebraic" elements, not unlike the classic extension of rational numbers Q[ √ 2]. 1


Universal Turing machine
Bahýľ, Viktor ; Krajíček, Jan (advisor) ; Holub, Štěpán (referee)
Title: Universal Turing machine Author: Viktor Bahýľ Department: Department of Algebra Supervisor: RNDr. Jan Krajíček, DrSc., Department of Algebra Abstract: This thesis is focused on the processes of solving computational problems. The Turing machine is an example of a model which we can use to solve these problems and these machines are the main objective of this Bachelor thesis. The generality of the model is important; it allows us to simulate any conceivable algorithm. In the theory of Turing machines, the generality is demonstrated by the construction of a universal Turing machine. This is the task of this Thesis: to define a universal Turing machine and to prove its universality. Key definitions, linked with the Turing machines, are recalled at the beginning of the Thesis. The simulation and representation of Turing machines will prove to be the key concepts. We make an extra effort to explain these fundamental notions. The thesis has its own form of representation and defined Turing machine with detailed descriptions for them, together with complete proof of the universality of the mentioned Turing machine. Keywords: Turing, machine, universality, representation


Squares in integer sequences
Hudcová, Barbora ; Holub, Štěpán (advisor) ; Bulín, Jakub (referee)
This work is based on an article which provides a construction of the first infinite word over a finite alphabet avoiding additive cubes. We construct other words with the same properties and we choose one of them to show the main idea of the proof that this word avoids additive cubes. 1


Star height
Svoboda, Tomáš ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
We present a certain family of languages and show that for those languages infinite hierarchy of star heights exists. The proof was first devised by Dejean and Schützenberger. More recently it was reformulated by Sakarovitch, who left some of the parts of the proof the the reader for more careful consideration. This thesis expands on those parts and provides more detailed proofs. We mainly focus on construction of rational expression with the star height of the given language. We also compare the star height and generalised star height and the difference in achieved results for those two similar concepts.


Proving by finite automata
Fišer, Jan ; Holub, Štěpán (advisor) ; Chvalovský, Karel (referee)
In 2016, Hamoon Mousavi published Walnut which is a program that implements automated theorem proving of propositions about automatic sequences. The main purpose of this thesis was to show the theoretical functi onality of Walnut on the basis of the relation between automatic sequences and Presburger (resp. B¨uchi) arithmetic that is a decidable theory. Another goal was to describe adequately how the decision procedure of Walnut really works, and finally, to show the practical use of Walnut on several particular problems. One of these particular problems that are solved in the thesis is computation of the critical exponent of the RudinShapiro sequence  this exercise was presented as an open problem in a book of 2003 (however, this exercise does not belong among open problems any more since Shallit proved in 2011 that the critical exponent is computable for all automatic sequences.) The last chapter itself can be also used as a brief manual for newcomers to Walnut that want to use this program for their own applications. 1


Solving systems of polynomial equations
Kubej, Lukáš ; Šťovíček, Jan (advisor) ; Holub, Štěpán (referee)
This work is about theory of systems of polynomial equations. Its main purpose is to prove the Elimination theorem and the Extension theorem, where the Elimination theorem helps us to solve a given systems of polynomial equations and the Extension theorem tells us, which partial solutions can be extended into a complete solutions. To formulate and prove those theorems, we will explain theory including monomial orders, division algorithm for polynomial and mainly the key concept of Groebner basis. At the end are solved examples showing application of explained theory.


Semilinear sets
Bouška, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
In this thesis we examine a part of the mathematical side of the theory of context free languages, namely semilinear sets. We prove that the semilinear sets are closed under set intersection and difference in a mathematically better digestible and possibly easier way than how it is presented as a noncentral result in the referenced literature. Then we introduce the notion of a contextfree language and present a result that relates semilinear sets and contextfree languages without a proof. 1
