8 citations · 29 across the 23 of their papers we have counts for
5 papers · 1 filter
Synchronizing Automata with Extremal Properties
Andrzej Kisielewicz, Marek Szykuła
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 short…
Experiments with Synchronizing Automata
Andrzej Kisielewicz, Jakub Kowalski, Marek Szykuła
We have improved an algorithm generating synchronizing automata with a large length of the shortest reset words. This has been done by refining some known results concerning bounds…
Generating Synchronizing Automata with Large Reset Lengths
Andrzej Kisielewicz, Marek Szykuła
We study synchronizing automata with the shortest reset words of relatively large length. First, we refine the Frankl-Pin result on the length of the shortest words of rank , an…
The Cerny conjecture for automata respecting intervals of a directed graph
M. Grech, A. Kisielewicz
The Černý's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n-11)^2. We prove this conjecture for a class…
A Fast Algorithm Finding the Shortest Reset Words
Andrzej Kisielewicz, Jakub Kowalski, Marek Szykuła
In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is ex…