On the Probability of Being Synchronizable

DOI10.1007/978-3-319-29221-2_7zbMath1398.68298arXiv1304.5774OpenAlexW1779978478MaRDI QIDQ2795936

Mikhail V. Berlinkov

Publication date: 23 March 2016

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Automata and finite order elements in the Nottingham group, Careful synchronization of partial deterministic finite automata, Groups synchronizing a transformation of non-uniform kernel, On the Number of Synchronizing Colorings of Digraphs, The road problem and homomorphisms of directed graphs, Unnamed Item, Preimage problems for deterministic finite automata, Circular automata synchronize with high probability, Complexity of Preimage Problems for Deterministic Finite Automata, The complexity of synchronizing Markov decision processes, Algebraic synchronization criterion and computing reset words, Černý's conjecture and the road colouring problem, Diameter and stationary distribution of random \(r\)-out digraphs, Reduced checking sequences using unreliable reset, Synchronizing Almost-Group Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronizing random automata on a 4-letter alphabet
• Dixon's theorem and random synchronization
• Groups synchronizing a transformation of non-uniform kernel
• The road coloring problem
• Asymptotic expansions for the distribution of the number of components in random mappings and partitions
• Synchronizing Automata and the Černý Conjecture