BIBLIOGRAPHY,  synchronization @  TESTAS
 

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

 

The package includes three main and some auxiliary programs. The main programs:
1) analyze an automaton of the language presented as oriented labeled graph (local testability and generalizations, piecewise testability, their levels);
2) find syntactic semigroup of the automaton, check the syntactic semigroup of automaton for the properties from 1)
3)view visual image of the graph (or subgraph) based on its structure properties (linear procedure),

4)check the synchronizabity, find synchronizing words,
5)find road coloring of DFA


The auxiliary programs (not included in DEMO version) find:
1) direct product of two transition graphs of the automaton;
2) direct product of two syntactic semigroups of the automaton 

 

      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), http://arxiv.org/abs/math/0702400v1

  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

 

  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)
IZVESTIYA VYSSHIKH UCHEBNYKH ZAVEDENII Math. 2010, N 1,  3–13

 

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

THEORETICAL COMPUTER SCIENCE 330 (1): 3-13 JAN 31 2005
 

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

 

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

 A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD

IN ONE-CLUSTER AUTOMATA

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

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

 

JEAN BERSTEL, DOMINIQUE PERRIN, CHRISTOPHE REUTENAUER

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

 

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

S. Bogdanovic, B. Imreh,

: Directable automata and their generalizations

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

P. Borovansky, M. Wincer,

Speed of direction of finite automata,

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

Boyle M.

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

 

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.
ZVESTIYA VYSSHIKH UCHEBNYKH ZAVEDENII Math., 2010, ? 1, 14-20
 

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 - arxiv.org

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

 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.

AROUND THE CERNY CONJECTURE, Wroclaw, Poland, 2008

 

A Carpi, F D'Alessandro

ˇCerný-like problems for finite sets of words

- ICTCS'14 Fifteenth Italian Conference N 21

 

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
 

J.Cerny,

Synchronizable automata and Graph Theory.

Workshop on Synchronizing Automata. Turku (Finland), 2004

J. Cerny

Automata and transportation theories -
AROUND THE CERNY CONJECTURE, Wroclaw, Poland, 2008

 

Cherubini A.

: MILAN JOURNAL OF MATHEMATICS. 75:1, 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 ...

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
 

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.

AROUND THE CERNY CONJECTURE, Wroclaw, Poland, 2008

 

Grech, M. / Kisielewicz, A.,

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

ArXiv, 2012

 

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


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

 

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 

DISCR. MATH. & ITS APPL.2008

 

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

 

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)


P. Goralcik, V. Koubek,

Rank problems for composite transformations,

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

 

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

 

Goran Hognas, Arunava Mukherjea

Semigroups Probability Measures on Semigroups. Convolution Products, Random Walks and Random Matrices

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

 

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

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

Lower bounds on lengths of checking sequences.

Formal Aspects Comput 22(6): 667–679


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

 

R JUNGERS, VD BLONDEL –

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

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.

AROUND THE CERNY CONJECTURE, Wroclaw, Poland, 2008


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)


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. 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)

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)

 

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.

 

P.Martyugin

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

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

 

P.Martyugin

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

P.Martyugin

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

 

 

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.

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

 

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

 

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

 

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

Application of Hierarchical Classifier to Minimal Synchronizing Word Problem

AISC, LNCS 7267(2012), 421-429

 

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

WAY BACK FROM ANYWHERE: EXPLORING THE ROAD COLORING CONJECTURE

Mathematics and Computer Education. 01, 2009.

 

A Restivo, R Vaglica

Automata with Extremal Minimality Conditions –

 DLT, 2010 - Springer  LNCS   6224, 399-410

 

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)

 

Emanuele Rodaro

Finiteness problem for the language of minimal synchronizing words.

AROUND THE CERNY CONJECTURE, Wroclaw, Poland, 2008


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.

LNCs, SOFSEM 2008

A. Roman,

Genetic Algorithm for Synchronization  

LNCS,   5457( 2009) 684-695

A. Roman,

Synchronizing finite automata with short reset words .
Conf.on Comput. Meth.in 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

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


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

Semigroups.

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

 

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

 SYNCHRONIZATION OF EULERIAN AUTOMATON

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

 

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.

AROUND THE CERNY CONJECTURE, Wroclaw, Poland,  2008

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 - arxiv.org

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.

 

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.

AROUND THE CERNY CONJECTURE, Wroclaw, Poland, 2008

 

 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)

Yaokun Wu and Xinmao Wang,

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

 

SYNCRONIZATION ALGORITHMS AND CERNY CONJECTURE.

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.

 

 

  home