Advertisement
Published in:
2015 | OriginalPaper | Chapter
Synchronizing Automata with Extremal Properties
Authors : Andrzej Kisielewicz, Marek Szykuła
Published in: Mathematical Foundations of Computer Science 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We present a few classes of synchronizing automata exhibiting certain extremal properties with regard to synchronization. The first is a series of automata with subsets whose shortest extending words are of length \(\varTheta (n^2)\), where n is the number of states of the automaton. This disproves a conjecture that every subset in a strongly connected synchronizing automaton is cn-extendable, for some constant c, and in particular, shows that the cubic upper bound on the length of the shortest reset words cannot be improved generally by means of the extension method. A detailed analysis shows that the automata in the series have subsets that require words as long as \(n^2/4+O(n)\) in order to be extended by at least one element.
We also discuss possible relaxations of the conjecture, and propose the image-extension conjecture, which would lead to a quadratic upper bound on the length of the shortest reset words. In this regard we present another class of automata, which turn out to be counterexamples to a key claim in a recent attempt to improve the Pin-Frankl bound for reset words.
Finally, we present two new series of slowly irreducibly synchronizing automata over a ternary alphabet, whose lengths of the shortest reset words are \(n^2-3n+3\) and \(n^2-3n+2\), respectively. These are the first examples of such series of automata for alphabets of size larger than two.