On the probability of being synchronizable

DOI10.1007/978-3-319-29221-2_7MaRDI QIDQ2795936zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: We prove that a random automaton with $n$ states and any fixed non-singleton alphabet is synchronizing with high probability. Moreover, we also prove that the convergence rate is exactly $1-Theta(frac1n)$ as conjectured by Cameron cite{CamConj} for the most interesting binary alphabet case. Finally, we describe a deterministic algorithm which decides whether a given random automaton is synchronizing in linear expected time.

Recommendations

• Synchronizing random automata
• Synchronizing random automata on a 4-letter alphabet
• scientific article; zbMATH DE number 6861928
• The Cerny Conjecture Holds with High Probability
• Synchronizing automata with random inputs (short paper)

Cites work

• Asymptotic expansions for the distribution of the number of components in random mappings and partitions
• Dimensions of random recursive sets
• Distribution of the number of accessible states in a random deterministic automaton
• Dixon's theorem and random synchronization
• Groups synchronizing a transformation of non-uniform kernel
• Synchronization and stability of finite automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing random automata
• Synchronizing random automata on a 4-letter alphabet
• The road coloring problem

Cited in

(31)

• Synchronizing random almost-group automata
• The complexity of synchronizing Markov decision processes
• Černý's conjecture and the road colouring problem
• Automata and finite order elements in the Nottingham group
• Careful synchronization of partial deterministic finite automata
• Preimage problems for deterministic finite automata
• Circular automata synchronize with high probability
• Reduced checking sequences using unreliable reset
• Synchronizing automata with random inputs (short paper)
• On the Number of Synchronizing Colorings of Digraphs
• Synchronizing random automata on a 4-letter alphabet
• Dixon's theorem and random synchronization
• Groups synchronizing a transformation of non-uniform kernel
• On the synchronization of traces
• scientific article; zbMATH DE number 777287 (Why is no real title available?)
• Complexity of preimage problems for deterministic finite automata
• On randomized generation of slowly synchronizing automata
• Implementation of the algorithm for testing an automaton for synchronization in linear expected time
• The graph structure of a deterministic automaton chosen at random
• Synchronizing random automata
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Synchronizing almost-group automata
• The road problem and homomorphisms of directed graphs
• Fast synchronization of inhomogenous random automata
• Short Synchronizing Words for Random Automata
• Exact synchronization for finite-state sources
• Synchronizing automatic sequences along Piatetski-Shapiro sequences
• Short synchronizing words for random automata
• An improved algorithm for finding the shortest synchronizing words
• Random deterministic automata with one added transition
• Diameter and stationary distribution of random r-out digraphs

This page was built for publication: On the probability of being synchronizable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2795936)