24:
48:
is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a
61:
using a theorem due to Ján Černý. A simple approach considers the power set of states of the DFA, and builds a directed graph where nodes belong to the power set, and a directed edge describes the action of the transition function. A path from the node of all states to a singleton state shows the
27:
This drawing represents a DFA with eight states and two input symbols, red and blue. The word blue-red-red-blue-red-red-blue-red-red is a synchronizing word that sends all states to the yellow state; the word blue-blue-red-blue-blue-red-blue-blue-red is another synchronizing word that sends all
66:
in the number of states. A polynomial algorithm results however, due to a theorem of ÄŚernĂ˝ that exploits the substructure of the problem, and shows that a synchronizing word exists if and only if every pair of states has a synchronizing word.
221:). This algorithm does not always find the shortest possible synchronizing word for a given automaton; as Eppstein also shows, the problem of finding the shortest synchronizing word is
304:
if it contains an element of rank 1, that is, an element whose image is of cardinality 1. A DFA corresponds to a transformation semigroup with a distinguished generator set.
237: − 1) (the bound given in ÄŚernĂ˝'s conjecture), and exhibits examples of automata with this special form whose shortest synchronizing word has length exactly (
139:
621:
144:
100:
150:
The problem of estimating the length of synchronizing words has a long history and was posed independently by several authors, but it is commonly known as the
49:
synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.
233:) that always finds the shortest synchronizing word, proves that these automata always have a synchronizing word of length at most (
492:
37:
174:). If this is true, it would be tight: in his 1964 paper, ÄŚernĂ˝ exhibited a class of automata (indexed by the number
351:
616:
297:
277:
155:
402:
17:
272:
of each vertex) in order to form a synchronizable DFA. It was conjectured in 1970 by
Benjamin Weiss and
269:
250:
178:
of states) for which the shortest reset words have this length. The best upper bound known is 0.1654
501:
444:
105:
429:
580:
539:
511:
383:
360:
285:
63:
33:
525:
458:
521:
454:
281:
207:
58:
23:
594:
57:
Given a DFA, the problem of determining if it has a synchronizing word can be solved in
343:
339:
257:
225:. However, for a special class of automata in which all state transitions preserve the
210:
199:
191:
85:
610:
254:
171:
430:"An improvement to a recent upper bound for synchronizing words of finite automata"
284:
regular digraph can be labeled in this way; their conjecture was proven in 2007 by
226:
596:
Proc. 2nd Int'l. Conf. Language and
Automata Theory and Applications (LATA 2008)
387:
380:
Proc. 2nd Int'l. Conf. Language and
Automata Theory and Applications (LATA 2008)
222:
163:
593:
Volkov, Mikhail V. (2008), "Synchronizing
Automata and the ÄŚernĂ˝ Conjecture",
516:
378:
Volkov, Mikhail V. (2008), "Synchronizing
Automata and the ÄŚernĂ˝ Conjecture",
585:
471:
Adler, R. L.; Weiss, B. (1970), "Similarity of automorphisms of the torus",
273:
74:
321:
562:
Rystsov, I. C. (2004), "ÄŚernĂ˝'s conjecture: retrospects and prospects",
364:
102:
states has a synchronizing word, must it have one of length at most
449:
506:
22:
16:
For synchronizing words in the theory of synchronized codes, see
229:
of the states, he describes a different algorithm with time O(
403:"Poznámka k homogénnym experimentom s konečnými automatmi"
166:
for the length of the shortest synchronizing word for any
382:, LNCS, vol. 5196, Springer-Verlag, pp. 11–27,
602:, LNCS, vol. 5196, Springer-Verlag, pp. 11–27
564:
Proc. Worksh. Synchronizing
Automata, Turku (WSA 2004)
410:
Matematicko-fyzikálny časopis
Slovenskej Akadémie Vied
490:
Trahtman, A. N. (2009), "The road coloring problem",
108:
88:
62:
existence of a synchronizing word. This algorithm is
323:
Synchronizing automata, algorithms, Cerny
Conjecture
133:
94:
18:Self-synchronizing code § Synchronizing word
541:Permutation groups and transformation semigroups
437:Journal of Automata, Languages and Combinatorics
194:finds a synchronizing word of length at most 11
8:
473:Memoirs of the American Mathematical Society
145:(more unsolved problems in computer science)
334:
332:
253:is the problem of labeling the edges of a
584:
571:JĂĽrgensen, H. (2008), "Synchronization",
515:
505:
448:
170:-state complete DFA (a DFA with complete
125:
107:
87:
344:"Reset Sequences for Monotonic Automata"
190:-letter input alphabet, an algorithm by
313:
622:Unsolved problems in computer science
7:
77:Unsolved problem in computer science
36:, more precisely, in the theory of
292:Related: transformation semigroups
14:
182:, far from the lower bound. For
264:-letter input alphabet (where
122:
109:
1:
493:Israel Journal of Mathematics
162: − 1) is the
38:deterministic finite automata
573:Information and Computation
388:10.1007/978-3-540-88282-4_4
638:
28:states to the green state.
15:
517:10.1007/s11856-009-0062-5
428:Shitov, Yaroslav (2019),
391:; see in particular p. 19
352:SIAM Journal on Computing
134:{\displaystyle (n-1)^{2}}
586:10.1016/j.ic.2008.03.005
326:. Accessed May 15, 2010.
298:transformation semigroup
538:Cameron, Peter (2013),
241: − 1).
260:with the symbols of a
172:state transition graph
135:
96:
29:
251:road coloring problem
136:
97:
26:
106:
86:
579:(9–10): 1033–1044,
401:Černý, Ján (1964),
320:Avraham Trakhtman:
186:-state DFAs over a
278:strongly connected
158:conjectured that (
131:
92:
42:synchronizing word
30:
95:{\displaystyle n}
629:
603:
601:
589:
588:
566:
549:
547:
546:
535:
529:
528:
519:
509:
487:
481:
479:
468:
462:
461:
452:
443:(2–4): 367–373,
434:
425:
419:
417:
407:
398:
392:
390:
375:
369:
368:
348:
336:
327:
318:
286:Avraham Trahtman
198:/48 +
152:ÄŚernĂ˝ conjecture
140:
138:
137:
132:
130:
129:
101:
99:
98:
93:
78:
34:computer science
637:
636:
632:
631:
630:
628:
627:
626:
617:Finite automata
607:
606:
599:
592:
570:
561:
558:
556:Further reading
553:
552:
544:
537:
536:
532:
489:
488:
484:
470:
469:
465:
432:
427:
426:
422:
405:
400:
399:
395:
377:
376:
372:
365:10.1137/0219033
346:
340:Eppstein, David
338:
337:
330:
319:
315:
310:
294:
247:
208:time complexity
206:), and runs in
148:
147:
142:
121:
104:
103:
84:
83:
80:
76:
73:
59:polynomial time
55:
21:
12:
11:
5:
635:
633:
625:
624:
619:
609:
608:
605:
604:
590:
568:
557:
554:
551:
550:
530:
482:
463:
420:
393:
370:
359:(3): 500–510,
328:
312:
311:
309:
306:
293:
290:
258:directed graph
246:
243:
192:David Eppstein
143:
128:
124:
120:
117:
114:
111:
91:
82:If a DFA with
81:
75:
72:
69:
54:
51:
46:reset sequence
13:
10:
9:
6:
4:
3:
2:
634:
623:
620:
618:
615:
614:
612:
598:
597:
591:
587:
582:
578:
574:
569:
565:
560:
559:
555:
543:
542:
534:
531:
527:
523:
518:
513:
508:
503:
499:
495:
494:
486:
483:
478:
474:
467:
464:
460:
456:
451:
446:
442:
438:
431:
424:
421:
415:
411:
404:
397:
394:
389:
385:
381:
374:
371:
366:
362:
358:
354:
353:
345:
341:
335:
333:
329:
325:
324:
317:
314:
307:
305:
303:
302:synchronizing
299:
291:
289:
287:
283:
279:
275:
271:
267:
263:
259:
256:
252:
245:Road coloring
244:
242:
240:
236:
232:
228:
224:
220:
216:
212:
209:
205:
201:
197:
193:
189:
185:
181:
177:
173:
169:
165:
161:
157:
153:
146:
126:
118:
115:
112:
89:
70:
68:
65:
60:
52:
50:
47:
43:
39:
35:
25:
19:
595:
576:
572:
563:
540:
533:
497:
491:
485:
476:
472:
466:
440:
436:
423:
418:(in Slovak).
413:
409:
396:
379:
373:
356:
350:
322:
316:
301:
295:
265:
261:
248:
238:
234:
230:
227:cyclic order
218:
214:
203:
195:
187:
183:
179:
175:
167:
159:
151:
149:
56:
45:
41:
31:
223:NP-complete
164:upper bound
154:. In 1969,
64:exponential
611:Categories
450:1901.06542
308:References
507:0709.0099
500:: 51–60,
416:: 208–216
282:aperiodic
276:that any
274:Roy Adler
270:outdegree
156:Ján Černý
116:−
53:Existence
40:(DFA), a
342:(1990),
526:2534238
459:4023068
268:is the
255:regular
524:
457:
71:Length
600:(PDF)
545:(PDF)
502:arXiv
445:arXiv
433:(PDF)
406:(PDF)
347:(PDF)
280:and
249:The
581:doi
577:206
512:doi
498:172
384:doi
361:doi
300:is
44:or
32:In
613::
575:,
522:MR
520:,
510:,
496:,
477:98
475:,
455:MR
453:,
441:24
439:,
435:,
414:14
412:,
408:,
357:19
355:,
349:,
331:^
296:A
288:.
231:kn
219:kn
583::
567:.
548:.
514::
504::
480:.
447::
386::
367:.
363::
266:k
262:k
239:n
235:n
217:+
215:n
213:(
211:O
204:n
202:(
200:O
196:n
188:k
184:n
180:n
176:n
168:n
160:n
141:?
127:2
123:)
119:1
113:n
110:(
90:n
79::
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
