Short synchronizing words for random automata

DOI10.1145/3736722MaRDI QIDQ6907350zbMATH OpenFDO

Authors Guillaume Chapuy, Guillem Perarnau

Publication date 3 November 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3736722

zbMATH Keywords

random automatasynchronizationw-treesČerny's conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A fast algorithm finding the shortest reset words
• A Telescopic Proof of Cayley’s Formula
• An extremal problem for two families of sets
• An improved algorithm for finding the shortest synchronizing words
• An improvement to a recent upper bound for synchronizing words of finite automata
• Analytic combinatorics
• Between primitive and 2-transitive: synchronization and its friends
• Circular automata synchronize with high probability
• Diameter and stationary distribution of random r-out digraphs
• Dixon's theorem and random synchronization
• Experimental study of the shortest reset word of random automata
• Fast synchronization of inhomogenous random automata
• Finite automata
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• On random primitive sets, directable NFAs and the generation of slowly synchronizing DFAs
• On the height of trees
• On the meeting of random walks on random DFA
• On the probability of being synchronizable
• On two Combinatorial Problems Arising from Automata Theory
• Open problems about regular languages, 35 years later
• Random deterministic automata
• Random trees have height \(O(\sqrt{n})\)
• Short Synchronizing Words for Random Automata
• Strong inapproximability of the shortest reset word
• Synchronizing Automata and the Černý Conjecture
• Synchronizing random almost-group automata
• Synchronizing random automata
• Synchronizing random automata on a 4-letter alphabet
• The action of a few permutations onr-tuples is quickly transitive
• The Cerny Conjecture Holds with High Probability
• The complexity of finding reset words in finite automata
• The complexity of synchronizing Markov decision processes
• The continuum random tree. III
• The graph structure of a deterministic automaton chosen at random

This page was built for publication: Short synchronizing words for random automata

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