Synchronizing finite automata on Eulerian digraphs

✍ Scribed by Jarkko Kari

• Book ID: 104325497
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 126 KB
• Volume: 295
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00405-x

✦ Synopsis

Ä Cernà y's conjecture and the road coloring problem are two open problems concerning synchronization of ÿnite automata. We prove these conjectures in the special case that the vertices have uniform in-and outdegrees.