Synchronizing automata with random inputs (short paper)

DOI10.1007/978-3-319-09698-8_7MaRDI QIDQ2921975zbMATH OpenOpenAlexFDO

Authors Vladimir V. Gusev

Publication date 14 October 2014

Published in Developments in Language Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We study the problem of synchronization of automata with random inputs. We present a series of automata such that the expected number of steps until synchronization is exponential in the number of states. At the same time, we show that the expected number of letters to synchronize any pair of the famous Cerny automata is at most cubic in the number of states.

Recommendations

• Synchronizing random automata
• scientific article; zbMATH DE number 6861928
• On the probability of being synchronizable
• The Cerny Conjecture Holds with High Probability
• Synchronizing random automata on a 4-letter alphabet

Cited in

(5)

• On the probability of being synchronizable
• Synchronizing random automata on a 4-letter alphabet
• scientific article; zbMATH DE number 6861928 (Why is no real title available?)
• Implementation of the algorithm for testing an automaton for synchronization in linear expected time
• Synchronizing random automata

This page was built for publication: Synchronizing automata with random inputs (short paper)

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