A fast algorithm finding the shortest reset words

DOI10.1007/978-3-642-38768-5_18MaRDI QIDQ4925236zbMATH OpenOpenAlexFDO

Authors Jakub Kowalski, Marek Szykuła, Andrzej Kisielewicz

Publication date 11 June 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

synchronizing automatonsynchronizing wordČerný conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a study using a SAT solver and considering automata up to $n=100$ states. With our algorithm we are able to consider much larger sample of automata with up to $n=300$ states. In particular, we obtain a new more precise estimation of the expected length of the shortest reset word $approx2.5sqrtn-5$.

Recommendations

• Computing the shortest reset words of synchronizing automata
• Experimental study of the shortest reset word of random automata
• Synchronizing finite automata with short reset words
• The complexity of finding reset words in finite automata
• Strong inapproximability of the shortest reset word

Cited in

(11)

• Computing the shortest reset words of synchronizing automata
• Random deterministic automata
• Approximating minimum reset sequences
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• Reset Sequences for Monotonic Automata
• scientific article; zbMATH DE number 4082982 (Why is no real title available?)
• Efficient Algorithms for Shortest Partial Seeds in Words
• Experimental study of the shortest reset word of random automata
• Fast synchronization of inhomogenous random automata
• Short synchronizing words for random automata
• An improved algorithm for finding the shortest synchronizing words

This page was built for publication: A fast algorithm finding the shortest reset words

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