BIBLIOGRAPHY,  synchronization @  TESTAS

  Download the freeware version for WINDOWS:
TESTAS (zip file, about 200 KB)


The package analyzes an automaton of the language presented as oriented labeled graph, for properties, possibilities and input data see section TESTAS   



      Bibliography  (Cerny conjecture, road coloring, synchronizing word)


R. L. Adler, L., B. Weiss,

Similarity of the automorphisms of the torus,

Memories of AMS, Providens, RI, N98, 1970. 


R. L. Adler, L., W. Goodwyn, B. Weiss,

Equivalence of topological Markov shifts,

 Israel Journal of Mathematics 27 (1977), 49-63


 Almeida, J., Margolis, S., Steinberg, B., Volkov, M.V.:

Representation theory of finite semigroups, semigroup radicals and formal language theory.

Trans. Amer. Math. Soc. (to appear, 2008),

  J Almeida, B Steinberg

Matrix Mortality and the Cerny-Pin Conjecture
   DLT 2009,  LNCS 5583( 2009),  Springer Monographs in Math. Springer,  67-80


J. Almeida,  A. Cardoso

A Sequence of Weakly Monotonic Automata with Increasing Level

Int. J. Algebra, 7 ( 2),  91 – 100,  2013

R Alseidi, J Garloff. Recognition of Matrices Which are Sign-regular of a Given Order and a Generalization of Oscillatory Matrices - 2020 -

L. V. Alves, P. N. Pena. Reconfiguration of Discrete Event Systems using Synchronizing Words. Conf. Workshop on Discr. Ev. Syst. 2020.Rio de Janeiro, Brazil


 Ananichev, D. S. / Volkov, M. V. / Gusev, V. V.,

Primitive digraphs with large exponents and slowly synchronizing automata

Journal of Math. Sci., 192 (3), .263-278, 2013



Dmitry Ananichev, Vladimir Gusev, Mikhail Volkov

Slowly Synchronizing Automata and Digraphs

LNCS 6281(010), MFCS 2010, 55-65


Dmitry S. Ananichev, Vladimir V. Gusev, Mikhail V. Volkov

Примитивные орграфы с большими экспонентами и медленно синхроизируемые автоматы

(Primitive  digraphs with large exponents and slowly synchronizing automata)

Zapiski Nauchnyh Seminarov POMI [Komb.  Teorija Grafov. IV], 402, 9-39 (2012).


 D. S. Ananichev

The mortality threshold for partially monotonic automata.

LNCS 3572: 112-121 2005


D.S. Ananichev 

Порог аннуляции для частично монотонных автоматов ata
(The threshold of avoidance of partially monotonic autom)


D. S. Ananichev, A. Cherubini, M. V. Volkov,

An inverse automata algorithm for recognizing 2-collapsing words,

 DLT (6th Int.Conf., Kyoto, 2002), LNCS 2450 (2003), 270-282

D. S. Ananichev, A. Cherubini, M. V. Volkov,

Image reducing words and subgroups of free groups,

Theoretical Computer Science 307 (2003), 77-92

D. S. Ananichev, I. V. Petrov,

Quest for short synchronizing words and short collapsing words,

 WORDS'03 (4th Int. Conf. on Comb. on Words, Turku, 2003),

Turku Centre of Comput.Sci. General Publication 27 (2003), 411-418

D. S. Ananichev, I. v. Petrov M.V. Volkov,

Collapsing words: A progress report

Int. J. of Found. of Comput. Sci. 17, 3(2006), 507-518, LNCS, 3572: 11-21 2005

D. S. Ananichev, M. V. Volkov, 

 Synchronizing Generalized Monotonic Automata.

 Workshop on Synchronizing Automata. Turku (Finland), 2004

D. S. Ananichev, M. V. Volkov, Yu. I. Zaks,

Synchronizing automata with a letter of deficiency 2,

LNCS, 4036(2006), 433-442

 D.S, Ananichev, M.V. Volkov, Y. I. Zaks  

Synchronizing automata with a letter of deficiency 2,
THEORET. COMPUT. SCI.   V.: 376   I: 1-2    30-41,   2007

D. S. Ananichev, M. V. Volkov,

Collapsing words vs. synchronizing words,

DLT (5th Int.l Conf. Vienna, 2001), LNCS, 2295 (2002), 166-174

D. S. Ananichev, M. V. Volkov,

Synchronizing monotonic automata,

DLT  (7th Int.Conf., Szeged, 2003), LNCS 2710 (2003), 111-121

D. S. Ananichev, M. V. Volkov,

Synchronizing monotonic automata,

Theoretical Computer Science, accepted (ps-file)

D. S. Ananichev, M. V. Volkov,

Some results on Cerny type problems for transformation semigroups,

Semigr.and Lang. (Int. Workshop, Lisbon, 2002), World Scientific, Singapore, 2004, 23-42

D. S. Ananichev, M. V. Volkov

Synchronizing generalized monotonic automata


DS Ananichev,
 VV Gusev Approximation of Reset Thresholds with Greedy Algorithms

 - Fundamenta Informaticae, vol. 145, no. 3, 221-227, 2016, 2016


D D'Angeli, E Rodaro

Groups and semigroups defined by colorings of synchronizing automata

 Int.J. of Algebra and Comp., World Scientific, 2014 - 2014, 9-39


F. Arnold, B. Steinberg.

Synchronizing groups and automata 

Theoret. Comput. Sci. V. 359, 1, 2006, 101-110


Araújo, João / Bentz, Wolfram / Cameron, Peter J1.

 Groups synchronizing a transformation of non-uniform kernel

TCS, V. 498, 1-9, 2013


J Araújo, W Bentz, PJ Cameron… Primitive groups, graph endomorphisms and synchronization

- Proc London Math Soc (2016) 113 (6): 829-867., 2016 -


MP Beal, D Perrin –

A quadratic algorithm for road coloring
arXiv:0803.0726v2 [cs.DS] 5 Mar 2008


MP Beal, E Czeizler, J Kari, D Perrin

Unambiguous automata-

Mathematics in Computer Science, 2008

MP Beal, J Berstel, B Marcus, D Perrin, C.,

Variable Length Codes and Finite Automata 2007  World Sci. 2008 


MP Beal, D Perrin
A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
Germany, DLT, Springer Monographs in Mathematics. Springer, 81-90, LNCS 5583( 2009)

Beal MP, Berlinkov MV, Perrin D



Int. J Found. Comput. Sci. 22(2), 277-288, 2011


NC Behague, JR Johnson Synchronizing Times for -sets in Automata,–arXiv preprint arXiv:2008.12166, 2020 -

Arthur Benjamin, Gary Chartrand & Ping Zhang

The Fascinating World of Graph Theory

Popular Math.,, 360, 2015


Mikhail V. Berlinkov

On the Probability of Being Synchronizable

Alg. Discr App. Math. V. 9602(2016) LNCS. 73-84

Berlinkov M.
Approximating the Minimum Length of Synchronizing Words Is Hard
LNCS 6072/2010, 37-47


M. Berlinkov

On a Conjecture by Carpi and D'Alessandro.

 Developments in Language Theory, Springer, NY,  LNCS 6224, 2010,  66-75


Mikhail V. Berlinkov

Synchronizing Automata on Quasi-Eulerian Digraph

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 90-100


М. В. Берлинков

О погрешности полиномиального вычисления оптимальной

раскраски графа в синхронизируемый автомат

Прикладная дискретная математика

2011, № 2, 49–72


Mikhail V. Berlinkov

Approximating the Minimum Length of Synchronizing Words Is Hard

Theor. Comput. Syst. 2(54), 211-223, 2014


MV Berlinkov, M Szykuła  Algebraic synchronization criterion and computing reset words.- Information Sciences, 2016 – Elsevier Volume 369,  2016, 718-730


MV Berlinkov On the probability of being synchronizable

- Conference on Algorithms and Discrete Applied, 73-84, 2016 - Springer


MV Berlinkov, R Ferens, M Szykuła Preimage problems for deterministic finite automata. Journal of Computer and System Sciences - Elsevier


Codes and Automata,

Cambridge University Press, 2010, 620


Jean Berstel, Clelia De Felice, Dominique Perrin, Christophe Reutenauer,

 Giuseppina Rindone.

Recent results on syntactic groups of prefix codes

Europ. J. Comb. 33(7), 1386-1401, 2012


V Berthé, M Rigo

Combinatorics, Words and Symbolic Dynamics

Encyclopedia Math. & Appl. 159. Cambridge University Press. 2016 .


Marek Tomasz Biskup

Shortest Synchronizing Strings for Huffman Codes.
LNCS. 120--131, MFCS 2008, 5162(2008)


Biskup, M.T. Plandowski, W. ,
Shortest synchronizing strings for Huffman codes
Theoretical Comput. Sci., 410 (38), 3925-3941, 2009

Synchronizing Words and Monoid Factorization: A Parameterized Perspective. J Bruchertseifer, H Fernau - … Conference on Theory and Appl. of …, 2020 - Springer

S. Bogdanovic, B. Imreh,

: Directable automata and their generalizations

A survey, Novi Sad Journal of Mathematics 29 (1999), No.2, 29-69

M De Bondt, H Don, H Zantema. Lower bounds for synchronizing word lengths in partial automata.- International Journal of …, 2019 - World Scientific

P. Borovansky, M. Wincer,

Speed of direction of finite automata,

2nd Czechoslovak-Soviet Conf. of Young Computer Scientists, Bratislava, 1982, 53-59


EA Bondar, MV Volkov,

Completely Reachable Automata

Workshop on Descriptional Complexity of Formal Lang., 2016, DCFS.  LNCS, vol 9777,. 2016- Springer


Boyle M.

Open Problems in Symbolic Dynamics
Geom. & prob. struct. In dynamics: CONT. MATH. SER. v. 469, 69-118, 2008


J Bruchertseifer, H Fernau 

Synchronizing Words and Monoid Factorization: A Parameterized Perspective.

Int. Conf. on Theory and Applications, TAMC 2020, 352-364


G. Budzban and Ph. Feinsilver

The generalized road coloring problem and periodic digraphs

Applicable Alg. in Eng., Communication and Computing, V 22, N 1,  2011, 21-35

 Budzban G., Feinsilver P.
An approach to road coloring problem based on vector spaces.

G. Budzban,  Semigroups and the Generalized Road Coloring Problem.

Workshop on Synchronizing Automata. Turku (Finland), 2004


G. Budzban, A. Mukherjea, A semigroup approach to the Road Coloring Problem,

Probability on Algebraic Structures, Contemporary Mathematics 261 (2000) 195-207

 Budzban G, Feinsilver P Completely simple semigroups, Lie algebras, and the road coloring problem
SEMIGROUP FORUM Volume: 74 Issue: 2 Pages: 206-226  2007

G Budzban, P Feinsilver,  -The Generalized Road Coloring Problem and periodic digraphs
 Arxiv preprint arXiv:0903.0192, 2009 -

Boyle M. Open Problems in Symbolic Dynamics
 Workshop on Dynamical Systems and Related Topics, MAR 15-18, 2008 Univ Maryland, College Pk, MD

 CONTEMPORARY MATHEMATICS SERIES Volume: 469 Pages: 69-118  2008

H.-D. Burkhard,

Zum Laengenproblem homogener Experimente an determinierten und nicht-deterministischen Automaten,

 Elektronische Informationverarbeitung und Kybernetik 12 (1976) 301-306 [in German]


M. Ito and M. Toyama (Eds.): DLT 2008, LNCS 5257, 240-251,


 A. Carbone,

 Cycles of relatively prime length and the Road Coloring Problem,

Israel J. of Math.123 (2001), 303-316

A. Carpi,

On synchronizing unambiguous automata,

Theoretical Comput. Sci. 60 (1988), 285-296


 A. Carpi, FD'Alessandro

The Synchronization Problem for Strongly Transitive Automata.
12th Int. Conf. DLT, Kyoto, LNCS 5257, 240-251, 2008 


 A Carpi, FD'Alessandro

The Synchronization Problem for Locally Strongly Transitive Automata
34th International Symposium, MFCS 2009, LNCS 5734 (2009) - Springer. 211-222


Arturo Carpi, Flavio D’Alessandro

Strongly transitive automata and the Cerny conjecture

Acta Informatica, V 46, 8(2009), 591-607.


A Carpi, FD'Alessandro

On the Hybrid Cerny-Road Coloring Problem and Hamiltonian Paths

- Developments in Language Theory, Springer, NY,  LNCS 6224, 2010, 124-135


  Arturo Carpi, Flavio D'Alessandro

Independent sets and synchronizing words.



A Carpi, F D'Alessandro

ˇCerný-like problems for finite sets of words

-      ICTCS'14 Fifteenth Italian Conference N 21

A Carpi, F DʼAlessandro. Independent sets of words and the synchronization problem - Advances in Applied Mathematics, 2013 - Elsevier

Cho, H., Jeong G Chartrand, P Zhang –

Chromatic graph theory 2008

 A Cerna, J Cerny
Position Identification of Moving Agents in Networks
. Acta Polytechnica Hungarica Vol. 7, No. 2, 2010. 5 -23.

J. Cerny, Poznamka k homogennym eksperimentom s konecnymi automatami,

Matematicko-Fyzikalny Casopis Slovensk. Akad. Vied 14 (1964) 208-216 [in Slovak]

J. Cerny, A. Piricka, B. Rosenauerova,

On directable automata,

Kybernetika 7 (1971), 289-298


Synchronizable automata and Graph Theory.

Workshop on Synchronizing Automata. Turku (Finland), 2004

J. Cerny

Automata and transportation theories -


Arthur Benjamin, Gary Chartrand and Ping Zhang  The Fascinating World of Graph Theory by  ACM SIGACT News, 2016

A. Cherubini. Synchronizing and collapsing words. Milan J. Math., 75:305–321, 2007.

A. Cherubini, P. Gawrychowski, A. Kisielewicz, B. Piochi.:A Combinatorial Approach to Collapsing Words. Lect.Notes in Comput. Sci. 4162 (2006),

A Cherubini, A Kisielewicz, B Piochi

On the Length of Shortest 2-Collapsing Words
Discr. Math. and Theoret. Comput. Sci. 11:1, 2009, 33–44.

Cherubini, A. Frigeri, and B. Piochi. Short 3-collapsing words over a 2-letter alphabet. In Developments in Language Theory. DLT 2011, volume 6795 of LNCS, pages 469–471, 2011.

A. Cherubini and A. Kisielewicz. Binary 3-compressible automata. In Proceedings of the 15th Italian Conference on Theoretical Computer Science (ICTCS 2014), volume 1231 of CEUR Workshop Proceedings, pages 109–120, 2014.

A. Cherubini and A. Kisielewicz. Recognizing 3-collapsing words over a binary alphabet. Theor. Comput. Sci., 629(C):64–79, 2016.

H Don, H Zantema, M de Bondt - Slowly synchronizing automata with fixed alphabet size Information and Computation, 2020 – Elsevier

H Don, H Zantema. Finding DFAs with maximal shortest synchronizing word length - International Conference on Language and Automata …, 2017 - Springer

D Chistikov, P Martyugin, M Shirmohammadi Synchronizing automata over nested words

 Conf. on Foundations of …, Berlin, 2016   LNCS, volume 9634, 252-268- Springer


Wojciech Czerwiński, Wim Martens, Tomáš Masopust

Separability of Regular Languages by Subsequences and Suffixes

Automata, Lang., Programming , LNCS 7966, 2013, 150-161

K. Culik II, J. Karhumaki, J. Kari,

A note on synchronized automata and Road Coloring Problem,

Developments in Lang.Theory (5th Int. Conf., Vienna, 2001), LNCS, 2295 (2002), 175-185

K. Culik II, J. Karhumaki, J. Kari,

A note on synchronized automata and Road Coloring Problem,

Int. J. of Foundations of Comput.Sci. 13 (2002), 459-471

H Fernau, P Wolf, T Yamakami Synchronizing Deterministic Push-Down Automata Can Be Really Hard. - arXiv preprint arXiv:2005.01381, 2020 -

H Fernau, P Wolf Synchronization of Deterministic Visibly Push-Down Automata  - arXiv preprint arXiv:2005.01374, 2020 -

Fedor Fominykh, Mikhail Volkov

Playing for Synchronization

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 159-170


 Pawel Gawrychowski

Complexity of the approximation of the shortest synchronizing word.


P Gawrychowski, D Straszak -Strong inapproximability of the shortest reset word. International Symposium on Mathematical …, 2015 - Springer

Grech, M. / Kisielewicz, A.,

The Cerny conjecture for automata respecting intervals of a directed graph .

ArXiv, 2012


M GrechA Kisielewicz . Synchronizing sequences for road colored digraphs

 - Discrete Applied Mathematics, 2020 - Elsevier


M Grech, A Kisielewicz Černý conjecture for edge-colored digraphs with few junctions

 - Electronic Notes in Discrete Mathematics, V.54,  2016, 115-120, - Elsevier


C Güniçen, E Erdem, H Yenigün

Generating Shortest Synchronizing Sequences using Answer Set Programming

Answer Set Programming  and Other Comput. Paradigms

6 Int. Workshop, 2013, Istanbul, Turkey


Vladimir V. Gusev, Marek Szykuła

On the Number of Synchronizing Colorings of Digraphs

 LNCS 9223(2015) 127-139


VV Gusev, EV Pribavkina On Synchronizing Colorings and the Eigenvectors of Digraphs

- LIPIcs-Leibniz International …, 2016 – DROPS,


Henk Don, Hans Zantema

Finding DFAs with maximal shortest synchronizing word length

arXiv:1609.06853 [math.CO]


S Hoffmann  Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words

- arXiv preprint arXiv:2007.09104, 2020 -

L. Dubuc,

Les automates circulaires biaises verifient la conjecture de Cerny,

RAIRO Informatique Theorique et Applications 30 (1996) 495-505 [in French]

L. Dubuc,

Sur les automates circulaires et la conjecture de Cerny,

RAIRO Informatique Theorique et Applications 32 (1998) 21-34 [in French]


Durmuş, M.S., Yildirim, U., Eriş, O., Söylemez, M.T.

 Synchronizing automata and Petri net based controllers

ELECO 2011 - 7th Int Conf. on Electrical and Electronics Eng. , art. no. 6140206 , II386-II390

D. Eppstein,

Reset sequences for monotonic automata,

SIAM Journal of Computing 19 (1990) 500-510


H Fernau, P Heggernes, Y Villanger

A multi-parameter analysis of hard problems on deterministic finite automata

J. Comput.Syst. Sci.81( 2),  359-484, 2015


F.M. Fominykh,  P.V. Martyugin , M.V. Volkov,

P(l)aying for Synchronization.

Int. J. Found. Comput. Sci. World Scientific, 6(24), 765-780,  2013.

Fischler, M.A., Tannenbaum, M.:

 Synchronizing and representation problems for sequential machines with masked outputs.

 In: Proc. 11th Annual Symp. Foundations Comput. Sci., pp. 97–103. IEEE, Los Alamitos (1970)


P. Frankl,

An extremal problem for two families of sets,

Eur. J. Comb., 3(1982) 125-127.

J. Friedman,

On the road coloring problem,

Proc. of the Amer. Math. Society 110 (1990), 1133-1135. 


G Chartrand, P Zhang 

Chromatic Graph Theory 



Gary Chartrand, Linda Lesniak, Ping Zhang

Graphs & Digraphs, Fifth Edition

 Taylor@Francis group, Chapman & Hall , 2010, 480p.


 P. Gawrychowski, A. Kisielewicz , 

Synchronizing words,

Palermo, AUTOMATA 2007


P Gawrychowski, A Kisielewicz –

2-Synchronizing words,

LNCS, 5196/(2008), 221-231


Gawrychowski, P., Straszak, D.,

Strong inapproximability of the shortest reset word.

In: Italiano, G., Pighizzini, G., Sannella, D. (Eds.),Math. Found. of CS 2015. Vol. 9234 LNCS. Springer Berlin Heidelberg, 243–255,  2015.


Michael Gerbush, Brent Heeringa

Approximating Minimum Reset Sequences,

LNCS, 2011, 6482/2011, 154-162


M Grech, A Kisielewicz

The Černý conjecture for automata respecting intervals of a directed graph

DMTCS vol. 15:3, 61–72, 2013


N Giambiasi, C Frydman

Timed synchronizing sequences

Proceedings of the Symposium  DEVS-14, 2014


Ginsburg, S.:

On the length of the smallest uniform experiment which distinguishes
the terminal states of a machine.

 J. Assoc. Comput. Mach. 5, 266–280 (1958)


W. Goehring,

 Minimal initializing word: A contribution to Cerny conjecture,

J. of Automata, Lang. and Comb. 2 (1997), 209-226

Goldberg, K.:

Orienting polygonal parts without sensors.

Algorithmica 10, 201–225 (1993)


F Gonze, RM Jungers

On the Synchronizing Probability Function and the Triple Rendezvous Time

Lang. and Aut., LNCS, 8977(2015), Springer, 212-223


François Gonze, Raphaël M. Jungers, Avraham N. Trahtman

A Note on a Recent Attempt to Improve the Pin-Frankl Bound

DM & TCS, 1(17), 2015, 307-308



Goran Hognas, Arunava Mukherjeaemi Groups Probability Measures on Semigroups. Convolution Products, Random Walks and Random Matrices

Probability and Its Applications, Springer,2011, 1-62

P. Goralcik, V. Koubek,

Rank problems for composite transformations,

Int. J. of Algebra and Computation 5 (1995), 309-316

M Grech, A Kisielewicz. Synchronizing sequences for road colored digraphs  - Discrete Applied Mathematics, 2020 - Elsevier

V.V. Gusev.

Lower Bounds for the Length of Reset Words in Eulerian Automata

Lect. Notes in Comput. Sci., 2011, V. 6945, Reachability Problems, 180-190


Vladimir V. Gusev

Synchronizing Automata of Bounded Rank

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 171-179


Higgins P.M.,

The range order of a product of i transformation from a finite full transformation semigroup, Semigroup Forum 37 (1988), 31-36.


J Holub, S Stekr.

On Parallel Implementations of Deterministic Finite Automata
LNCS 5642, 54-64, 2009

S Hoffmann Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words, - arXiv preprint arXiv:2007.09104, 2020 -

Galina Jirásková , Tomáš Masopust

On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata,. 229–239.


 B. Imreh, M. Ito,

On some special cases of regular languages, Jewels are Forever,

Springer Verlag, Berlin, 1999, 25-34

B. Imreh, M. Ito, M. Steinby,

On commutative directable nondeterministic automata,

Grammars and Automata for Strings: From Math. and Computer Science to Biology, and Back,

Taylor and Francis, London, 2003, 141-150

B. Imreh, M. Steinby,

Some remarks on directable automata, Acta Cybernetica 12 (1995), 23-35

B. Imreh, M. Steinby,

 Directable nondeterministic automata,

Acta Cybernetica 14 (1999), 105--115

Jourdan GV, Ural H, Yenigun H, Zhang JC (2010)

Lower bounds on lengths of checking sequences.

Formal Aspects Comput 22(6): 667–679


GV Jourdan, H Ural, H Yenigün

Reduced checking sequences using unreliable reset

- Information Processing Letters, 5(115), 532–535, 2015

M. Ito, J. Duske,

On cofinal and definite automata, Acta Cybernetica 6 (1983), 181--189.

M. Ito, M. Katsura,

On transitive cofinal automata,

 Math. Aspects of Natural and Formal Lang., World Scientific, 1994, 173-199  


M. Ito and K. Shikishima-Tsuji,

Shortest Directing Words of Nondeterministic Directable Automata. Workshop on Synchronizing Automata. Turku (Finland), 2004


Kouji Yano, Random Walk in a Finite Directed Graph Subject to a Road Coloring

J. Theoret.l Probability, 26( 1) ,, 2013, 259-283

N. Jonoska, S. A. Karl,

A molecular computation of the road coloring problem,

DNA Based Computers II, DIMACS Series in Discr. Math. and Theor. Comput. Sci. 44 (1998), 87-96

N. Jonoska, S. Suen,

Monocyclic decomposition of graphs and the road coloring problem,

Congressum Numerantium 110 (1995), 201-209

Bang-Jensen Jorgen, Gutin  Gregory
Digraphs: Theory, Algorithms and Applications. Springer Monographs in Math., 2-nd ed., 2009



Cruisable graphs. Proc. of the Journees Montoises, 2006


Raphaël M. Jungers

The Synchronizing Probability Function of an Automaton

SIAM J. Discrete Math. 26/1, 2012, 177-192


H. Jurgensen, Complexity, Information, Energy. Novy Smokovnec, Slovakia, DFCS 2007

Helmut Jurgensen  Synchronization Information and Computation. LATA 2007,v. 206, Iss. 9-10.1033-1044, 2008.


J. Kari, A counter example to a conjecture concerning synchronizing words in finite automata, Bulletin of the EATCS 73 (2001), 146

J. Kari, Synchronization and stability of finite automata, J. Univ. Comput. Sci. 8 (2002), 270-277

J. Kari, Synchronizing finite automata on Eulerian digraphs, Math. Found. of Comput. Sci.

 (26th Int. Symp., Marianske Lazne, 2001), LNCS, 2136 (2001), 432-438


J. Kari, M Volkov

Cerný's conjecture and the road coloring problem

Handbook of Automata, 2013


N Karimi Synchronizing Coloring Of A Directed Graph
Proc. of the IMECS 2010, Hong Kong,, V. III, 1-5


Sertaç Karahoda Osman Tufan Erenay Kamer Kaya Uraz Cengiz Türker, Hüsnü Yenigün

Parallelizing Heuristics for Generating Synchronizing Sequences

ICTSS 2016: Testing Software and Systems, 106-122


 M. Karpinski and R. Schmied. Improved inapproximability results for the shortest         superstring and related problems. In 19th Computing: The Australasian Theory Symposium (CATS 2013), Adelaide, Australia,volume 141 of CRPIT, pages 27–36, 2013.


V. Karthikeyan and M. Rajasekar

Strong γ-Syncronization in Fuzzy Automata

Int. Math. Forum, Vol. 6, 2011, no. 31, 1521 - 1528


V. Karthikeyan and M. Rajasekar

Homomorphism of γ-Synchronization in Fuzzy Automata

Int. J. Contemp. Math. Sciences, Vol. 6, 2011, no. 31, 1505 - 1514


Alica Kelemenova. On the lenght of the shortest reset words for Kn,3 automata.


A. Kelemenova, Synchronizing automata: Reset strings and state complexity 13th IEEE Int. Symposium on Comput. Intel. and Inform., Proc., art. no. 6496796 , CINTI 2012  391-394

J. Kari, Synchronizing finite automata on Eulerian digraphs, Theoretical Computer Science 295 (2003), 223-232 (pdf-file)

N Karimi - Reaching the minimum ideal in a finite semigroup

Semigroup Forum,  94, Issue 2, pp 390–425 2017 - Springer

D. J. Kfoury, Synchronizing sequences for probabilistic automata, Studies in Appl. Math., 29 (1970), 101-103.

A Kisielewicz, J Kowalski, M Szykuła

A Fast Algorithm Finding the Shortest Reset Words

LNCS,  Comput. and Comb, Springer, 7936, 2013, 182-196


A Kisielewicz, M Szykuła

Generating Small Automata and the Černý Conjecture

Impl. and Appl. of Automata, LNCS ,  7982(2013),  340-348


A Kisielewicz, J Kowalski, M Szykuła

Computing the shortest reset words of synchronizing automata

- Journal of Comb. Optim., 88-124,  29(2015) and 1-27, 2013


A. Klyachko, I. C. Rystsov, M. A. Spivak, An extremal combinatorial problem associated with the bound of the length of a synchronizing word in an automaton,

Kibernetika (1987), No.2, 16-20, 25  [in Russian; English translation: Cybernetics 23 (1987), 165-171]


Z. Kohavi, Switching and finite automata theory, McGraw-Hill Book Co., New York, 1970

Z. Kohavi, J. Winograd, Establishing certain bounds concerning finite automata, Journal of Computer and System Science

7 (1973) 288-299


 Kohavi, Z., Winograd, J.: Bounds on the length of synchronizing sequences and the
order of information losslessness. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines
and Computations, pp. 197–206. Academic Press, New York (1971)


J Kowalski, A Roman A New Evolutionary Algorithm for Synchronization

 - European Conference on the Applications of …, 2017 - Springer

A Kisielewicz, J Kowalski, M Szykuła Experiments with synchronizing automata

-IC Impl. and Application of Automata, CIAA 2016. LNCS, vol 9705, 2016 - Springer

A Kisielewicz, J Kowalski, M Szykuła. Computing the shortest reset words of synchronizing automata. - Journal of Combinatorial …, 2015 - Springer

A Kisielewicz, J Kowalski, M Szykuła - Journal of Combinatorial …, 2015 - Springer

Kudłacik, R. Roman, A. Wagner, H.,

Effective Synchronizing Algorithms

Expert Syst. Appl., 39 (14), 11746-11757, 2012


34.Kushik N, Yevtushenko N

 On the length of homing sequences for nondeterministic finite state machines. In: Konstantinidis S (ed) CIAA, LNCS, vol 7982. Springer, New York, 220–231, (2013)


Laemmel, A.E., Rudner, B.:

 Study of the application of coding theory, Report PIBEP-69-034, Polytechnic Inst. Brooklyn, Dept. Electrophysics, Farmingdale (1969)


E Lerner

On Synchronizing Automata and Uniform Distribution

Implementation and Application of Automata, 202-212, 2016 - Springer


Z Liu, A Frigeri, A Cherubini

Composing short 3-compressing words on a 2-letter alphabet. - Discrete Mathematics & Theoretical Computer Science, 2017



S. W. Margolis, J.-E. Pin, M. V. Volkov, Words guaranteeing minimal image,

Words, Languages and Combinatorics (III Int. Coll., Kyoto, 2000),

World  Sci., Singapore, 2003, 297-310,  IJFCS 15 (2004), 259-276


B. Marcus

Symbolic Dynamics. Encyclopedia of Complexity and Systems Science

Springer, New York, 2009, 8888-8910


P. Martjugin. A series of slowly synchronizable automata with a zero state over a small alphabet.

Tarragona Proc. of  LATA 2007


P. Martjugin. The Length of Subset Reachability in Nondeterministic Automata
 Electronic Notes in Theoret. Comput. Sci., V. 223, 26, 2008, 187-200


 P.Martjugin, Series of slowly synchronizing automata with a zero state over a small alphabet,

 Information and Computation. v. 206, Iss. 9-10, 1197-1203, 2008.



Complexity of problems concerning reset words for some partial cases of automata

Acta Cybernetica , V 19,  Issue 2,  2009 , 517-536  



Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFAP.
Computer Science–Theory and Applications, 2010 - Springer - LNCS(6072), 2010, 288-297


A lower bound for the length of the shortest carefully synchronizing words.
Russian Mathematics (Izv VUZ), 2010 Matematika, 2010, No. 1, 59–68.


Pavel V. Martyugin

Synchronization of Automata with One Undefined or Ambiguous Transition

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 278-288.


P. Martyugin

Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata

 Theory of Comput. Syst., Springer Sci.-Busyness Media, NY, 2013


Tomáš Masopust, Michaël Thomazo

On the Complexity of k -Piecewise Testability and the Depth of Automata

LNCS 9168(2015), 364-376


A. Mateescu, A. Salomaa,

Many-valued truth functions, Cerny's conjecture and road coloring,

Bulletin of the EATCS 68 (1999) 134-150

B. K. Natarajan,

An algorithmic approach to the automated design of parts orienters,

Foundations of Computer Science (27th Annual Symposium), IEEE, 1986, 132-142

B. K. Natarajan,

Some paradigms for the automated design of parts feeders,

 International Journal of Robotics Research 8 (1989), No.6, 89-109

Néraud, J.

Completing circular codes in regular submonoids TCS 391 (1-2) , 2008,  90-98


L. Niemela, On the directability of automata, Kybernetika 25 (1989), 419-421

G. L. O'Brien, The road coloring problem, Israel Journal of Mathematics, 39 (1981), 145-154.

J Olschewski, M Ummels. The complexity of finding reset words in finite automata - International Symposium on Mathematical …, 2010 - Springer

D. Perrin, Codes asynchrones. Bull.  Soc. Math. de France 105, 1977, 385-404.


D. Perrin, Synchronizing automata, Sequences II. Methods in Communication,

Security and Computer Science (International Workshop, Positano, 1991),

Springer-Verlag, New York, 1993, 470-476

D. Perrin, M. P. Schutzenberger, Synchronizing prefix codes and automata and the road coloring problem,

Symbolic Dynamics and its Applications, Contemporary Mathematics 135 (1991), 295-318

T. Petkovic, M. Ciric, S. Bogdanovic, Characteristic semigroups of directable automata,

Developments in Language Theory (6th International Conference, Kyoto, 2002),

Lecture Notes in Computer Science 2450 (2003), 417-428

T. Petkovic, M. Steinby, Piecewise directable automata, Journal of Automata, Languages and Combinatorics 6 (2001), 205-220


I. V. Petrov The mirror image of the language of 2-synchronizing words. Izv. Vyssh. Uchebn. Zaved. Mat., 2010,  1, 69–73

I. Petrov. An algorithm for recognition of n-collapsing words. Theoret. Comput. Sci., 391(1-2):99–108, 2008.

J.-E. Pin, Sur la longueur des mots de rang donne d'un automate fini, Comptes Rendus de l'Academie des Sciences

 284 (1977), 1233-1235 [in French]

J.-E. Pin, Le probleme de la synchronisation. Contribution a l'etude de la conjecture de Cerny,

These 3e cycle, Paris, 1978 [in French]

J.-E. Pin, Sur les mots synchronisants dans un automate fini, Elektronische Informationverarbeitung und Kybernetik

14 (1978), 283-289 [in French]

J.-E. Pin, Sur un cas pariculier de la conjecture de Cerny, Automata, Languages, Programming

 (5th Colloquium, Udine, 1978), Lecture Notes in Computer Science 62 (1978), 345-352 [in French]

J.-E. Pin, Utilisation de l'algebre lineaire en theorie des automates, Actes du 1er Colloque

AFCET-SMF de Mathematiques Appliquees, AFCET, 1978, Tome II, 85-92 [in French]

J.-E. Pin, Le probleme de la synchronisation et la conjecture de Cerny,

Non-commutative Structures in Algebra and Geometric Combinatorics, Quaderni de la Ricerca Scientifica 109 (1981), 37-48

J.-E. Pin, On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17 (1983), 535-548

Pixley, C., Jeong, S.-W., Hachtel, G.D.: Exact calculation of synchronization sequences
based on binary decision diagrams. In: Proc. 29th Design Automation Conf., pp.
620–623. IEEE, Los Alamitos (1992)

A. Piricka, Directable automata and directly subdefinite events, Kybernetika 8 (1972), 395-403

E.V. Pribavkina

2-­Collapsing Words And A Sequence Reconstruction Problem, Palermo, AUTOMATA 2007

E. V. Pribavkina. On some properties of the language of 2-collapsing words. In Developments in Language Theory, volume 3572 of LNCS, pages 374–384, 2005.

EV Pribavkina, E Rodaro  -Finitely Generated Synchronizing Automata

 LATA 2009, LNCS 5457, 672–683, 2009.


EV Pribavkina, E Rodaro

State Complexity of Prefix, Suffix, Bifix and Infix Operators on Regular Languages

Developments in Language Theory, 2010  Springer  LNCS   6224, 376-386


E. V. Pribavkina

Slowly synchronizing automata with zero and noncomplete sets

Math. Notes Vol. 90, N. 3-4, 411-417


Elena V. Pribavkina and Emanuele Rodaro

Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete

Lecture Notes in Computer Science, 6735(2011) Models of Computation in Context, 230-238

VY Protasov Surface Dimension, Tiles, and Synchronizing Automata, - SIAM Journal on Mathematical Analysis, 2020 - SIAM

Igor T. Podolak, Adam Roman and Dariusz Jędrzejczyk

Application of Hierarchical Classifier to Minimal Synchronizing Word Problem

AISC, LNCS 7267(2012), 421-429


Podolak, A Roman, M Szykuła, B Zieliński. A machine learning approach to synchronization of automata. I - Expert Systems with …, 2018 - Elsevier

K. Raiha and E. Ukkonen. The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science, 16:187–198, 1981.

Rampersad, N., Shallit, J., Xu, Z.

The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages

Fundamenta Informaticae 116 (1-4) , 2012, 223-236


Rauff, James V


Mathematics and Computer Education. 01, 2009.


A Restivo, R Vaglica

Automata with Extremal Minimality Conditions –

 DLT, 2010 - Springer  LNCS   6224, 399-410


M Rigo - Advanced graph theory and combinatorics

2016 - John Wiley & Sons


A Rezchikov, V Kushnikov, V Ivaschenko The Approach to Provide and Support the Aviation Transportation System Safety Based on Automation Models

CSOC 2017: Software 244-254 2017 - Springer


Rho, J.-K., Somenzi, F., Pixley, C.:

Minimum length synchronizing sequences of finite state machine.

In: Proc. 30th Design Automation Conf., pp. 463–468. ACM, New York (1993)


R Reis, E Rodaro Ideal regular languages and strongly connected synchronizing automata

 - Theoretical Computer Science,– V. 653,  2016, 97-107, Elsevier


Emanuele Rodaro

Finiteness problem for the language of minimal synchronizing words.



E Rodaro - A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number. J. of Algebraic Comb, 2019 - Springer

A. Roman

Two simple methods for obtaining new classes of automata fulfilling Cerny Conjecture

Schedae Informaticae 16 (2007), 35-46 .

A. Roman

Merging states and synchronization problem

Schedae Informaticae 15 (2006), 95-108


A. Roman,

Synchronization of finite automata.

 J. of Automata, Languages and Comb. (submitted).


A. Roman,

Merging states and Synchronization Problem

Workshop on Synchronizing Automata. Turku (Finland), 2004


 A. Roman,

New algorithms for finding short reset sequences in synchronizing automata
5th Int. Enform. Conf. (IEC 05),  2005 Prague, ENFORMATIKA, VOL 7: IEC 13-17 2005

A. Roman,

Synchronization of finite automaton. Computations for different alphabet sizes.

Workshop on words and automata. S-Petersburg, June, 2006


A. Roman,

A note on Cerny Conjecture for automata over 3-letter alphabet,

Journal of Automata, Languages and Combinatorics 13 (2008) 2, 141--143.

Adam Roman and Wit Forys.

Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata.


A. Roman,

Genetic Algorithm for Synchronization  

LNCS,   5457( 2009) 684-695

A. Roman,

Synchronizing finite automata with short reset words .
Conf.on Comput. Sci. and Eng.(ICCMSE 2005), OCT 21-26, 2005

APPLIED MATH. AND COMPUT.  Issue: 1, 125-136 209(2009) 125-136


A. Roman
Decision Version of the Road Coloring Problem is NP-complete,

LNCS 5699 (2009) 287-297


A. Roman

Experiments on Synchronizing Automata

Schedae Informaticae, Versita, Warsaw, V. 19, 35-51, 2010


Roman, Adam

The NP-completeness of the Road Coloring Problem

 Information Processing Letters, 111 (7), .342,  2011


Adam Roman

P–NP Threshold for Synchronizing Road Coloring

Language and Automata Theory and Applications, LNCS 7183(2012), 480-489


A Roman, M Szykuła

Forward and backward synchronizing algorithms

 Expert Syst. Appl., 2015 - Elsevier 42, (24), 2015, 9512–9527


A Roman Data validation using model-based testing and finite automata synchronization. - AIP Conference Proceedings, 2017


I. C. Rystsov,

An almost optimal estimate for the length of a reset word for regular automata,

Doklady Akademii Nauk Ukrainy (1992), No.9, 5-8 [in Russian]

I. C. Rystsov,

Rank of a finite automaton,

Kibernetika i Sistemnyj Analiz (1992),  No.3, 3-10 [in Russian; English translation: Cybernetics and System Analysis 28 (1992), 323-328]

I. C. Rystsov,

Reset words for solvable automata,

Kibernetika i Sistemnyj Analiz (1994),

No.6, 21-26 (in Russian; English transl.: Cybernetics and System Analysis 30 (1994), 807-811)

I. C. Rystsov,

Almost optimal bound of reccurent word length for regular automata,

Kibernetika i Sistemnyj Analiz (1995), No.5, 40-48 [in Russian;

English translation: Cybernetics and System Analysis 31 (1995), 669-674]

I. C. Rystsov,

Quasioptimal bound for the length of reset words for regular automata,

Acta Cybernetica 12 (1995), 145-152

I. C. Rystsov,

Exact linear bound for the length of reset words in commutative automata,

Publicationes Mathematicae Debrecen 48 (1996), 405-411

I. C. Rystsov,

Reset words for commutative and solvable automata,

Theoretical Computer Science, 172 (1997), 273-279

I. C. Rystsov,

Reset words for automata with simple idempotents,

Kibernetika i Sistemnyj Analiz (2000),  No.3, 32-39 [in Russian; English translation: Cybernetics and System Analysis 36 (2000), 339-344]

I. C. Rystsov,

Representations of regular ideals in finite automata,

Kibernetika i Sistemnyj Analiz (2003),  No.3, 48-58 [in Russian] 

I. C. Rystsov,

Height of a finite automaton,

Kibernetika i Sistemnyj Analiz, accepted [in Russian]

I. Rystsov,

Cerny Conjecture: Retrospects and Prospects.
Workshop on Synchronizing Automata. Turku (Finland), 2004


G Saccher

Book revuews

Monatshefte für Mathematik

2015, 3(178), 489-492


A. Salomaa,

Generation of constants and synchronization of finite automata,

Journal of Universal Computer Science 8 (2002), 332-347

A. Salomaa,

Synchronization of finite automata: contributions to an old problem,

The Essence of Computation, Lecture Notes in Computer Science 2566 (2002), 37-59

A. Salomaa,

Composition sequences for functions over a finite domain,

Theoretical Computer Science, 292 (2003), 263-281


 Arto Salomaa

Composition Sequences and Synchronizing Automata

Computation, Physics and Beyond, LNCS,  7160(2012), 403-416,


W. Samotij,

A note on the complexity of the problem of finding shortest synchronizing words,

Palermo, AUTOMATA 2007


Sandberg, S.:

Homing and synchronizing sequences.

In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5–33. Springer, Heidelberg (2005)


MV Sapir


Combinatorial Algebra: Syntax and Semantics,  2014 - Springer


N. Sauer, M. G. Stone,

Composing functions to reduce image size,

Ars Combinatoria 31 (1991), 171-176

George G. Szpiro

A Mathematical Medley: Fifty Easy Pieces on Mathematics

AMS Bookstore, 2010, 236


T. Shcherbak.

The interval rank of monotonic automata.

 IMPL. and APPL. of Automata. 3845,2006, 273-281.


S. Shin, J. Yoo  

A note on the rank of semigroups  

Semigroup Forum V 81, N 2, 335-343, 2010


M Szykuła, V Vorel - An Extremal Series of Eulerian Synchronizing Automata

… Conference on Developments in Language Theory, 380-392, 2016 - Springer


M Szykuła - Improving the upper bound the length of the shortest reset words

- arXiv preprint arXiv:1702.05455, 2017 


Evgeny Skvortsov, Evgeny Tipikin

Experimental Study of the Shortest Reset Word of Random Automata,

in Implementation and Application of Automata(2011)


Rm. Somasundaram and M. Rajasekar


Far East Journal of Applied Mathematics  V 27, Issue 1(2007), 77 - 84


, S.-W., Somenzi, F., Pixley, C.:

 Synchronizing sequences and symbolic traversal techniques in test generation.

J. Electronic Testing 4, 19–31 (1993)


R Stahlbock, S Vo

Efficiency considerations for sequencing and scheduling of double-rail-mounted
- International Journal of Shipping and Transport v 2,  N1, 2010, 95-123


P. H. Starke,

Eine Bemerkung ueber homogene Experimente,

Elektronische Informationverarbeitung und Kybernetik, 2 (1966), 257-259 [in German]

P. H. Starke,

Abstrakte Automaten,

VEB Deutscher Verlag der Wissenschaften, Berlin, 1969

 [in German; English translation: Abstract Automata, North-Holland Publishing Company,

Amsterdam-London, and American Elsevier Publishing Company, Inc., New York, 1972

M. Steinby,

On definite automata and related systems,

Annales Academiae Scientiarum Fennicae, Series A I, 444 (1969), 1-57


Benjamin Steinberg

The Černý conjecture for one-cluster automata with prime length cycle.

Theoret. Comput., Sci., 412(39), 5487-5491, 2011


B. Steinberg

A Theory of Transformation Monoids:

Combinatorics and Representation Theory, The Electronic J. of Combin.,  v.17,  i. 1,   2010, 3-56

  B Steinberg,

Cerny's conjecture and group representation theory.

J. of Alg. Combin.  2009 Springer Science+Business Media, 105-112, LLC 2009 .

B Steinberg
The averaging trick and the Cerny conjecture
Trans. Amer. Math. Soc. 361 (2009), 1429–1461.

- Developments in Language Theory, Springer, NY,

 LNCS 6224, 2010, 423-431

B. Steinberg
Cerny’s conjecture and group representation theory
  Journal of Algebraic Combinatorics, v. 31,  1 ( 2010 ), 83-109

B. Steinberg  13 Transformation Monoids

 in Representation Theory of Finite Monoids, 191-204, 2016 - Springer


L. M  Surhone, M. T. Timpledon, S. F Marseken 

Road Coloring Problem .

VDM Verlag Dr. Mller AG & Co. Kg,  2010, 76


 A.N. Trahtman,

Cerny conjencture for DFA accepting star-free languages.

ICALP, Workshop on synchronizing automata, Turku, Finland, July 16, 2004

A.N. Trahtman,

Some results of implemented algorithms of synchronization.

10-th Journees Montoises d'Inform. Theor., LIege, Belgia, September 8-11, 2004

A.N. Trahtman,

An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture.

31st Int. Symp. on Math. Found. of Comput. Sci.  2006. LNCS 4162 (2006),789-800

A.N. Trahtman,

Notable trends concerning the synchronization of graphs and automata.

El. Notes in Discr. Math., 25(2006), 173-175

A.N. Trahtman,

The Cerny Conjecture for Aperiodic Automata.  

 DMTCS 9:2, 2007, 3-10.

 A.N. Trahtman 

 Synchronization of some DFA.

TAMC 2007,  LNCS 4484, 234-243, 2007


A.N. Trahtman,

Cerny Conjecture for DFA Accepting Star-free Languages.
Workshop on Synchronizing Automata. Turku (Finland), 2004


A.N. Trahtman 

 Some aspect of synchronizing road coloring.


Trahtman A.N.

The Road Coloring and Cerny Conjecture.
Proc. of Prague Stringology Conference. 1-12, 2008.

Trahtman A.N.

Synchronizing Road Coloring.
5-th IFIP WCC-TCS, Springer, , 43-53, 273(2008). INT. FED. FOR INF. PROCESSING


Trahtman A.N.

Some Aspects of Synchronization of DFA -
 Journal of Computer Science and Technology, 719-727, V23(5), 2008


 Trahtman  A.N.,

The road coloring problem,

 Israel J. Math,  1(172), 51-60, 2009

Trahtman A.N.,

A Subquadratic Algorithm for Road Coloring
- Arxiv preprint arXiv:0801.2838, 2008 -

Trahtman A. N.

A Partially Synchronizing Coloring

CSR-2010, LNCS 6072, Springer, 2010, 362-370


Trahtman A.N, Bauer T., Cohen N.

Linear visualization of a Road Coloring.

9 Cologne Twente workshop on graphs and Comb. Optim., Cologne 2010, 13-16


Trahtman A.N,

Upper bound on the length of the reset word. 

Dynamical asp. of Autom. and Semigr. Theor. Vienna, 2010.


Trahtman A.N.

An Algorithm for Road Coloring.

Lect. Notes in Comp. Sci, Springer, 7056 (2011), Springer, 349—360


Trahtman A.N.

Some new Features and Algorithms for the Study of DFA

Open J. Discr. Math., 2(2), 2012, 45-50


Trahtman  A.N.

 An algorithm for road coloring.

J. Discr. Alg. 213–223, 16 (2012)


Travers, N., Crutchfield, J.: Exact Synchronization for Finite-State Sources,

J. Stat. Phys. 145:5 pp. 1181–1201, 2011.


Travers, N., Crutchfield, J.: Asymptotic Synchronization for Finite-State Sources,

J. Stat. Phys. 145:5 pp. 1202–1223, 2011.

J. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83:1–20, 1989.

Ural H, Williams C (2006)

Constructing checking sequences for distributed testing.

Formal Aspects Comput 18(1): 84–101


 Vojtěch Vorel

Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata

Language and Automata Theory and Appl.  LNCS 8370, 2014.  576-587 


M.V. Volkov ,

 Synchronizing strongly connected digraphs.



 M.V. Volkov 

Synchronizing automata preserving a chain of partial orders

CIAA 2007, Prague,  LNCS. 4783, 27-37, 2007


  Volkov MV

Synchronizing Automata and the Cerny Conjecture.
 Lang.& Aut. Theory & Appl. 2-d Int.Conf., Lata, Spain,  2008,

Springer, 11-27, 2008


Volkov, M.:

Open Problems on Synchronizing Automata.

'Around the Cerny Conjecture', Wroclaw (2008)

 Volkov, M.:

Synchronizing Automata and the Road Coloring Theorem.

Tutorial on Workshop on Algebra, Combin. and Complexity, WACC 2008, Russia (2008)


 M.V. Volkov
Synchronizing automata preserving a chain of partial orders
Theoretical Computer Science 410 (37), 3513-3519, (2009)

V Vorel, A Roman

Complexity of road coloring with prescribed reset words

Language and Automata Theory and Applications,

LNCS 8977(2015), 161-172



Yaokun Wu and Xinmao Wang,

 Synchronizing Problems for General Digraphs
Workshop on Synchronizing Automata. Turku (Finland), 2004


V Vorel Subset synchronization and careful synchronization of binary finite automata

- 2016 Int. J. Found. Comput. Sci., 27, 557 (2016).  - World Scientific


V Vorel  Complexity of a problem concerning reset words for eulerian binary automata

- Information and Computation, olume 253, Part 3, Pages 497–509 2017 - Elsevier


V Vorel. Subset Synchronization and Careful Synchronization of Binary Finite Automata - arXiv preprint arXiv:1403.3972, 2014 -

 K Zhang, Q Wang, CL Giles Adversarial Models for Deterministic Finite Automata  - Canadian Conference on Artificial …, 2020 - Springer



A word w is called synchronizing (recurrent, reset, directable) word of an automaton if w sends all states of the automaton on a unique state.

A deterministic finite automaton (DFA) with complete state transition graph G and transition semigroup S is considered. The problem of synchronization of DFA is natural and various aspects of this problem were touched upon the literature. Synchronization makes the behavior of an automaton resistant against input errors since, after detection of an error, a synchronizing word can reset the automaton back to its original state, as if no error had occurred. Therefore different problems of synchronization draw the attention.

A problem with a long story is the estimation of the minimal length of synchronizing word. Most known as a Cerny conjecture, it was aroused independently by distinct authors. Jan Cerny had found in 1964 n-state complete DFA with shortest synchronizing word of length (n-1)2. He had conjectured that it is an upper bound for the length of the shortest synchronizing word for any n-state complete DFA. The best known upper bound is now equal to (n3-n)/6. The conjecture holds true for wide class of automata, but in general the problem remains open. This simply looking conjecture is now one of the most longstanding open problems in the theory of finite automata.

The existence of some non-trivial subgroup in the transition semigroup of the automaton is essential in many investigation of Cerny conjecture. An opposite approach confirms the conjecture for automata having syntactic semigroup without non-trivial subgroups and proved to be fruitful:

The synchronizing DFA has a synchronizing word of length not greater than n(n-1)/2 for automata with syntactic semigroup having only trivial subgroups and therefore the Cerny conjecture holds true for such DFA.

The testing of synchronizing automata is an indispensable part of investigation in this area.
The best known to date algorithm of Eppstein finds a synchronizing word for n-state DFA in O(n3+n2q) time. The integer q denotes here the size of the input alphabet.

The C/C++ compact package TESTAS is mentioned on home pages of several prominent CONFERENCES among the systems for manipulating automata.
We realize in the package two modifications of Eppstein algorithm called cyclic and semigroup algorithms. For wide class of automata the time complexity of semigroup algorithms is O(n2q). There are no examples of automata for the time being such that the length of the shortest synchronizing word is greater than (n-1)2. The length of synchronizing word found by the algorithm was not greater than n2 in all considered to date cases including exotic examples of Cerny, Kari, Roman and all n-state automata for n<11.
In the class of automata for n<11 with alphabet of size 2 and for n<8 with alphabet of size < 5, all automata with shortest synchronizing word of (n-1)2 are found. There are 8 such automata out of Cerny sequence and five of them are found by the package TESTAS.
The theoretical possibility of the existence of examples with length of the minimal synchronizing word essentially greater than n2 is doubtful and connected mostly with disproof of the conjecture of Cerny. We consider the last algorithm as almost quadratic.

An algorithm to verify synchronizability of deterministic finite automaton has order O(n2) (in the worst case). The package TESTAS contains also Eppstein algorithm for finding synchronizing word, an algorithm for finding synchronizing word based on the results of Frankl and Klyachko-Rystsov-Spivak of O(n4q) time complexity and straightforward algorithm for finding synchronizing word of minimal length.

An automaton with transition graph G is synchronizing iff G2 has a sink state.

The last statement is a base for an algorithm to verify synchronizability of deterministic finite automaton of order O(n2) in the most worst case. The algorithm is subquadratic.

The comparison of the experimental data suggests that the length of the synchronizing word found by considered algorithms is normally much closer to the length of synchronizing word of the minimal length than to the above-mentioned theoretical upper bound. The results of the algorithms altogether correspond to the Cerny conjecture.