Subset properties and synchronization of finite state automata
(2019)
Files
ThesisFrançoisGonzeFinal.pdf
Open Access - Adobe PDF
- 1.22 MB
Details
- Authors
- Supervisors
- Jungers, Raphaël
- Abstract
- Finite state systems, also called automata, are key tools for modelling physical systems, for emulating computers and for text processing. These systems are composed of a set of possible states and a set of letters. The letters represent the commands which can be applied to the system, and their effect depends on the current state. The control of such systems raises many theoretical questions about reachability and synchronization of subsets of states, one of them being well known as the Černý conjecture. This conjecture, which has been open for 55 years, states that a synchronizing automaton has a quadratic reset threshold. In this thesis, we study open problems related to subsets of states while targeting the Černý conjecture. Our results are twofold. On the one hand we disprove several conjectures that, if true, would have led to proving the Černý conjecture. More precisely, we first disprove a conjecture on the synchronizing probability function. Second, we provide a counterexample to a tentative improvement of the best general bound on the reset threshold, based on subset avoidance. Finally, we disprove a conjecture on subset reachability. On the other hand, we prove positive results toward the Černý conjecture. We first prove an upper bound on the triple rendezvous time, the length of the shortest word synchronizing three states of an automaton. Secondly, we prove upper and lower bounds for 2-Transitivity of permutation sets. Thirdly, we provide an algorithmic characterization of completely reachable automata. Finally we prove that automata generating the whole transformation semigroup, which is the widest possible transformation set, have quadratic reset threshold.
- Affiliations
Citations
Gonze, F. (2019). Subset properties and synchronization of finite state automata. https://hdl.handle.net/2078.5/169526