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
Springer Monographs in Mathematics. Springer, 67-80
J. Almeida, A. Cardoso
A Sequence of Weakly Monotonic Automata with
Increasing Level
Int. J. Algebra, 7 ( 2),
91 – 100, 2013
Dmitry Ananichev,
Vladimir Gusev, Mikhail Volkov
Slowly Synchronizing
Automata and Digraphs
LNCS 6281(010), MFCS
2010, 55-65
Dmitry S. Ananichev,
Примитивные
орграфы с
большими
экспонентами
и медленно
синхроизируемые
автоматы
(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.
LECTURE NOTES IN
COMPUTER SCIENCE 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,
Developments in Language Theory (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 International Conference on
Combinatorics on Words,
Turku Centre of
Computer Science General Publication 27 (2003), 411-418
D. S. Ananichev,
Int. J. of Found. of
Comput. Sci. 17, 3(2006), 507-518, Lecture Notes in Computer Science, 3572:
11-21 2005
D. S. Ananichev, M.
V. Volkov, Synchronizing Generalized Monotonic Automata.
Workshop
on Synchronizing Automata.
D. S. Ananichev, M. V. Volkov, Yu. I. Zaks, Synchronizing automata with a
letter of deficiency 2,
Lecture Notes in
Computer Science, 4036(2006), 433-442
D.S, Ananichev, M.V. Volkov, Y. I. Zaks Synchronizing
automata with a letter of deficiency 2,
THEORET. COMPUT. SCI.
Volume: 376 Issue: 1-2 Pages: 30-41,
2007
D. S. Ananichev, M. V. Volkov, Collapsing words vs. synchronizing words,
Developments in
Language Theory (5th International Conference,
D. S. Ananichev, M. V. Volkov, Synchronizing
monotonic automata, Developments in Language Theory
(7th International Conference, Szeged, 2003),
Lecture Notes in Computer Science 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,
Semigroups and
Languages (International Workshop,
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
Theoretical
Computer Science V. 359, 1, 2006, 101-110
M.P.Beal,
J.Berstel, B Marcus, D Perrin,
Length Codes and Finite Automata World Sci. 2008
MP Beal, D
Perrin - A quadratic algorithm for road coloring
arXiv:0803.0726v2 [cs.DS]
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
MP Beal, D Perrin
A Quadratic Upper
Bound on the Size of a Synchronizing Word in One-Cluster Automata
Stuttgart, Germany, DLT, 81-90, LNCS 5583( 2009)
MP Beal, D Perrin
A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster
Automata
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
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
JEAN BERSTEL, DOMINIQUE PERRIN, CHRISTOPHE REUTENAUER
Codes and Automata,
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.
Biskup, M.T.
Plandowski, W. ,
Shortest synchronizing strings for Huffman codes
Theoretical Computer Science, 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 Conference of Young Computer Scientists
(Smolenice Castle,
1982),
Boyle M. Open
Problems in Symbolic Dynamics
Geom. & prob. struct. In dynamics: CONT. MATH. SER. v. 469, 69-118,
2008
The generalized road
coloring problem and periodic digraphs
Applicable
Algebra in Engineering, Communication and Computing, 2011
V 22, N
1, 2011, 21-35
Budzban
G., Feinsilver P.
An approach to road coloring problem based on vector spaces.
(Ïîäõîä ê çàäà÷å ðàñêðàñêè äîðîã, îñíîâàííûé íà âåêòîðíûõ ïðîñòðàíñòâàõ)
ZVESTIYA VYS
2010, ? 1, 14-20
G. Budzban,
Semigroups and the Generalized Road Coloring Problem.
Workshop on Synchronizing
Automata.
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
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,
A. Carpi, On
synchronizing unambiguous automata, Theoretical Computer Science 60 (1988),
285-296
A.
12th Int. Conf. DLT,
A
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
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,
Cho, H., Jeong G
Chartrand, P Zhang – Chromatic graph theory 2008
, S.-W.,
Somenzi, F., Pixley, C.: Synchronizing sequences and symbolic
traversal techniques in test generation. J. Electronic Testing 4, 19–31 (1993)
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.
J. Cerny Automata
and transportation theories -
AROUND THE CERNY CONJECTURE,
Cherubini A.
Synchronizing and collapsing words : 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
Discrete Mathematics and Theoretical Computer Science 11:1, 2009, 33–44 ...
K. Culik II, J. Karhumaki, J. Kari, A note on synchronized automata and Road
Coloring Problem,
Developments in
Language Theory (5th International Conference,
Lecture Notes in
Computer Science 2295 (2002), 175-185
K. Culik II, J. Karhumaki, J. Kari, A note on synchronized automata and Road
Coloring Problem,
International
Journal of Foundations of Computer Science 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,
Grech, M. / Kisielewicz, A., The Cerny conjecture for automata respecting intervals of a directed graph . ArXiv, 2012
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]
D. Eppstein, Reset sequences for monotonic automata, SIAM Journal of Computing
19 (1990) 500-510
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, Proceedings of the American
Mathematical 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,
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
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,
Journal of Automata,
Languages and Combinatorics 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,
International
Journal 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,
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,
B. Imreh, M. Ito, M. Steinby, On commutative directable nondeterministic
automata,
Grammars and
Automata for Strings: From Mathematics 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
M. Ito, J. Duske, On cofinal and definite automata, Acta Cybernetica 6 (1983),
181--189.
M. Ito, M. Katsura, On transitive cofinal automata, Mathematical Aspects of
Natural and Formal Languages,
World Scientific,
1994, 173-199
M. Ito and K.
Shikishima-Tsuji, Shortest Directing Words of Nondeterministic Directable
Automata.
Workshop on
Synchronizing Automata.
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 Discrete Mathematics and Theoretical Computer Science 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 Mathematics, 2-nd edition, 2009
R JUNGERS, VD
BLONDEL - Cruisable graphs.
Proceedings of the
Journees Montoises, 2006
Raphaël M. Jungers
The Synchronizing
Probability Function of an Automaton
H. Jurgensen,
Complexity, Information, Energy.
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, Journal of Universal
Computer Science 8 (2002), 270-277
J. Kari, Synchronizing finite automata on Eulerian digraphs, Mathematical
Foundations of Computer Science
(26th International Symposium, Marianske
Lazne, 2001), Lecture Notes in Computer Science 2136 (2001), 432-438
N Karimi Synchronizing
Coloring Of A Directed Graph
Proc. of the IMECS 2010, Hong Kong,, Vol III, 1-5
V. Karthikeyan and M. Rajasekar
Strong γ-Syncronization in Fuzzy Automata
International Mathematical 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
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
Applied Mathematics 29 (1970), 101-103.
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,
Kudłacik, R. Roman, A. Wagner, H.,
Effective Synchronizing Algorithms
Expert Syst. Appl., 39 (14), 11746-11757, 2012
Laemmel, A.E.,
Rudner, B.: Study of the application of coding theory, Report PIBEP-
69-034, Polytechnic Inst.
S. W. Margolis,
J.-E. Pin, M. V. Volkov, Words guaranteeing minimal image,
Words, Languages and
Combinatorics (III International Colloquium,
World Scientific,
International Journal of Foundations of Computer Science 15 (2004), 259-276
B. Marcus
Symbolic Dynamics.
Encyclopedia of Complexity and Systems Science
Springer,
P. Martjugin. A
series of slowly synchronizable automata with a zero state over a small
alphabet.
P. Martjugin. The
Length of Subset Reachability in Nondeterministic Automata
Electronic Notes in Theoretical Computer Science, Volume 223, 26 December
2008, Pages 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.
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
L. Niemela, On the
directability of automata, Kybernetika 25 (1989), 419-421
G. L. O'Brien, The road coloring problem,
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,
Developments in
Language Theory (6th International Conference,
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,
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,
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,
J.-E. Pin, Utilisation de l'algebre lineaire en theorie des automates, Actes du
1er Colloque
AFCET-
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.
A. Piricka, Directable automata and directly subdefinite events, Kybernetika 8
(1972), 395-403
E.V. Pribavkina
2-Collapsing Words
And A Sequence Reconstruction Problem,
EV Pribavkina,
LATA 2009, LNCS 5457, 672–683, 2009.
EV Pribavkina,
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
Rauff, James V
WAY BACK FROM
ANYWHERE: EXPLORING THE
Mathematics and
Computer Education. 01, 2009.
A Restivo, R Vaglica
Automata with
Extremal Minimality Conditions - Developments in Language Theory, 2010
- Springer LNCS 6224, 399-410
Rho, J.-K.,
Somenzi, F., Pixley, C.: Minimum length synchronizing sequences of ?nite
state machine. In: Proc. 30th Design Automation Conf., pp. 463–468. ACM,
York
Emanuele Rodaro
Finiteness problem for the language of minimal synchronizing words.
AROUND THE CERNY
CONJECTURE,
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.
A.
Roman, New algorithms for finding short reset sequences in synchronizing
automata
5th International Enformatika Conference (IEC 05), AUG 26-28, 2005 Prague,
CZECH REPUBLIC
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 Computational Methods in Sciences and Engineering (ICCMSE 2005), OCT
21-26, 2005
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,
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]
No.3, 3-10 [in
Russian; English translation: Cybernetics and System Analysis 28 (1992),
323-328]
No.6, 21-26 (in
Russian; English translation: Cybernetics and System Analysis 30 (1994),
807-811)
Kibernetika i
Sistemnyj Analiz (1995), No.5, 40-48 [in Russian;
English translation:
Cybernetics and System Analysis 31 (1995), 669-674]
Acta Cybernetica 12
(1995), 145-152
Publicationes
Mathematicae
172 (1997), 273-279
No.3, 32-39 [in Russian; English translation:
Cybernetics and System Analysis 36 (2000), 339-344]
No.3, 48-58 [in Russian]
I. Rystsov,
Cerny Conjecture: Retrospects and Prospects.
Workshop on Synchronizing Automata.
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
Lecture Notes in Computer Science, 7160(2012), 403-416,
W. Samotij, A note
on the complexity of the problem of finding shortest synchronizing words,
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,
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.
Chapter
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
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
[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
Journal of Combinatorics, v.17, i. 1,
2010, 3-56
B Steinberg, Cerny's conjecture and group
representation theory.
Journal of Algebraic Combinatorics 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.
B. Steinberg
The Averaging Trick
and the Cerny Conjecture
- 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. I
Workshop on synchronizing
automata,
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.
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,
LECTURE NOTES IN
COMPUTER SCIENCE 4484, 234-243, 2007
A.N. Trahtman, Cerny
Conjecture for DFA Accepting Star-free Languages.
Workshop on Synchronizing Automata.
A.N. Trahtman
Some aspect of synchronizing road coloring.
AROUND THE CERNY
CONJECTURE
Trahtman A.N.
The Road Coloring and Cerny Conjecture.
Proc. of
Trahtman A.N. Synchronizing Road Coloring.
5-th IFIP WCC-TCS, Springer, , 43-53, 273(2008).
Trahtman A.N.
The Road Coloring for Mapping on k States
Arxiv preprint arXiv:0812.4798, (withdrawn).
Dec 2008
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
Trahtman A.N, Upper bound on the length of the reset word. Dynamical asp. of Autom. and Semigr. Theor.
Trahtman A.N, Modifying the Upper Bound on the Length of Minimal Synchronizing Word.
Lect. Notes in Comp. Sci, 6914(2011) Springer, 173-180
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.
M.V. Volkov ,
Synchronizing strongly connected digraphs.
AROUND THE CERNY
CONJECTURE
M.V.
Volkov Synchronizing automata preserving a chain of partial orders
CIAA 2007,
Volkov MV
Synchronizing
Automata and the Cerny Conjecture.
Lang.& Aut. Theory & Appl. 2-d Int.Conf.,
Springer, 11-27,
2008
Volkov, M.:
Open Problems on Synchronizing Automata. Conference 'Around the
Cern y Conjecture',
Volkov, M.: Synchronizing Automata and the Road Coloring Theorem.
Tutorial
on Workshop on Algebra, Combinatorics and Complexity, WACC 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.
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.