Circular automata synchronize with high probability

DOI10.1016/j.jcta.2020.105356zbMath1477.68142arXiv1906.02602OpenAlexW3095856527MaRDI QIDQ2221830

Emanuele Rodaro, Daniele D'Angeli, Amnon Rosenmann, Abraham Gutierrez, Christoph Aistleitner

Publication date: 2 February 2021

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.02602

zbMATH Keywords

automatarandom matricessynchronizationcirculant graphschromatic polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Random matrices (probabilistic aspects) (60B20) Formal languages and automata (68Q45) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Synchronizing random almost-group automata
• On the Probability of Being Synchronizable
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• Circulants and their connectivities
• Synchronizing Automata and the Černý Conjecture
• Slowly Synchronizing Automata and Digraphs
• On two Combinatorial Problems Arising from Automata Theory
• Codes asynchrones
• The Cerny Conjecture Holds with High Probability
• An improvement to a recent upper bound for synchronizing words of finite automata