This book introduces recently developed ideas and techniques in semigroup theory to
provide a handy reference guide previously unavailable in a single volume. The opening …

Synchronizing Automata and theˇCerný Conjecture Page 1 Synchronizing Automata and
theˇCerný Conjecture Mikhail V. Volkov Department of Mathematics and Mechanics, Ural State …

Consider the finite set Xn={1, 2,…, n} ordered in the standard way. Let Tn denote the full
transformation semigroup on Xn, that is, the semigroup of all mappings α: Xn→ Xn under …

Slowly Synchronizing Automata and Digraphs Page 1 Slowly Synchronizing Automata and
Digraphs * Dmitry Ananichev, Vladimir Gusev, and Mikhail Volkov Department of Mathematics …

In this paper we give the details of our new algorithm for finding minimal reset words of finite
synchronizing automata. The problem is known to be computationally hard, so our algorithm …

The notion of a synchronizing sequence plays an important role in the model-based testing
of reactive systems, such as sequential circuits or communication protocols. The main …

In this paper we describe an approach to finding the shortest reset word of a finite
synchronizing automaton by using a SAT solver. We use this approach to perform an …

In this paper we present a new fast algorithm for finding minimal reset words for finite
synchronizing automata, which is a problem appearing in many practical applications. The …

Synchronizing automata with a letter of deficiency 2 Page 1 Theoretical Computer Science 376
(2007) 30–41 www.elsevier.com/locate/tcs Synchronizing automata with a letter of deficiency …

A synchronizing word of a deterministic automaton is a word in the alphabet of colors
(considered as letters) of its edges that maps the automaton to a single state. A coloring of …