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), 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
R Alseidi, J Garloff. Recognition of Matrices Which are Sign-regular of a
Given Order and a Generalization of Oscillatory Matrices - 2020 -
kops.uni-konstanz.de
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)
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
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 - plms.oxfordjournals.org
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
NC Behague, JR Johnson Synchronizing Times for -sets
in Automata,–arXiv preprint arXiv:2008.12166, 2020 - arxiv.org
Arthur
Benjamin, Gary Chartrand & Ping Zhang
The
Fascinating World of Graph Theory
Popular
Math., press.princeton.edu, 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
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
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,
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.
J
Bruchertseifer, H Fernau
Synchronizing Words
and Monoid Factorization: A Parameterized Perspective.
Int. Conf. on Theory and
Applications, TAMC 2020, 352-364
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 VYS
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
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
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
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 -
arxiv.org
H Fernau, P Wolf Synchronization of Deterministic Visibly Push-Down
Automata - arXiv preprint
arXiv:2005.01374, 2020 - arxiv.org
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
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 Grech, A 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, drops.dagstuhl.de
Henk Don, Hans
Zantema
Finding DFAs with
maximal shortest synchronizing word length
arXiv:1609.06853
[math.CO]
- arXiv preprint arXiv:2007.09104,
2020 - arxiv.org
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
DISCR.
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 - arxiv.org
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,
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
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.
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)
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.
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
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,
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-
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, 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
WAY BACK FROM
ANYWHERE: EXPLORING THE
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.
AROUND THE CERNY
CONJECTURE, Wroclaw, Poland, 2008
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.
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
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
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.
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
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
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.
I
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
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.
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.
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)
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 - arxiv.org
K
Zhang, Q Wang, CL Giles Adversarial Models for Deterministic Finite
Automata - Canadian Conference on
Artificial …, 2020 - Springer
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.